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 HalaSubject: 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." >