Na teto strance najdete popis ruznych prechodovych funci Turingovych stroju ve zdrojove podobe pro emulator Turingova stroje v Prologu. Pocatecni stav je ve vsech prikladech q0 a programy predpokladaji, ze na zacatku stoji hlava na poslednim pravem pismenu slova.
K dispozici jsou zatim nasledujici priklady:
Vlastni zajimave priklady muzete zasilat na adresu bartak@kti.mff.cuni.cz.
Tip: pouzijte funci cut© pro prenesení zdrojového textu do svého systému Prologu.
Zdvojeni slova patri k typickym ukazkam prace jednoducheho Turingova stroje. Provadi se tak, ze se pismena postupne od konce oznacuji a zaroven se duplikuji na konec slova. Na zaver se oznacemi pismen zrusi. Vsimnete si meta-instrukce c(ql,X,q0,X,none):-X\=a2., ktera nam umozni zadat jednu instrukci v Prologu reprezentujici nekolik podobnych instrukci Turingova stroje.
Priklad: [a,a,a] -> [a,a,a,a,a,a] (volani ?-turing(q0,[a,a,a]-[],Vysledek).)
c(q0,a,qr,a2,right). % pismeno oznacim a jdu ho zapsat vpravo c(qr,a2,qr,a2,right). % bezim s pismenem vpravo c(qr,free,ql,a2,left). % zapisi pismeno (zdvojeni) a vracim se c(ql,a2,ql,a2,left). % vracim se pro dalsi pismeno vlevo c(ql,X,q0,X,none):-X\=a2. % nasel jsem pismeno, jdu na start (q0) c(q0,free,qc,free,right). % vse zkopirovano, jdu na cisteni c(qc,a2,qc,a,right). % pri behu vpravu rusim oznaceni pismen c(qc,free,qf,free,left). % koncim f(qf). % jediny koncovy stav
Kod pro zdvojovani slova nad vice-pismennou abecedou (nasledujici kod zvlada vsechny mozne abecedy) se lisi od predchoziho kodu pro zdvojeni slova nad jednopismennou abecedou. Slovo se zde postupne cte a oznacuje zleva a jeho duplikat je vytvaren na konci slova. Konci se ve chvili, kdy jsou vsechny pismena zduplikovana (jeste je potreba zrusit oznaceni pismen).
Priklad: [a,b,c] -> [a,b,c,a,b,c] (volani ?-turing(q0,[c,b,a]-[],Vysledek).)
c(q0,X,q0,X,left):-X\=free,X\=l(_). % hledam prvni nezdvojene pismeno zleva c(q0,l(X),qc,l(X),right). % zarazka na oznacenem pismenu c(q0,free,qc,free,right). % zarazka na mezere vlevo c(qc,X,qr(X),l(X),right):-X\=free,X\=l(_). % nasel jsem pismeno, oznacim ho a jdu vpravo udelat dvojnika c(qr(X),Y,qr(X),Y,right):-Y\=free. % beh doprava z duplikatem c(qr(X),free,ql,l(X),left). % zapisuji duplikat a vracim se c(ql,l(X),ql,l(X),left). % vracim se pres duplikovana pismena c(ql,X,q0,X,none):-X\=l(_). % jeste musim preskocit neduplikovana pismena c(qc,free,qf,free,left). % prazdne slovo, konec c(qc,l(X),qm,X,right). % vse duplikovano, zrus oznaceni c(qm,l(X),qm,X,right). % pri behu vpravo rusim oznaceni c(qm,free,qf,free,left). % oznaceni zruseno, konec f(qf). % jediny koncovy stav
Pridani zrcadloveho obrazu slova na jeho konec vychazi z myslenky zdvojeni slova nad jednopismennou abecedou. Pouze je treba si pamatovat prenasene pismeno ve vnitrnim stavu.
Priklad: [a,b,c] -> [a,b,c,c,b,a] (volani ?-turing(q0,[c,b,a]-[],Vysledek).)
c(q0,X,qr(X),l(X),right). % oznacim pismeno a jdu vpravo udelat jeho duplikat c(qr(X),l(Y),qr(X),l(Y),right). % bezim vpravo s duplikatem c(qr(X),free,ql,l(X),left). % zapisuji duplikat a vracim se c(ql,l(X),ql,l(X),left). % hledam dalsi nezduplikovane pismeno c(ql,X,q0,X,none):-X\=l(_). % nasel jsem, jdu na start c(q0,free,qc,free,right). % vse zduplikovano c(qc,l(X),qc,X,right). % pri ceste vpravo zrus oznaceni pismen c(qc,free,qf,free,left). % oznaceni zruseno, konec f(qf). % jediny koncovy stav
Prevraceni slova se jednoduse provedena tak, ze je vytvoren zrcadlovy duplikat pouzitim predchoziho kodu a original slova je na konci smazan.
Priklad: [a,b,c] -> [c,b,a] (volani ?-turing(q0,[a,b,c]-[],Vysledek).)
c(q0,X,qr(X),l(X),right). % originalni pismeno znacim jednoduse a jdu vpravo c(qr(X),Y,qr(X),Y,right):-Y\=free. % jdu vpravo s kopii c(qr(X),free,ql,ll(X),left). % zapisuji duplikat s dvojitym oznacenim a vracim se c(ql,ll(X),ql,ll(X),left). % vracim se vlevo pres duplikaty c(ql,l(X),ql,l(X),left). % vracim se vlevo pres jiz duplikovane originaly c(ql,X,q0,X,none):-X\=l(_),X\=ll(_). % nasel jsem dalsi pismeno, jdu na start c(q0,free,qc,free,right). c(qc,l(X),qc,free,right). % mazu original c(qc,ll(X),qc,X,right). % zrcadlovy obraz odznacim c(qc,free,qf,free,left). % vse odznaceno, konec f(qf). % jediny koncovy stav
Prevraceni slova na miste nepotrebuje dalsi misto na pasce. Provadi se tak, ze jsou postupne vymenovana pismena z konce slova za odpovidajici pismena na jeho zacatku.
Priklad: [a,b,c] -> [c,b,a] (volani ?-turing(q0,[a,b,c]-[],Vysledek).)
c(q0,free,cf,free,none). % prazdne slovo c(q0,X,cl(X),free,left):-X\=free,X\=l(_). % zapamutuji si pismeno a jdu vlevo c(cl(X),Y,cl(X),Y,left):-Y\=free,Y\=l(_). % bezim vlevo c(cl(X),free,cw(X),free,right). % koncim beh vlevo na konci slova c(cl(X),l(Y),cw(X),l(Y),right). % koncim beh vlevo na oznacenem pismenu c(cw(X),free,cl,l(X),left). % pisu pismeno a zacinam cisteni; slovo bylo liche delky c(cw(X),Y,cr(Y),l(X),right). % pisu pismeno, s dalsim pismenem jdu vpravo c(cr(X),Y,cr(X),Y,right):-Y\=free. % jdu vpravo s pismenem c(cr(X),free,q0,l(X),left). % nasel jsem volno, pisu pismeno c(q0,l(X),cl,l(X),left). % slovo obraceno, zacinam cisteni; slovo bylo sude delky c(cl,l(X),cl,l(X),left). % hledam levy konec oznaceneho slova c(cl,free,cr,free,right). % levy konec nalezen, zacinam prepis c(cr,l(X),cr,X,right). % rusim oznaceni pismen c(cr,free,cf,free,left). % oznaceni zruseno, konec f(cf). % jediny koncovy stav
Last update 6th
October 1997