Was genau bedeutet es für eine unendliche Zeit-Turingmaschine, das Stadium ωω\omega zu erreichen (und das ordinale Stadium zu begrenzen)?

Welche Bedingungen sind erforderlich, damit die Grenzstufe eintritt?

Nun, es tritt genau dann auf, wenn ... wir an einer Grenze sind.

Erinnern wir uns zunächst daran, wie klassische Turing-Maschinen für den Moment funktionieren.

Zeit für eine gewöhnliche Turing-Maschine ist$\omega$. Die Definition der Turing-Maschine sagt uns, wie man eine Maschine nimmt $\Phi$(Ich ignoriere Orakel vorerst, aber sie ändern das Bild nicht wesentlich), eine Eingabe $n$, und eine endliche Ordinalzahl $s$, und erhalten Sie eine Beschreibung (ich habe auch gehört, dass dies die (vollständige) Konfiguration genannt wird )$D(n,s)$von dem, was zur Zeit los ist$s$bei der Berechnung von$\Phi(n)$. Diese besteht aus:

• Was steht auf dem Band

• Wo der Kopf der Maschine ist

• In welchem ​​Zustand sich die Maschine befindet

zum Zeitpunkt$s$.

Beachten Sie das in der Tat, wenn wir die Karte verstehen$n,s\mapsto D(n,s)$, verstehen wir tatsächlich die ganze Maschinerie. Wir können uns also eine Turing-Maschine als genau die oben beschriebene Art von Karte vorstellen , mit der Voraussetzung, dass sie eine bestimmte Form hat.

Bei einem ITTM machen wir dasselbe, aber jetzt$s$darf eine beliebige Ordinalzahl sein. Dies sollte angesichts des Namens „ Infinite Time Turing Machine“ nicht überraschen.

Wenn Sie Details für einen Moment ignorieren, können Sie sich ein ITTM als eine Karte vorstellen, die eine Eingabe aufnimmt$A$und eine Ordnungszahl$\sigma$zu einer Beschreibung$D(A,\sigma)$... einige Regeln befolgen . Die Regel für Folgeschritte - also die Regelbestimmung$D(A,\alpha+1)$gegeben$D(A,\alpha)$- ist dasselbe wie für klassische Turing-Maschinen, aber jetzt brauchen wir eine neue Regel, um herauszufinden, was$D(A,\omega)$sollte sein (bzw$D(A,\lambda)$für jede Grenzordnungszahl$\lambda$, allgemeiner). Beachten Sie, dass hier alles ein Problem zu sein scheint:

• Wo soll der Kopf der Maschine auf dem Band sein?

• In welchem ​​Zustand soll die Maschine sein?

• Welches Symbol sollte sich bei einer gegebenen Zelle auf dem Band in dieser Zelle befinden (beachten Sie, dass es sich bis zur Grenzstufe unendlich oft hin und her geändert haben könnte)?

Lassen Sie uns jetzt etwas konkreter werden. Bei einer Eingabe$A$, erzeugt ein ITTM einen Run auf die Eingabe$A$: diese besteht aus einer ordinal-indizierten Folge von Beschreibungen, nämlich

Wenn wir es auf einem Band mit nur Nullen starten, erhalten wir hier den Lauf (mit Rot, um das Symbol zu kennzeichnen, das gerade betrachtet wird; beachten Sie, dass wir es der Einfachheit halber getrost ignorieren können, da es nur einen Zustand gibt, da es nur einen Zustand gibt).

• Zeit$0$:$(\color{red}{0}, 0,0,0,0,0,0,...)$

• Zeit$1$:$(1, \color{red}{0}, 0,0,0,0,0,...)$

• Zeit$2$:$(1,1,\color{red}{0}, 0,0,0,0,...)$

• Zeit$3$:$(1,1,1,\color{red}{0}, 0,0,0,...)$

• ...

• Zeit$\omega$:$(\color{red}{1}, 1,1,1,1,1,1,...)$

• Zeit$\omega+1$:$(0,\color{red}{1}, 1,1,1,1,1,...)$

• Zeit$\omega+2$:$(0,0,\color{red}{1}, 1,1,1,1,...)$

• ...

• Zeit$\omega^2$:$(\color{red}{1}, 1,1,1,1,1,1,...)$

• Zeit$\omega^2+1$:$(0,\color{red}{1},1,1,1,1,1,...)$

• ...

Ich habe explizit zwei unterschiedliche Limitstufen aufgeführt:$\omega$Und$\omega^2$. Bühne$\omega$war einfach, da jede Zelle auf dem Band einen "letzten Wert" hatte (nämlich$1$); Bühne$\omega^2$war ein bisschen interessanter, da jede Zelle zwischendurch wechselte$0$Und$1$schließlich oft, und so mussten wir die Begrenzungsregel auch für Symbole auf dem Band verwenden (nämlich verwenden wir das Limsup der Symbole). Beachten Sie, dass sich der Kopf bei jeder Begrenzungsstufe auf die Anfangszelle im Band "zurückzieht".

Der relevante Text im Artikel von Hamkins/Lewis lautet (hervorgehoben von mir) :

Um eine solche Grenz-Ordnungskonfiguration einzurichten, wird der Kopf von dort entfernt, wo er hingelaufen sein könnte, und auf die erste Zelle gelegt . Und es wird in einen besonders ausgezeichneten Grenzzustand versetzt . Jetzt müssen wir eine Grenze der Zellenwerte auf dem Band nehmen. Und das machen wir Zelle für Zelle nach folgender Regel: Wenn die in einer Zelle auftretenden Werte konvergiert sind, also vor der Grenzstufe entweder irgendwann 0 oder irgendwann 1 sind, dann behält die Zelle den Grenzwert bei der Stufe begrenzen. Andernfalls, für den Fall, dass die Zellenwerte unbegrenzt oft von 0 auf 1 und wieder zurück gewechselt haben, machen wir den Grenzzellenwert zu 1. Dies ist gleichbedeutend damit, den Grenzzellenwert zum Grenzwert der Zellenwerte vor dem Grenzwert zu machen .

Lassen Sie uns jetzt etwas komplizierter vorgehen und sehen, wie man taktet$\omega$. Hier brauche ich einen "Halt"-Zustand.

Unsere Maschine wird zwei Zustände haben,$S_0$Und$S_1$:

• $S_0$ist der Startzustand ; es geht nur zu sich selbst über, bewegt sich nach rechts und ändert nicht, was auf dem Band ist.

• $S_1$ist sowohl der Grenzzustand als auch der Haltezustand .

Hier ist der Lauf, den wir bekommen (beginnend mit all-$0$s auf dem Band) - beachten Sie, dass wir dieses Mal nachverfolgen müssen, in welchem ​​​​Zustand sich die Maschine befindet :

• Zeit$0$: Zustand =$S_0$, Band =$(\color{red}{0}, 0,0,0,0,0,0,...)$

• Zeit$1$: Zustand =$S_0$, Band =$(0, \color{red}{0}, 0,0,0,0,0,...)$

• Zeit$2$: Zustand =$S_0$, Band =$(0,0,\color{red}{0}, 0,0,0,0,...)$

• Zeit$3$: Zustand =$S_0$, Band =$(0,0,0,\color{red}{0}, 0,0,0,...)$

• ...

• Zeit$\omega$: Zustand =$S_1$, Band =$(\color{red}{0}, 0,0,0,0,0,0,...)$.

Beachten Sie, dass wir wie von Zauberhand zu gesprungen sind$S_1$- einfach weil$S_1$war der designierte Grenzzustand! Und jetzt, zur Zeit$\omega$, wir befinden uns im Haltezustand, also halten wir an .