Is pure Prolog Turing-complete, and if so, why can't it implement list intersection?

Question

The Wikipedia section on this topic is a mess. It states:

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:

(emphasis added)

And then it goes on to show code that uses things that are not Horn clauses (! and once):

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

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

OK, so Prolog is Turing-complete. No one doubted that. What about pure Prolog?

If pure Prolog is, in fact, Turing-complete, how come we seemingly can't implement list intersection (the first list filtered by membership in the second list) in it? All implementations use at least one of the following: !, \+, findall, call directly or indirectly.

Answer 1

how come we seemingly can't implement list intersection (the first list filtered by membership in the second list) in it? All implementations use at least one of the following: !, \+, findall, call directly or indirectly.

Please note that the answer using if_/3 does not need any cut at all. The cut (or if-then-else) is here merely for performance and robustness reasons (that is to catch determinate cases and to signal errors in case of unintended use). You can expand it all to a version without any such constructs. It will terminate the same way, but be less efficient in current implementations.

Here are the purified versions of if_/3 and (=)/3:

if_(If_1, Then_0, Else_0) :-
   call(If_1, T),
   (  T = true, call(Then_0)
   ;  T = false, call(Else_0)
   %;  nonvar(T) -> throw(error(type_error(boolean,T),_))
   %;  /* var(T) */ throw(error(instantiation_error,_))
   ).

=(X, X, true).
=(X, Y, false) :-
   dif(X,Y).

And, in case you do not accept the call/2 and call/1 (after all both are not part of first order logic), you would have to expand each use accordingly. In other words, all uses of if_/3 are such that such an expansion is possible.

As for Turing completeness, this is already established using a single rule. See this question and the references contained therein how this is possible (it is really not that intuitive).

Answer 2

You can build a Turing Machine with your language, whereby the current tape and inner state are represented as "accumulator terms". It's just that you cannot use the "!" to commit to a selected clause for an essentially deterministic "proof", so a real implementation would be laden with ever-growing stack (that will never be visited again) in addition to growing terms. But in the Turing Universe, space is free, time is infinite and thermodynamically usable energy is abundant (plus there is a big heat sink around). No worries!

Actually a nice exercise to build Marvin Minsky's minimal Universal Turing Machine in pure Prolog.

---

Edit: How about this implementation of "intersect". What's missing?

% horn_intersect(++List1,++List2,?List3)
% List3 is the intersection of List1 and List2
% Assumptions: 
% 1) All the members of List1, List2, List3 are grounded
%    No unbound variables (a non-logical concept)
% 2) We don't care about determinism. The same solution
%    may be generated several times (as long as it's right)
%    Choicepoints are not removed.
% 3) There is a dataflow direction: (List1,List2) --> List3.
%    This also ensures that this is a function (only one solution,
%    though represented by a set of equivalent solutions)
%    These are not foreseen:
%    Going the other ways (List1,List3) --> "an infinite set of List2 templates"
%    Going the other ways (List2,Listd) --> "an infinite set of List1 templates"
%    Going the other ways List3         --> "an infinite set of (List1,List2) templates tuples"
%    However, accepting a (List1,List2,List3) is ok.

horn_intersect([],_,[]).
horn_intersect(_,[],[]).

horn_intersect([X|Xs],List2,[X|Ms]) :- in(X,List2),horn_intersect(Xs,List2,Ms).
horn_intersect([X|Xs],List2,Ms)     :- not_in(X,List2),horn_intersect(Xs,List2,Ms).

in(X,[X|_]).
in(X,[K|Ms]) :- X\=K,in(X,Ms).

not_in(_,[]).
not_in(X,[K|Ms]) :- X\=K,not_in(X,Ms).

:- begin_tests(horn_horn_intersect).

test(1,[true,nondet])           :- horn_intersect([a,b,c],[a,b,c],[a,b,c]).
test(2,[true,nondet])           :- horn_intersect([b],[a,b,c],[b]).
test(3,[true,nondet])           :- horn_intersect([a,b,c],[b],[b]).
test(4,[true,nondet])           :- horn_intersect([a,b,c],[],[]).
test(5,[true,nondet])           :- horn_intersect([],[a,b,c],[]).
test(6,[true,nondet])           :- horn_intersect([x,y],[a,b],[]).
test(7,fail)                    :- horn_intersect([x,y],[a,b],[u,v]).
test(8,[Out == [], nondet])     :- horn_intersect([x,y],[a,b],Out).
test(9,[Out == [a,b], nondet])  :- horn_intersect([a,b,c],[a,b],Out).
test(10,[Out == [a,b], nondet]) :- horn_intersect([a,b],[a,b,c],Out).
test(11,[Out == [], nondet])    :- horn_intersect([x,y],[a,b],Out).
   
:- end_tests(horn_horn_intersect).

Answer 3

If you enconde states as Peano numbers, and use 0 for halt.
And s(X) for all non-halt states. Then you dont need a cut:

perform(0, Ls, Ls, Rs, Rs).
perform(s(Q0), Ls0, Ls, Rs0, Rs) :-
    symbol(Rs0, Sym, RsRest),
    rule(s(Q0), Sym, Q1, NewSym, Action),
    action(Action, Ls0, Ls1, [NewSym|RsRest], Rs1),
    perform(Q1, Ls1, Ls, Rs1, Rs).

But you could also show "Computational Completeness" by way of showing
that pure Prolog can do µ-recursion inside Peano numbers.