20
$\begingroup$

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

Source

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?

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

2 Answers 2

Reset to default
23
$\begingroup$

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.

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

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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