Was passiert, wenn sich der Kopf einer Infinite Time Turing Machine ganz links befindet und das Programm vorschreibt, den Kopf nach links zu bewegen?

Sie haben zwei gute Alternativen zur Lösung der Frage vorgeschlagen. Jetzt sollten Sie fragen:

1. Gibt es einen Unterschied zwischen diesen beiden?
2. Wenn es einen Unterschied gibt, bestätigen beide Lösungen immer noch die Hauptsätze über unendlich lange Turing-Maschinen (insbesondere utm- und smn-Theoreme)?

Es lohnt sich, selbst darüber nachzudenken, da dies den Unterschliff von Turing-Maschinen vertieft.

In Bezug auf die Äquivalenz der beiden Lösungen können wir, soweit ich sehen kann, eine Fall-of-the-Tape-Maschine in eine Maschine umwandeln, die sich einfach nicht nach links von der ersten Zelle bewegt, indem wir eine spezielle Markierung an der Anfang des Bandes (und den Rest der Eingabe leicht nach rechts verschieben, was dauern kann$\omega$Schritte für eine unendliche Turing-Maschine). Für die andere Richtung können wir wieder eine Markierung ganz links platzieren und in einen speziellen Zustand gehen, wenn wir jemals versuchen, uns von dieser Markierung nach links zu bewegen.

Alles in allem gibt es also keinen großen Unterschied und es spielt keine Rolle, was Sie tun.

So wie ich es verstehe, gilt Ihre Sorge dem Rechenmodell in diesem Papier. Jetzt basierend auf dem ersten Zitat in Ihrer Frage (dieses Zitat stammt aus der Mathoverflow-Version Ihrer Frage, in der Sie einen Satz aus diesem Papier zitiert haben):

Die Berechnung endet nur, wenn der Haltezustand explizit erhalten wird, und in diesem Fall ist die Ausgabe das, was auch immer auf das Ausgabeband geschrieben wird. (Wenn der Kopf vom Band fällt, erfolgt keine Ausgabe.)

Um genau zu sein, nehmen wir an, wir betrachten nur Funktionen von$\mathbb{N}$Zu$\mathbb{N}$. Soweit ich das obige Zitat verstehen kann, ist die beabsichtigte Bedeutung, dass es sich um eine Eingabe handelt$x \in \mathbb{N}$während im Laufe der Berechnung die Köpfe dann vom Band fallen$f(x)$soll undefiniert sein. Das ist,$f$wird bei der Eingabe als teilweise betrachtet$x$(dasselbe wie nie anhalten).

Im Folgenden gehe ich davon aus, dass wir eine einfache Möglichkeit haben, die Ausgabe mit jeder möglichen Konfiguration auf dem Ausgabeband in Beziehung zu setzen. Eine Möglichkeit besteht beispielsweise darin, die Anzahl der aufeinanderfolgenden Einsen (beginnend bei der Zelle an der 0-Position), die auf dem Ausgabeband auftreten, als Ausgabe zu nehmen. Und wenn das Band nur 1 ist, dann nehmen Sie den Ausgang auf 0.

Nennen Sie nun das Rechenmodell mit der obigen Konvention als$C_1$. Nun, eine Möglichkeit, wie ich Ihre Frage interpretiere (dies ist möglicherweise nicht die beste Art), ist, was wäre, wenn wir die Konvention ändern und erklären würden, dass, wenn der Kopf für eine Eingabe vom Band fällt, wir die Ausgabe als das deklarieren, was sich auf dem Ausgabeband befand Zeit. Würde das resultierende Rechenmodell (z$C_2$) dieselbe Sammlung von Funktionen berechnen (aus$\mathbb{N}$Zu$\mathbb{N}$) als$C_1$? Rufen Sie die Menge der Funktionen auf ($\mathbb{N}$Zu$\mathbb{N}$) berechnet von$C_1$,$C_2$als$A_1$,$A_2$bzw. Die Frage ist ob$A_1=A_2$?

Es gibt zwei Richtungen zur Gleichheit:$A_1 \supseteq A_2$Und$A_2 \supseteq A_1$. Konzentrieren wir uns auf die erste Ungleichung. Wir wollen im Wesentlichen das Modell simulieren$C_2$innerhalb$C_1$. Betrachten Sie nun eine bestimmte Maschine im Modell$C_2$. Wenn wir dieselbe Maschine in simulieren wollen$C_1$, wir wollen eine (allgemeine) Möglichkeit haben, zu "wissen", wann der Kopf vom Band fällt. Denn in diesem Fall möchten wir das ausgeben, was sich auf dem Ausgabeband befindet (anstatt einen undefinierten Wert zurückzugeben).

