Prolog - Turing Completeness

Turing Completeness

Pure Prolog is based on a subset of first-order predicate logic, Horn clauses, which is Turing-complete. Turing completeness of Prolog can be shown by using it to simulate a Turing machine:

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) :- symbol(Rs0, Sym, RsRest), once(rule(Q0, Sym, Q1, NewSym, Action)), action(Action, Ls0, Ls1, Rs1), perform(Q1, Ls1, Ls, Rs1, Rs). symbol(, b, ). symbol(, Sym, Rs). action(left, Ls0, Ls, Rs0, Rs) :- left(Ls0, Ls, Rs0, Rs). action(stay, Ls, Ls, Rs, Rs). action(right, Ls0, Rs). left(, Rs0, ). left(, Ls, Rs, ).

A simple example Turing machine is specified by the facts:

rule(q0, 1, q0, 1, right). rule(q0, b, qf, 1, stay).

This machine performs incrementation by one of a number in unary encoding: It loops over any number of "1" cells and appends an additional "1" at the end. Example query and result:

?- turing(, Ts). Ts = ;

This illustrates how any computation can be expressed declaratively as a sequence of state transitions, implemented in Prolog as a relation between successive states of interest.