Matematické Fórum

Ahojte vsetci. Mam taketo zadanie projektu a neviem s tym vobec pohnut.

(Další otázka týkající se Turingových strojů)
Představme si, že navrhujeme Turingův stroj M , přičemž chceme používat již hotový M1 jako proceduru, které lze předat vstup (parametr), tj. řetězec symbolů, a obdržet od ní příslušný výstup. K tomu se hodí chápat M jako dvoupáskový (víme, že vícepáskový stroj lze simulovat jednopáskovým, je-li potřeba). Když M potřebuje výstup M1 odpovídající vstupu w, neboli potřebuje zjistit řetězec M1 (w), napíše w na druhou pásku, na ní pak nechá běžet M1 a až M1 skončí, překopíruje si M výsledný řetězec z druhé pásky na „základní pásku a udělá si s ním, co potřebuje. Popište teď, jak byste řešili případ, kdy M potřebuje takto „volat stroje M1 , M2 , . . . , Mk , které se ovšem mohou také rekurzivně volat navzájem.


Dakujem za hocijaku radu, ako to vyriesit.