/* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Turing machine simulator, written in Prolog (C) 2007 Markus Triska triska@metalevel.at Adapted from our solution to the 2005 Prolog contest. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ :- use_module(etrace). turing(Tape0, Tape) :- perform(q0, [], Ls, Tape0, Rs), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs) :- !. perform(Q0, Ls0, Ls, Rs0, Rs) :- ( Rs0 == [] -> Sym = b, RsRest = [] ; Rs0 = [Sym|RsRest] ), once(rule(Q0, Sym, Q1, NewSym, Action)), action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1), perform(Q1, Ls1, Ls, Rs1, Rs). action(left, Ls0, Ls, Rs0, Rs) :- ( Ls0 == [] -> Ls = [], Rs = [b|Rs0] ; Ls0 = [L|Ls], Rs = [L|Rs0] ). action(stay, Ls, Ls, Rs, Rs). action(right, Ls0, [Sym|Ls0], [Sym|Rs], Rs). /* - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - Example TM computing (x + 1) of a number x in unary encoding. - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ rule(q0, 1, q0, 1, right). rule(q0, b, qf, 1, stay). tm(Ts) :- turing([1,1,1], Ts). test(X) :- member(X, [a,b,c]).