So ordnen Sie die Bänder einer „K-Tape“ -Turingmaschine dem einzelnen Band einer „1-Tape“ -Turingmaschine zu

Ich lese Sipser und finde es schwierig zu verstehen, wie der Prozess abläuft. Wenn Sie mir k Turing-Maschinen mit k Bändern geben, kann ich eine äquivalente Turing-Maschine mit nur einem Band ausspucken. Ein Beispiel wäre schön. Eigentlich ein ausgearbeitetes Beispiel, das zeigt, wie man von TM mit$k$bin ich auf der Suche nach k Bändern zu einem mit 1 Band wechselt. Ich konnte bisher keinen finden. Ich suche auch keine Beweise.

Eine schamlos von mir kopierte Antwort :

Eine Mehrband-Turingmaschine ist meistens dieselbe wie eine Einzelbandmaschine, außer dass wir eine erweiterte Übergangsfunktion wobei k die Anzahl der Bänder ist. In jedem Zustand liest die Übergangsfunktion den Inhalt jedes Bandes, wechselt in einen neuen Zustand, schreibt (vielleicht) etwas auf jedes Band und bewegt jeden Kopf - genau wie ein normales TM, außer dass wir jetzt mehr Dinge zum Lesen und Schreiben haben und bewegen.$Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$$k$

Wie aus Ihrer Frage hervorgeht, kann eine solche Maschine mit einem Single-Tape- TM simuliert werden . Noch besser ist, dass dies nur mit quadratischer Verlangsamung möglich ist (für polynomiell geschlossene Klassen reicht es also aus, über Einzelbandmaschinen zu sprechen).

Der Beweis dafür ist etwas aufwendig und mit einer einfachen Websuche leicht verfügbar, daher skizziere ich einfach die Tastenzuordnung der Bänder auf ein einzelnes Band.$k$

Die Grundidee ist ziemlich einfach; Wir fügen einfach ein paar neue Symbole hinzu und verfolgen jedes Band und jeden Kopf nacheinander. Bei jedem Schritt in der Berechnung können wir nur eine begrenzte Anzahl von Bändern besucht haben, sodass wir nur so viele Informationen über jedes Band speichern müssen. Daher fügen wir für jedes ein neues Symbol γ _ zu Γ hinzu, das angibt, wo sich der Kopf (für jedes Band) an einem beliebigen Punkt der Berechnung befindet. Wir führen auch ein Trennzeichen # in Γ ein, das den Beginn und das Ende der "virtuellen" Bänder angibt. Gegebener Eingang ω = ω 1 … ω $\gamma \in \Gamma$$\underline{\gamma}$$\Gamma$$\#$$\Gamma$$\omega = \omega_{1}\ldots\omega_{n}$(Wir können davon ausgehen, dass sich selbst auf dem Multibandgerät der gesamte Eingang auf dem ersten Band befindet - was beweist, warum dies eine gute Übung ist). Auf dem Multibandgerät hat unser Einzelbandgerät den Eingang

$$\underbrace{\#\underline{\omega_{1}}\ldots\omega_{n}\#\underline{\sqcup}\#\underline{\sqcup}\#\ldots\#\underline{\sqcup}\#}_{k \text{ sections, one per tape}}\sqcup\sqcup\sqcup\sqcup\sqcup\sqcup\ldots$$

Wir verwenden dann den Status der Einzelbandmaschine, um zu codieren, in welchem ​​Zustand sich die Mehrbandmaschine befindet und was die Köpfe betrachten. Die Übergangsfunktion der Einzelbandmaschine ist eine mehrstufige Simulation der Mehrbandübergangsfunktion, bei der wir die verschiedenen Bandaktionen entsprechend ausführen und das einzelne Band nacheinander zu jedem Abschnitt nach oben bewegen. Die einzigen verbleibenden Falten bestehen darin, alles zu verschieben, wenn wir in einem Abschnitt keinen Platz mehr haben (aber eine solche Submaschine ist eine einfache Übung) - wir reduzieren niemals die Größe jedes Abschnitts.$k$

Ein (hoffentlich) einfaches Beispiel:

Angenommen, wir haben ein 3-Band-TM, bei dem das Eingabealphabet nur , das Bandalphabet Γ = { 0 , 1 , ⊔ } und die Eingabe ω = 10101 ist . Der anfängliche Bandstatus des Geräts sieht folgendermaßen aus: Band 1: 1 ∧ 0101 ⊔ ⊔ ⊔ … Band 2: 3 ∧ ∧ ⊔ ⊔ ⊔ ⊔ … Band 3: ⊔ ∧ ⊔ ⊔ ⊔ ⊔ ⊔ $\Sigma=\{0,1\}$$\Gamma=\{0,1,\sqcup\}$$\omega=10101$

$$\begin{array}{lc} \text{Tape 1:} & \underset{\wedge}{1}0101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$ Das " " gibt an, wo sich der Lese- / Schreibkopf auf jedem Band befindet.$\wedge$

Um die kombinierte Einzelbandmaschine zu konstruieren, müssen wir dem Bandalphabet neue Symbole hinzufügen:

1. Wir brauchen ein Symbol, das den Anfang und das Ende der simulierten Bänder kennzeichnet
2. Für jedes Symbol in benötigen wir außerdem eine Version, die angibt, dass sich der simulierte Bandkopf an diesem Zeichen auf dem simulierten Band befindet.$\Gamma$

$\Gamma' =\{0,1,\sqcup,\underline{0},\underline{1},\underline{\sqcup},\#\}$

$$\#\underset{\wedge}{\underline{1}}0101\#\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$ $\wedge$) und die simulierten Köpfe der 3 simulierten Bänder (die unterstrichenen Zeichen). Natürlich erstreckt sich das Band wie gewohnt unendlich nach rechts. Ich habe auch leicht betrogen, indem ich den Bandkopf zum ersten Zeichen auf der ersten Saite bewegt habe; streng genommen sollte es in der Zelle ganz links beginnen, aber dies ist eine triviale Technik.

$\#$

$1$$1$$0$$1$

$1$

$$\begin{array}{lc} \text{Tape 1:} & 1\underset{\wedge}{0}101\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & \underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$

$0$

$$\begin{array}{lc} \text{Tape 1:} & 10\underset{\wedge}{1}01\sqcup\sqcup\sqcup\ldots\\ \text{Tape 2:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \text{Tape 3:} & 1\underset{\wedge}{\sqcup}\sqcup\sqcup\sqcup\sqcup\ldots\\ \end{array}$$

$\Gamma'$

$$\#1\underset{\wedge}{\underline{0}}101\#1\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$

Nach dem zweiten Schritt:

$$\#10\underset{\wedge}{\underline{1}}01\#1\underline{\sqcup}\#1\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$$

Natürlich ist dies eine allgemeine Ansicht des Prozesses - ich habe nicht versucht zu erklären, wie die Zustände aufgebaut werden oder wie jedes simulierte Band länger wird (dazu benötigen Sie eine kleine Routine, die überprüft, ob Sie auf den gestoßen sind Ende des simulierten Bandes, bewegt dann alles einen Schritt nach rechts und drückt einen neuen Rohling ein - dh es werden nur simulierte Bandzellen hinzugefügt, wenn sie benötigt werden).