% the code of the turing machine is taken from % http://en.wikipedia.org/wiki/Prolog#Turing_completeness % and modified by Andreas Loth turing(Tape0, Tape) :- perform(q0, nil, Ls, Tape0, Rs, 1), reverse(Ls, Ls1), append(Ls1, Rs, Tape). perform(qf, Ls, Ls, Rs, Rs, _) :- !. perform(Q0, Ls0, Ls, Rs0, Rs, Step) :- write("Step: ", Step), add(Step1, Step, 1), symbol2(Rs0, Sym, RsRest), rule2(Q0, Sym, Q1, NewSym, Action), action2(Action, Ls0, Ls1, "."(NewSym, RsRest), Rs1), perform(Q1, Ls1, Ls, Rs1, Rs, Step1). symbol2(Rs0, Sym, RsRest) :- symbol(Rs0, Sym, RsRest), !. rule2(Q0, Sym, Q1, NewSym, Action) :- rule(Q0, Sym, Q1, NewSym, Action). action2(Action, Ls0, Ls1, "."(NewSym, RsRest), Rs1) :- action(Action, Ls0, Ls1, "."(NewSym, RsRest), Rs1), !. symbol(nil, b, nil). symbol("."(Sym, Rs), Sym, Rs). action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). action(stay, Ls, Ls, Rs, Rs). action(right, Ls0, "."(Sym, Ls0), "."(Sym, Rs), Rs). left(nil, nil, Rs0, "."(b, Rs0)). left("."(L, Ls), Ls, Rs, "."(L, Rs)). % the busy beaver rule-functions are taken from % http://en.wikipedia.org/wiki/Busy_beaver#Examples_of_busy_beaver_Turing_machines % 4-state, 2-symbol busy beaver, needs paramodulation % paramodulation because of different names for states and symbols "="(qa, q0). "="(halt, qf). "="(0, b). rule(qa, 0, qb, 1, right). rule(qa, 1, qb, 1, left). rule(qb, 0, qa, 1, left). rule(qb, 1, qc, 0, left). rule(qc, 0, halt, 1, right). rule(qc, 1, qd, 1, left). rule(qd, 0, qd, 1, right). rule(qd, 1, qa, 0, right). /* % 4-state, 2-symbol busy beaver, does not need paramodulation rule(q0, b, qb, 1, right). rule(q0, b, qf, 1, right). rule(q0, 1, qb, 1, left). rule(qb, b, q0, 1, left). rule(qb, 1, qc, b, left). rule(qc, b, qf, 1, right). rule(qc, 1, qd, 1, left). rule(qd, b, qd, 1, right). rule(qd, 1, q0, b, right). */ ?- turing(nil, Ts).