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

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.

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.$R$$L$

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.