Maszyna Turinga dowód tożsamości

0

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

1

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.

2

Dwie taśmy nieskończone jednostronnie:

|AAAAAAAAAAAAAAAAAAA-->
|BBBBBBBBBBBBBBBBBBB-->

Jedna taśma nieskończona obustronnie:

<--AAAAAAAAAAAAAAAAAAA||BBBBBBBBBBBBBBBBBBB-->

Teraz widać? ;-)

0

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)?

1

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ą.

1 użytkowników online, w tym zalogowanych: 0, gości: 1