Editing Prolog (section)

== Turing completeness ==
Pure Prolog is based on a subset of first-order [[predicate logic]], [[Horn clause]]s, which is [[Turing completeness|Turing-complete]]. Turing completeness of Prolog can be shown by using it to simulate a Turing machine:
<syntaxhighlight lang="prolog">
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, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

symbol([], b, []).
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([], [], Rs0, [b|Rs0]).
left([L|Ls], Ls, Rs, [L|Rs]).
</syntaxhighlight>

A simple example Turing machine is specified by the facts:
<syntaxhighlight lang="prolog">
rule(q0, 1, q0, 1, right).
rule(q0, b, qf, 1, stay).
</syntaxhighlight>

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:
<syntaxhighlight lang="prolog">
?- turing([1,1,1], Ts).
Ts = [1, 1, 1, 1] ;
</syntaxhighlight>

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.