Witam.
Czy jest ktoś w stanie wytłumaczyć(udowodnić) mi "na chłopski rozum" że mając Maszynę Turinga X o dwustronnie nieskończonej taśmie liczącą pewną funkcję można skonstruować Maszynę Turinga X' o dwóch jednostronnie nieskończonych taśmach która także obliczy tą funkcję? Mam dowód formalny, mało tego wydaje mi się to dosyć oczywiste, jednak nie potrafię tego dowieść(wytłumaczyć). Będę wdzięczny za każde wskazówki
No akurat przypadek który podałeś jest śmieszny, bo przecież wystarczy założyć że jak jesteś an końcu taśmy 1 i chcesz iść np. w "lewo" to przechodzisz do stanów poruszających głowicą po taśmie 2 i odwrotnie.
W ten sposób tak jakby "sklejasz" sobie te dwie taśmy i voila, możesz symulować taśmę nieskończoną dwustronnie.
Dwie taśmy nieskończone jednostronnie:
|AAAAAAAAAAAAAAAAAAA-->
|BBBBBBBBBBBBBBBBBBB-->
Jedna taśma nieskończona obustronnie:
<--AAAAAAAAAAAAAAAAAAA||BBBBBBBBBBBBBBBBBBB-->
Teraz widać? ;-)
Dzięki chłopaki za zobrazowanie problemu, trochę mi to rozjaśniło:) Rozumiem że potrzebujemy jeszcze dodatkowej funkcji przejścia która będzie kontrolować poruszanie się po dwóch taśmach(symulowanie sklejania i sterowanie głowicą w odpowiednich kierunkach)?
To akurat nie jest zbyt trudne -> wystarczy że przejście "za" koniec jednej taśmy powoduje przeskoczenie do zestawu stanów które pozwalają poruszać tylko tą drugą głowicą i analogicznie kiedy druga głowica przejdzie "za" koniec to wskakujesz do stanów które poruszają pierwszą.