I know that it can be proven PROLOG is Turing-complete by constructing a program that simulates a Turing machine like this:

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]).


However, I’m wondering which parts of the PROLOG language one could strip away (esp. function symbols, clause overloading, recursion, unification) without losing Turing completeness. Are function symbols themselves Turing complete?

  • 4
    $\begingroup$ You only need the features of prolog used in your code snippet. $\endgroup$ Commented Jan 9, 2014 at 8:21
  • 1
    $\begingroup$ Have you seen this question? $\endgroup$
    – Raphael
    Commented Jan 9, 2014 at 9:15
  • 2
    $\begingroup$ @YuvalFilmus: Maybe there are other ways of programming a Turing machine in PROLOG. $\endgroup$
    – Lenar Hoyt
    Commented Jan 9, 2014 at 16:40

2 Answers 2


It's a fairly reliable rule of thumb that Turing-completeness depends on the ability to construct answers or intermediate values of unrestricted "size" and the ability to loop or recurse an unrestricted number of times. If you have those two things, you probably have Turing-completeness. (More specifically, if you can construct Peano arithmetic, then you certainly have Turing-completeness!)

Let's assume for the moment that you've already stripped arithmetic. We'll also assume that you don't have any non-logical features like atom_chars, assert, and so on, which enable general shenanigans.

If you stripped out function symbols, you can't construct answers or intermediates of unrestricted size; you can only use atoms which appear in the program and the query. As a result, the set of all possible solutions to any query is finite, so taking the least fixed point of the program/query will always terminate. Datalog (a relational database query language based on Prolog) works on this principle.

Similarly, if you restricted Prolog to primitive recursion only (that includes no recursion as a degenerate case), then the amount of recursion that you can do is bounded by the size of the query, so all computation terminates. So you need general recursion for Turing-completeness.

And, of course, if you have general recursion, you can cut a whole bunch of features and retain Turing-completeness, including general unification (construction and top-level pattern matching is sufficient), negation, and the cut.

  • 4
    $\begingroup$ One binary horn clause is enough. $\endgroup$
    – false
    Commented Feb 13, 2017 at 14:10
  • $\begingroup$ Very good point. I wasn't thinking about quantification, but that indeed is another approach. $\endgroup$
    – Pseudonym
    Commented Feb 13, 2017 at 22:33
  • $\begingroup$ How come we can't implement list intersection in pure Prolog? $\endgroup$
    – MWB
    Commented Dec 18, 2020 at 10:37
  • $\begingroup$ @Pseudonym doesn’t recursion/fold already imply “intermediate values of unbounded size”? $\endgroup$ Commented Apr 5, 2022 at 11:50
  • $\begingroup$ @ErikKaplun Primitive recursion always terminates (and primitive corecursion always coterminates) and is therefore not Turing-complete. $\endgroup$
    – Pseudonym
    Commented Apr 5, 2022 at 23:39

Completing the excellent answer by @Pseudonym and referring to your last question "Are function symbols themselves Turing complete?".

You probably mean: Can a language made only of function symbols be Turing-Complete?

The answer is yes - think of Functional Programming languages like ML and Haskell.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.