Jak zamapować taśmy maszyny Turinga typu „k-tape” na pojedynczą taśmę maszyny Turinga typu „1-tape”

Czytam Sipser i trudno mi zrozumieć, na czym polega ten proces, więc jeśli dasz mi k maszyn Turinga z k taśmami, mogę wypluć równoważną maszynę Turinga za pomocą tylko jednej taśmy. Przykład byłby miły. Właściwie to naprawdę opracowany przykład, który pokazuje, jak przejść z TM z taśmami na tę, która ma 1 taśmę, jest tym, czego naprawdę szukam. Jak dotąd nie udało mi się go znaleźć. Nie szukam też żadnych dowodów.$k$

Odpowiedź bezwstydnie skopiowana ode mnie :

Maszyna Turinga z wieloma taśmami jest w większości taka sama jak maszyna z jedną taśmą, tyle że mamy rozszerzoną funkcję przejścia gdzie to liczba taśm. Tak więc w każdym stanie funkcja przejścia odczytuje zawartość każdej taśmy, przechodzi do nowego stanu, (być może) zapisuje coś na każdej taśmie i przesuwa każdą głowę - tak jak zwykła TM, tyle że teraz mamy więcej rzeczy do czytania, pisania i ruszaj się.$Q\times\Gamma^{k}\rightarrow Q\times\Gamma^{k}\times\{L,R\}^{k}$$k$

Jak sugeruje twoje pytanie, taką maszynę można symulować za pomocą TM z jedną taśmą . Co więcej, można tego dokonać tylko z kwadratowym spowolnieniem (więc w przypadku klas wielomianowo zamkniętych wystarczy mówić o maszynach z jedną taśmą).

Dowód na to jest nieco zaangażowany i łatwo dostępny za pomocą prostego wyszukiwania w sieci, więc po prostu naszkicuję kluczowe mapowanie taśm na pojedynczą taśmę.$k$

Podstawowa idea jest dość prosta; po prostu dodajemy kilka nowych symboli i śledzimy każdą taśmę i przewijamy jeden po drugim. Na każdym etapie obliczeń odwiedziliśmy tylko skończoną liczbę dowolnych taśm, więc musimy przechowywać tylko tyle informacji o każdej taśmie. Zatem dla każdego dodajemy nowy symbol do który będzie wskazywał, gdzie głowa (dla każdej taśmy) znajduje się w dowolnym punkcie obliczeń. Wprowadzamy również znak separatora do który będzie wskazywał początek i koniec „wirtualnych” taśm. Biorąc pod uwagę dane wejściowe ω = ω 1 … ω nγ _ Γ # $\gamma \in \Gamma$$\underline{\gamma}$$\Gamma$$\#$$\Gamma$$\omega = \omega_{1}\ldots\omega_{n}$(możemy założyć, że nawet na maszynie z wieloma taśmami wszystkie dane wejściowe znajdują się na pierwszej taśmie - co dowodzi, dlaczego jest to dobre ćwiczenie) na maszynie z wieloma taśmami, nasza maszyna z jedną taśmą będzie miała wejście

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

$k$

(Mam nadzieję) prosty przykład:

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

Aby zbudować połączoną maszynę z jedną taśmą, musimy dodać nowe symbole do alfabetu taśmy:

1. Potrzebujemy symbolu, który będzie oznaczać początek i koniec symulacji taśm
2. $\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$) i symulowane głowice 3 symulowanych taśm (podkreślone znaki). Oczywiście taśma jak zwykle rozciąga się nieskończenie w prawo. Oszukałem też łagodnie, przesuwając głowicę taśmy do pierwszego znaku na pierwszym sznurku; ściśle powinien zacząć się od lewej komórki, ale jest to banalna technika.

$\#$

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

$1$ na drugiej taśmie, a pierwsza i druga głowica przesuną się w prawo o jeden krok:

$$\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$ , więc zamiast tego piszemy na trzeciej taśmie:

$$\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'$ i pisząc na odpowiedniej symulowanej taśmie. Tak więc po pierwszym kroku połączona taśma wygląda następująco:

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

Po drugim kroku:

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

Oczywiście jest to ogólny widok procesu - nie próbowałem wyjaśniać, jak konstruować stany, ani jak każda symulowana taśma wydłuża się (w tym celu potrzebna jest rutyna, która sprawdza, czy napotkano koniec symulowanej taśmy, a następnie przesuwa wszystko o jeden krok w prawo i wciska nowy blank - tzn. dodaje symulowane komórki taśmy tylko wtedy, gdy są potrzebne).