Maszyna Turinga - nieskończona taśma w jednym lub dwóch kierunkach

11

Widziałem maszyny Turinga przedstawiane za pomocą taśm nieskończonych w jednym i w dwóch kierunkach. Czy jest jakaś różnica w mocy takich maszyn Turinga, czy są one zasadniczo równoważne? W mojej głowie myślę, że są one równoważne, ponieważ sądzę, że musi istnieć jakiś sposób na przedstawienie dwustronnej nieskończonej taśmy jako jednokierunkowej nieskończonej taśmy, ale nie mogę znaleźć dowodu ani przykładu.

użytkownik2795095
źródło
1
Duplikujesz stany i symbole taśmy, dzięki czemu masz wersję dla prawej części i drugą dla lewej części. Na taśmie przechowujesz pary symboli, lewy i prawy. Dostosowujesz funkcję przejścia, aby zmieniała tylko część pary odpowiadającą połowie taśmy, z którą obecnie pracujesz. I dodaj trochę zarządzania, gdy musisz zmienić rozważaną pół taśmy. Nie zapominaj, że jeśli złożysz prawą pół taśmę po lewej, ruchy głowy zostaną odwrócone. Więc odpowiednio zmień przejścia dla odpowiednich stanów.
babou
@babou Zamień się w pełnoprawną odpowiedź?
Yuval Filmus

Odpowiedzi:

12

Są równoważne pod względem mocy obliczeniowej. Wszystko, co można obliczyć za pomocą jednego z tych dwóch rodzajów maszyn Turinga, można obliczyć za pomocą drugiego rodzaju. Spójrzmy, jak symulować maszynę Turinga z podwójnie nieskończoną taśmą, na maszynie Turinga z pojedynczo nieskończoną taśmą.

Chodzi o to, aby przeciąć podwójnie nieskończoną taśmę na dwie części, tak aby mieć dwie pojedynczo nieskończone taśmy, lewą i prawą, które ostatecznie połączycie. Możesz oznaczyć końce miejscem na taśmie zawierającym specjalny symbol EOF. Powielasz również swoją kontrolę skończoną, dzięki czemu masz dwie identyczne kontrole stanu skończonego. Zakładasz, że masz urządzenie przekazujące sterowanie (patrz poniżej), więc gdy lewy komputer próbuje wyjść poza prawy koniec taśmy, przekazuje sterowanie do prawego komputera, w jego skrajnie lewej pozycji taśmy (tuż przed lewy koniec prawej taśmy). I odwrotnie, przy próbie przejścia lewego końca prawej taśmy.

Teraz, aby rozróżnić lewą i prawą maszynę, zmieniamy nazwy stanów i symbole taśmy, indeksując je odpowiednio i odpowiednio dla lewej i prawej maszyny. I odpowiednio zmieniamy przejścia dwóch maszyn, aby działały jak poprzednio.RL

Teraz jesteśmy gotowi połączyć dwie pół-taśmy, na przykład składając prawą na lewą. W tym celu odwróć prawą połowę taśmy i ostrożnie zmodyfikuj odpowiednio przejścia, wymieniając prawą na lewą i lewą na prawą. Następnie łączymy dwie połówki taśmy w jedną taśmę zawierającą pary symboli, lewą i prawą, przy czym każdy element jest prawdopodobnie pusty.

Ponownie modyfikujesz przejścia obu komputerów, tak aby lewe (lub prawe) przejścia wykorzystywały i modyfikowały tylko lewą (lub prawą) część par na taśmie. Następnie scalasz kontrolę nad dwoma maszynami przez proste połączenie odpowiednio dla stanów i przejść.

Dodajesz zestaw przejść dla każdego istniejącego stanu, tak że gdy symbolem taśmy jest EOF, wraca do poprzedniej lokalizacji taśmy (pierwsza lokalizacja inna niż EOF), a stan zmienia się na chiralny odpowiednik: jeśli jest lewą (odpowiednio. po prawej), zmienia się na swój prawy (lub odpowiednio lewy) odpowiednik. To jest urządzenie przekazujące kontrolę.

Mogłem zapomnieć o szczegółach, ale taka jest ogólna idea konstrukcji. Dowód jest pozostawiony jako wykonanie.

Oczywiście początkowa taśma (wejście) musi zostać odpowiednio zmodyfikowana. Ale można to uprościć, umieszczając wejście (jeśli jest skończone) całkowicie po lewej stronie (tej, która nie jest odwrócona) przeciętej taśmy.

Następnie odłóż śrubokręt, ponieważ może to być niebezpieczne dla dzieci.

PS Pokazałem tylko, że podwójnie nieskończoną taśmę można symulować za pomocą pojedynczo nieskończonej taśmy. Rozmowa wydaje się zbyt oczywista.

Babou
źródło
@DW Dzięki za edycję. Powinienem był to zrobić. O ile pamiętam, wstawiłem ostatni wiersz jako uzupełnienie w trakcie 5-minutowego okresu karencji po edycji. Biorąc pod uwagę istniejące zasady dotyczące liczby zmian, zwykle czekam na zebranie potrzebnych zmian przed nową sesją edycji.
babou
Ach, tak, zasady edycji! Nie jestem fanem zasad ograniczających liczbę edycji; w każdej chwili ludzie niechętnie poprawiają swoją odpowiedź, wydaje się to stratą dla strony, ale cóż, co zrobisz? Przepraszam, że podniosłem twoją liczbę edycji o jeden - nie chciałem ci przeszkadzać, biorąc pod uwagę ilość pracy, którą już włożyłeś, ale może powinienem był zapytać pierwszy. Dzięki za świetną odpowiedź!
DW
Pytanie z prośbą o wydajną symulację: cs.stackexchange.com/questions/28901/…
Ciro Santilli 冠状 病毒 审查 六四 事件 法轮功