Das erste ist, dass ich, da es drei Bänder gibt, so etwas schreiben werde$[0,1,0]$um eine bestimmte (zusammengesetzte) "Zelle" (die aus drei einzelnen Zellen zusammengesetzt ist) zu bezeichnen. Wenn sich das Programm nun im Startzustand befindet, bewegen wir uns zuerst nach rechts (z. B. 5 Mal) und drucken$[1,1,1]$die gleiche Anzahl von Malen (also werden die ersten fünf Zellen alle sein$[1,1,1]$) ---- Dies ist jedoch nach einer erneuten Anpassung der uns gegebenen Eingaben . Der Haupttrick besteht nun darin, dass ( nach den ersten fünf Zellen ) in unserer Simulation eine Zelle wie z$[1,0,1]$(im Originalprogramm in angegeben$C_2$) verwenden wir zwei aufeinanderfolgende Zellen. Waren anwesend$[1,0,1]$als zwei Zellen (nebeneinander platziert):$[0,0,0]$,$[1,0,1]$. Die allgemeine Idee ist, dass jede Zelle wie z$[a,b,c]$(im Originalprogramm von$C_2$) dargestellt (in unserer Simulation via$C_1$) durch zwei benachbarte Zellen, die sein werden:$[0,0,0]$,$[a,b,c]$.

Jetzt an Grenzen, da sich unsere Maschine in einen speziellen "Grenzzustand" bewegt, wobei der Kopf auf die äußerst linke Position eingestellt ist. Wenn wir uns also im Grenzzustand befinden, bewegen wir uns wieder fünfmal zum richtigen Druck$[1,1,1]$. Im Originalprogramm (von$C_2$) immer wenn es einen Übergang von einem Zustand in einen anderen hat, müssen wir es in unserer Simulation zerlegen. Wenn der ursprüngliche Übergang war sagen$([1,0,1],[1,0,0],R)$(aus$s_{10}$Zu$s_{11}$sagen wir), müssen wir es in weitere Zustände/Übergänge zerlegen. Der Punkt ist, dass$[1,0,1]$wird dargestellt als$[0,0,0]$,$[1,0,1]$(in unserer Simulation). Also, wenn unser Zeiger eingeschaltet war$[0,0,0]$wir gehen zunächst unbedingt einen Schritt nach rechts (mit Zwischenzuständen). Danach werden wir einen Übergang haben$([1,0,1],[1,0,0],R)$(und dieser Übergang führt zu einem neuen Zustand analog zu$s_{11}$in unserer Simulation). Auf diese Weise wird das ursprüngliche Programm (in$C_2$) eine Zelle verändert$[1,0,1]$Zu$[1,0,0]$. In unserer Simulation (mit program$C_1$), ändern wir die "benachbarten Zellen"$[0,0,0]$,$[1,0,1]$ ZU $[0,0,0]$,$[1,0,0]$.

Tut mir leid, dass es etwas langatmig geworden ist. Aber der eigentliche Punkt ist der nach den ersten fünf aufeinanderfolgenden Zellen$[1,1,1]$, in unserer Simulation jede der ursprünglichen Zellen des Formulars$[a,b,c]$(mit$a,b,c \in \{0,1\}$) im Programm$C_1$werden jetzt durch "zwei benachbarte Zellen" des Formulars dargestellt$[0,0,0]$,$[a,b,c]$. Wenn Sie genau hinsehen, wird das "Herunterfallen des Kopfes vom Band" jetzt durch das Auftreten von zwei aufeinanderfolgenden Zellen des Formulars angezeigt$[1,1,1]$,$[1,1,1]$(wenn wir einen Übergang simulieren, der den Kopf nach links bewegt).

Also jetzt in unserer Simulation des Programms von$C_2$(über$C_1$) Immer wenn wir feststellen, dass der "Kopf vom Band fällt", halten wir sofort an (nachdem wir die Ausgabe in die gewünschte Form geändert haben). Beachten Sie, dass ein wenig geändert werden muss, wenn wir zeigen wollen$A_2 \supseteq A_1$(bis auf den allerletzten Teil bleibt alles beim Alten).