Fachrat Informatik - Forum

w#x ist in der Regel wie folgt definiert: w ist ein Wort über dem Alphabet {0,1} und entspricht einer Gödelisierung einer Turingmaschine (also eine Codierung). Hierbei wird abhängig von der Eingabe (vergl. S. 45 im Skript) eine Turingmaschine aus dem Wort w erstellt, wenn w eine gültige Gödelisierung ist, ansonsten die TM, die die überall undefinierte Funktion Omega berechnet.
# ist ein Trennsymbol, damit man weiß, dass hiernach die Eingabe x für die Turingmaschine M_w (also die, die aus der Codierung w gebastelt wurde) steht.

Soweit Fragen geklärt?

Der Sinn der ganzen Simulation ist die Frage, ob die Turingmaschine auf diese Eingabe (ihrer eigenen Gödelisierung) hält oder nicht. Diese Fragestellung ist relativ speziell, deshalb heißt dieses Problem auch spezielles Halteproblem. Es wurde zudem eine allgemeinere Version des ganzen entwickelt: das allgemeine Halteproblem. Hierbei ist die Eingabe für die aus w abgeleitete TM dann immer ein beliebiges Eingabewort x (deshalb sind die Instanzen auch w#x) und nicht mehr die eigene Gödelisierung. Das spezielle Halteproblem ist also die Eingabe w#w für das allgemeine Halteproblem.
Ich hoffe die Erklärungen helfen.

Danke. Jetzt habe ich aber noch eine Frage zum Skript auf Seite 48
(Das Halteproblem auf leerem Band)

"Zu jedem Wort w#x betrachten wir die TM M(w#x), die folgendermaßen
arbeitet: ....."

Soweit ich das mitgekriegt habe, ist M(w#x) die Turingmaschine, welche
durch w gödelisiert wurde. Instinktiv würde man sagen, M(w#x) ist die
TM w.

Nun bekommt M(w#x) eine Eingabe y.
Dann unterscheidet man 2 Fälle:
Entweder y ist das leere Wort, somit schreibe man x auf das Band und simuliere Mw
auf x.
Oder die Eingabe ist nicht leer (also y ist ein beliebig langes Wort). Dann
stoppt M(w#x).

Hoffe soweit ist alles richtig.

Nun die Frage: Woher weiß die Turingmaschine M(w#x), auf welcher
Eingabe sie simuliert werden soll: x oder y?

Die Definition der Maschine ist ja

(Hast du ja auch geschrieben).

Quoted

Nun die Frage: Woher weiß die Turingmaschine M(w#x), auf welcher Eingabe sie simuliert werden soll: x oder y?

Die TM M(w#x) überprüft einfach als aller erstes, ob die Eingabe leer ist oder nicht. Ist sie leer schreibt sie x aufs Band un simuliert. Ist das Band nicht leer, so stoppt sie.
Wo ist da jetzt das Verständnisproblem?

Achso.

Also, zusammengefasst betrachtet man 3 Wörter:

w ist die Gödelisierung der TM M(w#x).
x ist ein beliebiges Eingabewort, das wir nicht kennen.
Und y ist das Wort, worauf die TM M(w#x) simuliert wird.

Falls y leer ist, wird Mw auf x simuliert.
Falls x leer ist, hält Mw,
falls x nicht leer ist hält Mw nicht.

Wieso nennt man das jetzt das Halteproblem auf leerem Band?
M(w#x) hält doch, oder nicht?

Edit: Falls die Eingabe leer ist, weiß man nicht, ob M(w#x) hält.
Bin ich da schonmal auf der richtigen Spur?

Falls die Eingabe leer ist, dann simuliert man die Maschine M_w auf Eingabe x und verhält sich dementsprechend. Das ganze ist dann quasi eine Instanz von H. Und da die Eingabe leer war, ist M_(w#x) bei leerer Eingabe die gleiche Frage für das Problem H_0. Also wird H auf H_0 mit der Funktion f(w#x)=M_(w#x) reduziert (was die eigentliche Frage bei dem Beweis war).