Nejprve popis. Tady je kopie mailu: >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 :) Toto byl mail od Martina Marese. Ja tady predkladam jednu z moznych implementaci. Nas Turinguv stroj se bude pouzivat tako: sed -f turing.comp turing.in > turing.out -ze zadaneho turingova stroje(turing.in) vytvori sedovy skript, ktery bude jeho cinnost simulovat (turing.out) sed -f turing.out -timto se spusti Turinguv stroj(popsany v turing.in) -kazdy radek vstupu spusti cinnost Turingova stroje, format je "xabc defg...", kde -x je pocatecni stav -abcdefg... je pocatecni hodnota pasky -mezera pred "d" znaci, ze hlava Turingova stroje je prave na policku s "d" -pri zadavani pocatecniho stavu je mozno pasku nenastavit (cili vstup je jediny znak - pocatecni stav stroje), na pasce jsou pak implicitne same nuly -vsechny nase stavy budou reprezentovany jedinym pismenkem a nebude to smet byt mezera. Pokud by vam to nevyhovovalo, neni problem upravit regulerni vyrazy aby fungovaly na "delsi" stavy soubor turing.in, reprezentujici turinguv stroj, se bude skladat z radek v tomto formatu: spSPm kde s je stav Turingova stroje, p je symbol na pasce Turingova stroje. m je pohyb hlavy (bud 0 nebo - nebo +) Vyznam teto radky je: "Je-li Turinguv stroj ve stavu s a na pasce je symbol p, stroj prejde do stavu S, na pasku zapise P a hlavu posune (m=-) doleva nebo (m=+) doprava nebo (m=0) ji neposune vubec" skript turing.out bude fungovat takto: - v kazde chvili si musime pamatovat jednak aktualni stav a jednak pasku Turingova stroje. Budeme to delat tak, ze aktualni radka bude mit format "xabc def". To znamena "jsem ve stavu x, na pasce mam abcdef a hlava je na policku s pismenem d". - je treba mit na pameti, ze paska se smerem vpravo nekonecna - my si budeme pamatovat jen dosud navstivenou cast pasky. Ovsem pokud jsme na pravem kraji pasky a chceme posunout hlavu doprava, je treba na pasku "pripsat" symbol 0. - v jednom pruchodu skriptem zjistime, zda nejaka petice z turing.in neodpovida aktualnimu stavu stroje a symbolu na pasce. Pokud ano, zmenime stav stroje a symbol na pasce. Nebudeme ovsem hned hybat hlavou stroje, jen si zapamatujeme, kam se mame pohnout (na zacatek radky si pripiseme symbol " 0" nebo " -" nebo " +"; prvni mezera je tam, abych vedel, ze jsem nejakou petici jiz pouzil, druhy symbol je posun hlavy). Celou tuto zmenu dokazeme pro jednu petici provest jednim s/// asi takto s/^s\([^ ]*[ ]\)p/ +S\1P/ tento nahrazovaci prikaz probehne, pokud je na zacatku aktualni radky pismenko s a za prvni mezerou je znak p <=> stroj je ve stavu s a na pasce je prave p. Pokud probehne, tak zmeni stav tak, ze si poznaci, ze uz nejakou petici pouzil (prida mezeru na zacatek radky), ulozi si plus, ze bude treba pohnout hlavou doprava, zmeni stav stroje na S a zmeni symbol na pasce na P. To presne jsme chteli - na konci je treba jeste vyresit pohyb hlavy - je-li m=- a hlava je uplne vlevo, nic se nedeje - je-li m=- a hlava neni uplne vlevo, posun hlavu vlevo - je-li m=+ a hlava je uplne vpravo, na konec pasky se pripise symbol nula a hlava se posune vpravo (na nove pridany symbol) - je-li m=+ a hlava neni uplne vpravo, posun hlavu vpravo pokud jsem v pruchodu zmenil stav nebo symbol na pasce, je treba opakovat -> pridam skok na zacatek skriptu. To, ze se tak stalo poznam podle toho, ze na zacatku aktualni radky je mezera (ta neni platny stav, na zacatek radky se mohla dostat jen tak, ze jsem si tam pridal pri pouzivani nejake petice). Pokud je tedy mezera na zacatku, odeberu ji (za mezerou je jeste znak pro pohyb hlavy, ten odeberu taky) a skocim na zacatek radky. To zvladnou tyto dva prikazy: s/^[ ].// <- odebere prvni mezeru a dalsi znak t next; <- pokud byl predchozi s/// uspesny, skoci na next skript turing.comp, ktery vytvari popsany skript, bude pracovat nasledovane: - na zacatek vystupu vypise prikaz, ktery upravi kazdou zadanou vstupni radku do formatu, ktery zbytek skriptu ocekava (pokud uzivatelem zadana radka ma format "alespon jeden nemezerovy znak, pak mezera, pak alespon jeden nemezerovy znak", je vse v poradku. Pokud radka tento format nema, vezme se z ni prvni znak, za nej se da mezera a za ni nula). Krome toho se na zacatek skriptu vypise label next - pote z kazde petice v souboru turing.in udelam jeden (vyse popsany) nahrazovaci prikaz s/// - nakonec skriptu pridam prikazy pro pohyb hlavy Nyni uz jen vypis souboru ------------------------- turing.comp: 1 i \ /^[^ ]\\{1,\\}[ ][^ ]\\{1,\\}$/! s/^\\(.\\).*$/\\1 0/ \ :next s/\(.\)\(.\)\(.\)\(.\)\(.\)/s\/^\1\\(.*\\)[ ]\2\/ \5\3\\1 \4\// $ a\ s/^[ ]-\\(.\\)[ ]/ 0\\1 / \ s/^[ ]-\\(.*\\)\\([^ ]\\)[ ]/ 0\\1 \\2/ \ s/^[ ]+\\(.*\\)[ ]\\(.\\)$/ 0\\1\\2 0/ \ s/^[ ]+\\(.*\\)[ ]\\(.\\)/ 0\\1\\2 / \ s/^[ ]0// \ t next \ s/\\(.\\)\\(.*\\)[ ]\\(.*\\)$/State:\\1,tape:\\2#\\3/1021+ Priklad souboru turing.in: 2032+ 3043+ 4054+ 5065+ 6076+ 7087+ 80a80 a8a7- a7a6- a6a5- a5a4- a4a3- a3a2- a2a1- a1a0- a00X0 Priklad turing.out pro turing.in: /^[^ ]\{1,\}[ ][^ ]\{1,\}$/! s/^\(.\).*$/\1 0/ :next s/^1\(.*\)[ ]0/ +2\1 1/ s/^2\(.*\)[ ]0/ +3\1 2/ s/^3\(.*\)[ ]0/ +4\1 3/ s/^4\(.*\)[ ]0/ +5\1 4/ s/^5\(.*\)[ ]0/ +6\1 5/ s/^6\(.*\)[ ]0/ +7\1 6/ s/^7\(.*\)[ ]0/ +8\1 7/ s/^8\(.*\)[ ]0/ 0a\1 8/ s/^a\(.*\)[ ]8/ -a\1 7/ s/^a\(.*\)[ ]7/ -a\1 6/ s/^a\(.*\)[ ]6/ -a\1 5/ s/^a\(.*\)[ ]5/ -a\1 4/ s/^a\(.*\)[ ]4/ -a\1 3/ s/^a\(.*\)[ ]3/ -a\1 2/ s/^a\(.*\)[ ]2/ -a\1 1/ s/^a\(.*\)[ ]1/ -a\1 0/ s/^a\(.*\)[ ]0/ 00\1 X/ s/^[ ]-\(.\)[ ]/ 0\1 / s/^[ ]-\(.*\)\([^ ]\)[ ]/ 0\1 \2/ s/^[ ]+\(.*\)[ ]\(.\)$/ 0\1\2 0/ s/^[ ]+\(.*\)[ ]\(.\)/ 0\1\2 / s/^[ ]0// t next s/\(.\)\(.*\)[ ]\(.*\)$/State:\1,tape:\2#\3/