Pogovor:Turingov stroj

Iz MaFiRaWiki

V mojih časih Turingovi stroji niso smeli pisati praznih znakov. Tudi vhod je bil omejen na končno besedo sestavljeno iz nepraznih znakov. V nasprotnem primeru stroj ne more ugotoviti, kje je konec podatkov. Pa tudi delamo z akutalno neskončnostjo, kar ni preveč zdravo, saj imamo namesto števne množice vhodnikh besed kontinuum in potem diagonalni argumet ter indukcija odpovesta. TomazPisanski 14:44, 2 oktober 2006 (CEST)

Pisanje praznih znakov na trak ni škodljivo, neskončni vhod pa je lahko malo zoprna zadeva. Bom pazil, da bo prav, ko napišem razdelek o izvajanju programa. AndrejBauer 17:14, 2 oktober 2006 (CEST)

Mislim, da se motiš. Recimo, da nas zanima "jezik", ki ga sestavljajo vhodne besede oblike:

11
1P1
1PP1
1PPP1
...

Tak jezik običajno razpoznava že preprost končni avtomat. Ker stroj lahko tava levo in desno, pomeni, da je na začetku naokrog vse prazno:

... PPP11PPP ...
... PPP1P1PPP ...
... PPP1PP1PPP ...
... PPP1PPP1PPP ...
...

Zdaj pa nastopijo resne težave, pa čeprav je bralno pisalna glava Turingovega stroja nad najbolj levo enico.

Kako bi Tvoj stroj v končno mnogo korakih ugotovil, da

1

ni v jeziku? TomazPisanski 07:50, 4 oktober 2006 (CEST)

Osebna orodja