What makes PROLOG Turing-complete?

Problem Detail: 

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?

Asked By : Lenar Hoyt

Answered By : Pseudonym

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19591