Zadani prikladu na druhem terminu UNIXu (10.5.2000)

Naprogramujte Turinguv stroj


misto meho vlastniho vykladu tohoto zadani predkladam mail od Martina Marese:

Date: Wed, 17 May 2000 11:10:12 +0200
To: Jan.Stuchl@st.ms.mff.cuni.cz
From: Vojtech Hala 
Subject: Fwd: Re: Turinguv stroj

>Date: Sun, 14 May 2000 23:29:07 +0200
>From: Martin Mares 
>To: Vojtech Hala 
>Subject: Re: Turinguv stroj
>
>Ahoj!
>
>> Na predterminu z Uvodu do UNIXu (Forst) bylo cilem naprogramovat simulator
>> Turingova stroje. Ptal jsem se nekolika lidi na definici, ale dovedel jsem
>> se same nepresne informace. Jak se, prosimte, definuje Turinguv stroj?
>
>Neformalne (prevzato z KSP):
>
>   Turinguv stroj sestává z~pásky a oídící jednotky. Páska Turingova stroje
>má jen jeden konec, a to levý (doprava je nekoneená) a je rozdilena na~políeka.
>Na~ka dém políeku se nachází právi jeden znak z~abecedy $\Sigma$ (to je
>nijaká koneená mno ina, o~které navíc víme,  e obsahuje znak $\Lambda$).
>Nad páskou se pohybuje hlava stroje, v~ka dém okam iku je nad právi jedním
>políekem.
>
>   Oídící jednotka stroje je v~ka dém okam iku v~jednom stavu ze~stavové
>mno iny $Q$ (opit nijaká koneená mno ina) a rozhoduje se podle poechodové
>funkce $f(q,z)$, která pro ka dou kombinaci stavu $q$ a znaku $z$, který
>je zrovna pod hlavou, dává uspooádanou trojici $(q^\prime,z^\prime,m)$,
>poieem  $q$ je stav, do kterého oídící jednotka poejde v~dal ím kroku,
>$z^\prime$ znak, kterým bude nahrazen znak $z$ umístiný pod hlavou a koneeni
>$m$ je buito $L$ nebo $R$ podle toho, zda se má hlava posunout doleva nebo
>doprava.
>
>   Výpoeet Turingova stroje probíhá takto: na poeátku je hlava nad nejlevij ím
>políekem, na~poeátku pásky jsou ulo ena vstupní data (zbytek pásky je vyplnin
>symboly $\Lambda$) a oídící jednotka je ve~stavu $q_0$. V~ka dém kroku výpoetu
>se Turinguv stroj podívá, co oíká funkce $f$ o~kombinaci aktuální stav + znak
>pod hlavou, naee  znak nahradí, poejde do nového stavu a posune hlavu v~udaném
>smiru. Takto pracuje do té doby, ne  narazí hlavou do levého okraje pásky, eím 
>výpoeet koneí a páska obsahuje výstup stroje.
>
>Formalne:
>
>   Turinguv stroj je usporadana petice (Sigma, Q, delta, q0, F), kde Sigma
>je konecna mnozina symbolu (abeceda) obsahujici symbol Lambda, Q je konecna
>mnozina stavu, q0 prvek Q je pocatecni stav stroje, delta: Sigma x Q ->
>Sigma x {L,R,.} je prechodova funkce stroje a F podmnozina Q je mnozina
>koncovych stavu.
>
>   Vypocet se pak nadefinuje indukci jako posloupnost kroku zacinajicich
>v q0 a rizenych prechodovou funkci (viz vyse).
>
>   Pod UNIXem bych to asi cele programoval tak, ze bych napsal sedovy script,
>ktery prepise zadani Turingova stroje na jiny sedovy script :)
>
>				Have a nice fortnight
>-- 
>Martin `MJ' Mares      http://atrey.karlin.mff.cuni.cz/~mj/
>Faculty of Math and Physics, Charles University, Prague, Czech Rep., Earth
>"To understand a program you must become both the machine and the program."
>