Matematické Fórum

Ahoj, potřeboval bych, prosím, pomoci. Mám následující úlohu:

Představte si Turingův stroj pracující na “čtverečkované rovině” (místo lineární pásky).
Vstupní slovo je zapsáno na začátku v jednom řádku, čtecí hlava stojí na jeho začátku
(ostatní buňky=čverečky obsahují prázdný znak). Obor hodnot přechodové funkce je nyní
rozšířen tak, že možné pohyby hlavy jsou Left, Right, Up, Down.
Stručně a srozumitelně popište, jak je možné simulovat tento “rovinný” stroj klasickým
“lineárním” strojem. (Nápověda. Musíte tedy popsat, jak bude mít lineární stroj uložen
na pásce obsah oné roviny; stačí mít v každém okamžiku zachycen jen obdélník obsahující
všechna políčka roviny, která simulovaný stroj dosud navštívil. Pak musíte popsat, jak bude
simulující stroj provádět analogii konkrétních instrukcí simulovaného.)

Já si to dokážu představit tak, že bych udělal jednu pásku, kde budou speciální zarážky, které mi budou odlišovat nové řádky, ale co dál? Potřeboval bych trochu nakopnout, děkuji