Unendliches Alphabet Turing Machine

Ist eine Turing-Maschine, die Symbole aus einem unendlichen Alphabet lesen und schreiben darf, leistungsfähiger als ein normales TM (das ist der einzige Unterschied, die Maschine hat immer noch eine endliche Anzahl von Zuständen)?

Die Intuition sagt es mir nicht, da Sie eine unendliche Anzahl von Zuständen benötigen, um jedes Symbol zu unterscheiden. Daher denke ich, dass einige der Symbole oder Übergänge, die durch die Symbole verursacht werden (oder einige Teilmengen der Übergänge), äquivalent sein müssen. Sie können eine solche Maschine also tatsächlich mit einem regulären TM und einer begrenzten Teilmenge solcher Symbole oder Übergänge simulieren.

Wie könnte ich mich einem formalen Beweis dafür nähern?

Nein, es wäre mächtiger. Die Übergangsfunktion wäre nicht mehr endlich, und das bringt Ihnen viel Kraft.

Mit einem unendlichen Alphabet können Sie jedes Eingabeelement aus einer unendlichen Menge in einem Symbol codieren (obwohl die Eingabemenge nicht "unendlicher" sein kann als die Alphabetmenge, z. B. wäre das Alphabet vermutlich nur zählbar unendlich, also Elemente von unzähligen Mengen wie die reellen Zahlen konnten nicht in einem Symbol dargestellt werden. Und ebenso für die Ausgabe.

Sie können also ein Infinite-Alphabet-TM mit zwei Zuständen (eine Initiale, eine Annahme) mit einem einzigen Übergang erstellen, der in den Annahmezustand wechselt und das Symbol unter dem Bandkopf entsprechend der Funktion ändert, die Sie berechnen möchten. Mit diesem Rezept können Sie jede Zuordnung zwischen Sätzen berechnen, die in eine Eins-zu-Eins-Entsprechung mit dem Alphabet eingefügt werden kann.

Um zu vermeiden, dass diese entartete Art von Maschine die Antwort auf alles ist, müssen Sie die Möglichkeiten der Übergangsfunktion einschränken. Eine naheliegende wäre, zu verlangen, dass die Übergangsfunktion selbst berechenbar ist (gewöhnliche Übergangsfunktionen von TM sind schließlich trivial berechenbar, da sie endlich sind). Aber dann würden Sie versuchen, berechenbare Funktionen zu verwenden, um Ihr Modell berechenbarer Funktionen zu definieren.

Die obige Antwort ist richtig, aber es gibt noch ein wenig mehr über unendliche Alphabete und Berechenbarkeit zu sagen.

Eine Turingmaschine wird in WP als in der alle Mengen endlich sind. Somit ist die Übergangsfunktion notwendigerweise endlich.$M = (Q, \Gamma,b,\Sigma,\delta, q_0, q_f)$

$$\delta: Q / F \times \Gamma \rightarrow Q \times\Gamma \times \{L,R \}$$

In einer Maschine mit unendlichem Alphabet würden wir das Eingabealphabet durch say und damit das Bandalphabet durch und die Übergangsfunktion durch ersetzen.$\Sigma$$\Sigma^{inf}$$\Gamma^{inf}$$\delta^{inf}$

$$\delta^{inf}: Q / F \times \Gamma^{inf} \rightarrow Q \times\Gamma^{inf} \times \{L,R \}$$

So ist notwendigerweise eine unendliche Funktion. Wie bemerkt, wenn diese Funktion nicht berechenbar sein soll, ist das Obige nicht endlich darstellbar. Nehmen wir an, wir werden (teilweise) rekursiv halten, wenn möglich. Die Frage ist, ob das Alphabet dies immer zulässt.$\delta^{inf}$$\delta^{inf}$

Das Grundproblem ist, dass ein endliches Alphabet in seiner Gesamtheit dargestellt wird (so dass wir unsere Funktionen rekursiv definieren können), ein unendliches Alphabet jedoch niemals in seiner Gesamtheit dargestellt werden kann. Welcher Mechanismus erzeugt also das Alphabet?

Der einfachste Weg, dies zu berücksichtigen, besteht darin, sich vorzustellen, dass es ein endliches "Kern" -Alphabet gibt, beispielsweise . Dann erzeugen Sie eine Sprache . Es sei angenommen , dass die Zeichenfolge abaab . Definieren Sie dann . Das unendliche Alphabet besteht also aus von zu einem einzigen Symbol wie .$A=\{a,b\}$$L \subset A^*$ $\in L$$\alpha = <abaab> \in \Gamma^{inf}$$L$$<abaab>$

Das einfachste derartige Alphabet ist im Grunde <1 *> , die reguläre Sprache, in der zwei beliebige Symbole durch Zählen der Anzahl vertikaler Striche in jedem Symbol unterschieden werden. Dies kann mit einem Parser für endliche Zustände berechnet werden (allerdings als LBA, nicht als endliche Automaten). Turing plädierte für ein endliches Alphabet, um das Auftreten einer nicht endlichen Operation in einer TM-Operation zu vermeiden. Es ist jedoch anzumerken, dass die 26 Buchstaben des englischen Alphabets nicht diesem Zählmuster folgen: Buchstabe z enthält keine 26 Striche oder Punkte oder irgendetwas. Somit sind andere Muster mit dem allgemeinsten Rechenmuster möglich, das auf einer rekursiv aufzählbaren (Wieder-) Sprache basiert .$L$

Das Problem hierbei ist jedoch, dass die Konstruktion von nur möglich ist, wenn die Definition von explizit angegeben wird. Dies liegt zum einen daran, dass die Äquivalenz von Re-Sets nicht entschieden werden kann, und zum anderen daran, dass wir sonst immer nur eine endliche Stichprobe haben, mit der wir arbeiten können, und daraus nicht ableiten können . Wenn wir die Definition von (und damit ) haben, dann ist in rekursiv, dann ist in endlichem A rekursiv, und daher ist absolut rekursiv und kann rekursiv sein.$\delta^{inf}$$L$$L$$L$$\Gamma^{inf}$$f$$\Gamma^{inf}$$f$$f$$\delta^{inf}$

Schließlich betrachten wir den Fall, dass nicht mit zwei Beispielen re ist:$L$

Beispiel1 . iff divergiert nachweislich. In diesem Fall hat das Alphabet offensichtlich keine endliche Beschreibung - stattdessen "wächst" es mit der Zeit (und wird nur in einer gewissen Rechengrenze selbst vollständig definiert). Aber dann ist es ein unendliches Alphabet, das auf keinen Fall sofort präsentiert werden kann. Wenn also in rekursiv ist , dann ist f in - der Halting-Menge. So kann nicht rekursiv sein. ϕ n ( n ) Γ i n f f Γ i n f Δ 0 $<n>\in \Gamma^{inf}$$\phi_{n}(n)$$\Gamma^{inf}$$f$$\Gamma^{inf}$$\Delta_2^0$$\delta^{inf}$

Beispiel2 . Ein geometrischeres Beispiel betrachtet Penrose-ähnliche Fliesen . Das Symbol wenn eine Einheit von N aperiodischen Kacheln ist, die nachweislich die Ebene kacheln können. Dieses Alphabet ist unendlich, da man für jedes N eine N-Kachel-Einheit von Penrose-Kacheln konstruieren kann. Das Kacheln der Ebene selbst ist jedoch unentscheidbar, sodass die Menge von S wächst, wenn mehr Kacheln wie diese entdeckt werden. Ein mögliches rekursiv in aber nicht absolut rekursiv, könnte f (S) = Anzahl der Kacheln in S sein. S f Γ i n $S\in\Gamma^{inf}$$S$$f$$\Gamma^{inf}$