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