Comment mapper les bandes d'une machine de Turing «k-tape» dans la bande unique d'une machine de Turing «1-tape»

Je lis Sipser et j'ai du mal à comprendre quel est le processus de sorte que si vous me donnez des machines k Turing avec k bandes, je peux cracher une machine Turing équivalente avec une seule bande. Un exemple serait bien. En fait, un exemple élaboré qui montre comment passer d'une MT qui a bandes à une qui a 1 bande est ce que je recherche vraiment. Jusqu'à présent, je n'ai pas pu en trouver. Je ne cherche pas non plus de preuves.$k$

Une réponse copiée sans vergogne de moi - même :

Une machine de Turing à plusieurs bandes est essentiellement la même qu'une machine à bande unique, sauf que nous avons une fonction de transition étendue où k est le nombre de bandes. Donc, dans chaque état, la fonction de transition lit le contenu de chaque bande, passe à un nouvel état, (peut-être) écrit quelque chose sur chaque bande et déplace chaque tête - tout comme une MT régulière, sauf que maintenant nous avons plus de choses à lire, à écrire et bouger.$Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$$k$

Comme votre question le suggère, une telle machine peut être simulée par un TM à bande unique . Encore mieux, cela peut se faire avec seulement un ralentissement quadratique (donc pour les classes fermées polynomialement, il suffit de parler de machines à bande unique).

La preuve en est quelque peu impliquée et facilement disponible avec une simple recherche sur le Web, je vais donc simplement esquisser le mappage des clés des bandes sur une seule bande.$k$

L'idée de base est assez simple; nous ajoutons simplement quelques nouveaux symboles et gardons une trace de chaque bande et tête l'un après l'autre. À chaque étape du calcul, nous ne pouvons avoir visité qu'une quantité limitée de l'une des bandes, nous n'avons donc besoin que de stocker autant d'informations sur chaque bande. Ainsi, pour chaque nous ajoutons un nouveau symbole γ _ à Γ qui indiquera où se trouve la tête (pour chaque bande) à tout moment du calcul. Nous introduisons également un caractère séparateur # à Γ qui indiquera le début et la fin des bandes "virtuelles". Étant donné l'entrée ω = ω 1 … ω $\gamma \in \Gamma$$\underline{\gamma}$$\Gamma$$\#$$\Gamma$$\omega = \omega_{1}\ldots\omega_{n}$(nous pouvons supposer que même sur la machine à bandes multiples, toutes les entrées se trouvent sur la première bande - ce qui prouve pourquoi est un bon exercice) sur la machine à bandes multiples, notre machine à bande unique aura l'entrée

$$\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$$

Nous utilisons ensuite l'état de la machine à bande unique pour coder dans quel état se trouve la machine à bandes multiples et ce que les têtes regardent. La fonction de transition de la machine à bande unique est une simulation à plusieurs étapes de la fonction de transition à bandes multiples, où nous effectuons les différentes actions de bande de manière appropriée, en déplaçant la bande unique vers chaque section à tour de rôle. Les seules rides restantes sont de tout déplacer lorsque nous manquons d'espace dans une section (mais une telle sous-machine est un exercice simple) - nous ne réduisons jamais la taille de chaque section.$k$

Un exemple (espérons-le) simple:

Supposons que nous ayons une TM à 3 bandes, où l'alphabet d'entrée est juste , l'alphabet de bande est Γ = { 0 , 1 , ⊔ } et l'entrée est ω = 10101 . L'état initial de la bande de la machine ressemble à: Bande 1: 1 ∧ 0101 ⊔ ⊔ ⊔ … Bande 2: ⊔ ∧ ⊔ ⊔ ⊔ ⊔ ⊔ … Bande 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}$$ Le " " indique l'emplacement de la tête de lecture / écriture sur chaque bande.$\wedge$

Pour construire la machine à bande unique combinée, nous devons ajouter de nouveaux symboles à l'alphabet de la bande:

1. Nous avons besoin d'un symbole qui indiquera le début et la fin des bandes simulées
2. Pour chaque symbole dans nous avons également besoin d'une version qui indique que la tête de bande simulée se trouve à ce caractère sur la bande simulée.$\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$) et les têtes simulées des 3 bandes simulées (les caractères soulignés). Bien sûr, la bande s'étend infiniment vers la droite comme d'habitude. J'ai également triché légèrement en déplaçant la tête de bande sur le premier caractère de la première chaîne; strictement, il devrait commencer sur la cellule la plus à gauche, mais c'est une technicité triviale.

$\#$

$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$$

Après la deuxième étape:

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

Bien sûr, ceci est une vue de haut niveau du processus - je n'ai pas essayé d'expliquer comment construire les états, ou comment chaque bande simulée s'allonge (pour cela, vous avez besoin d'une petite routine qui vérifie si vous avez rencontré le à la fin de la bande simulée, puis déplace tout vers la droite d'une étape et le serre dans un nouveau blanc - c'est-à-dire qu'il n'ajoute des cellules de bande simulées que lorsqu'elles sont nécessaires).