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$

turing-machines simulation

— użytkownik678392
źródło

Co rozumiesz przez „równoważną maszynę”? Jakie są dane wejściowe i jakie dane wyjściowe? (Być może chodziło Ci o jedną maszynę Turinga z taśmami ?)

k

$k$

— Yuval Filmus

Tak. Jedna tokarka z taśmami K.

— user678392,

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

\underset{k sections, one per tape}{\underset{⏟}{# \underline{ω_{1}} \dots ω_{n} # \underline{⊔} # \underline{⊔} # \dots # \underline{⊔} #}} ⊔ ⊔ ⊔ ⊔ ⊔ ⊔ \dots

$\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} Tape 1: & \underset{\land}{1} 0101 ⊔ ⊔ ⊔ \dots \\ Tape 2: & \underset{\land}{⊔} ⊔ ⊔ ⊔ ⊔ ⊔ \dots \\ Tape 3: & \underset{\land}{⊔} ⊔ ⊔ ⊔ ⊔ ⊔ \dots \end{array}

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

\land

$\wedge$

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

Potrzebujemy symbolu, który będzie oznaczać początek i koniec symulacji taśm
$\Gamma$

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

# \underset{\land}{\underline{1}} 0101 # \underline{⊔} # \underline{⊔} # ⊔ ⊔ ⊔ \dots

$\#\underset{\wedge}{\underline{1}}0101\#\underline{\sqcup}\#\underline{\sqcup}\#\sqcup\sqcup\sqcup\ldots$

\land

$\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} Tape 1: & 1 \underset{\land}{0} 101 ⊔ ⊔ ⊔ \dots \\ Tape 2: & 1 \underset{\land}{⊔} ⊔ ⊔ ⊔ ⊔ \dots \\ Tape 3: & \underset{\land}{⊔} ⊔ ⊔ ⊔ ⊔ ⊔ \dots \end{array}

$\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} Tape 1: & 10 \underset{\land}{1} 01 ⊔ ⊔ ⊔ \dots \\ Tape 2: & 1 \underset{\land}{⊔} ⊔ ⊔ ⊔ ⊔ \dots \\ Tape 3: & 1 \underset{\land}{⊔} ⊔ ⊔ ⊔ ⊔ \dots \end{array}

$\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{\land}{\underline{0}} 101 # 1 \underline{⊔} # \underline{⊔} # ⊔ ⊔ ⊔ \dots

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

Po drugim kroku:

# 10 \underset{\land}{\underline{1}} 01 # 1 \underline{⊔} # 1 \underline{⊔} # ⊔ ⊔ ⊔ \dots

$\#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).

— Luke Mathieson
źródło

Alternatywnie, użyj osobnych „ ścieżek ”, aby zapisać osobne taśmy obok siebie w tym samym miejscu. Wymaga to jednak wprowadzenia nowego alfabetu.

— Hendrik Jan

@ user678392 Szczegółowa analiza konstrukcji i zapisanie jej tutaj zajęłoby co najmniej kilka godzin. Jeśli nawet nie zamierzasz wyjaśniać, której części nie rozumiesz, dlaczego ktoś miałby włożyć tyle pracy w Twoim imieniu? A co jeśli ktoś to zrobi? Chcesz tylko powiedzieć: „Nie rozumiem tego. Ktoś inny to robi”.

— David Richerby

@ user678392 Dzięki. I dla wyjaśnienia, czy to angielski, z którym masz trudności (tj. Czy przeredagowanie może pomóc), czy potrzebujesz bardziej szczegółowych wyjaśnień?

— David Richerby

@ user678392, dodałem przykład widoku wysokiego poziomu z pierwszych kroków konwersji i praktycznych wyników na taśmach. Unikałem dyskusji o tym, jak skonstruować nowy zestaw stanów, ponieważ jest to bardzo skomplikowane i nie znajdziesz lepszego wyjaśnienia niż to, co jest w Sipser lub podobnym - jest z natury skrzypiące i matematyczne.

— Luke Mathieson

@RomaKarageorgievich Wydaje się, że wiele wyraźniejszych dowodów zniknęło w ciągu ostatnich 5 lat (nie ufaj internetowi: D). Najczystszy, jaki znalazłem, jest tutaj (ostrzeżenie, plik .doc!). Dowód w „Wprowadzenie do języków i teorii obliczeń” Martina jest całkiem dobry, jeśli masz dostęp do tej książki (str. 244 w 4. wydaniu). Dowód w „Wprowadzenie do teorii obliczeń” Sipsera jest wystarczający (s. 177 w 3 wyd.).

— Luke Mathieson