Verständnisporblem zu anhalten/nicht-anhalten von TM

Question

Hierzu eine kleine Frage:

"Die Menge der Turingmaschinen, die nicht anhalten, ist nicht aufzählbar aber abzählbar."

 

"Die Menge der Turingmaschinen mit zugehöriger Eingabe, die anhalten, ist aufzählbar, aber nicht entscheidbar, da für eine Turingmaschine, die nicht anhält, nicht entschieden werden kann, ob sie in dieser Menge liegt."

 

Bezieht sich die erste Aussage auf Turingmaschinen, die überhaupt nie halten egal für welche Eingabe? Die zweite Aussage verwirrt mich nämlich ein wenig, da zuerst von anhaltenden TM die Rede ist, dann aber wieder von nichtanhaltenden. Bezieht sich die zweite Aussage damit auf TM, die akzeptierend halten für eine Eingabe aus einer Menge und endlos weiterlaufen, falls die Eingabe nicht aus der Menge ist? Oder wo ist jetzt der Unterschied zwischen den TM aus der ersten und der zweiten Aussage?

Danke!

 

Answer 1

Hallo,

wir haben das vielleicht ein wenig missverständlich (wenn auch nicht falsch) formuliert.

Man kann die erste Menge konkreter und - mit Bezug auf die Diagonalsprache $L_{NA}$ aus der Vorlesung - besser angeben als:

"Die Menge der Kodierungen aller Turingmaschinen, die auf ihrer eigenen Kodierung als Eingabe nicht halten..."

Die Beschreibung der zweiten Menge würde ich dann auch etwas anpassen:

"Die Menge der Kodierungen aller Turingmaschinen mit einer zugehörigen Eingabe, die auf dieser Eingabe anhalten..."

Der Unterschied, der das erste Problem schwieriger macht als das zweite, liegt darin, dass man hier wissen will, ob die Turingmaschine NICHT anhält. Will man nämlich "nur" wissen, ob die Turingmaschine anhält, dann kann man sie  "einfach" simulieren und warten, ob sie anhält. Falls sie anhält, hat man die positive Antwort, nur falls nicht, weiß man nicht, ob sie irgendwann anhalten wird oder doch ewig weiterlaufen.

Will man also die zweite Menge $M$ aufzählen, kann man bspw. folgendermaßen vorgehen:

    Erzeuge eine Ordnung (bspw. längenlexikographisch) der Kodierungen aller Turingmaschinen mit Eingaben: $<T1,w1>,<T2,w2>,…;$
    Simuliere $T1$ auf $w1$ einen Schritt weit;
    Simuliere $T1$ auf $w1$ einen weiteren Schritt und $T2$ auf $w2$ einen Schritt weit;
    Simuliere $T1$ auf $w1$ und $T2$ auf $w2$ einen weiteren Schritt und $T3$ auf $w3$ einen Schritt weit;
    ...

Falls irgendeine der Turingmaschinen während der Simulation anhält, füge sie mit der zugehörigen Eingabe zu $M$ hinzu. Auf diese Weise werden alle Turingmaschine-Eingabe-Paare, für die die Simulation anhält, nach endlicher Zeit zu der Menge $M$ hinzugefügt.

Dieses Vorgehen ist bei der ersten Menge nicht möglich, da man, um sicher zu sein, dass eine Turingmaschine NICHT anhält, unendlich lange warten müsste.

Viele Grüße

Lukas König