Yes, you can implement a Turing machine without
dif/2. But you cannot even implement intersection or similar predicates.
Suppose we do extend pure Prolog (Horn FOL + CWA + UNA) with call/N, dif/2, and (=)/3, to be used in if_/3, would there still be gaps in its expressiveness, i.e. things that are trivial to define in, say, Scheme, but are much harder to state in such extended (almost pure) Prolog?
In particular, does such a Prolog allow manipulating Prolog lists about as conveniently as Scheme allows manipulating Scheme lists?
Edit: Assume Scheme without mutation, macros, continuations, laziness, streams, numbers, strings, vectors or characters. Just symbols, booleans and lists (trees).
Just symbol/1 and dif/2 are sufficient extensions of logically pure Prolog.
Proof:
This answer contains an evaluator for Scheme expressions, evil/2. It understands lambda and quote, and can be easily extended to handle built-in list procedures like list, car, cdr, etc. Aside from pure (Horn) Prolog, it uses only symbol/1 and dif/2. While it is an interpreter and will run slowly, its existence shows that the same list operations done by Scheme can be done in such almost pure Prolog. (I think symbol/1 wouldn't be needed either, if Scheme symbols were translated into symb(prolog_atom) instead of directly into prolog_symbol)
Edit
This extends evil/2 to handle if, #t and #f (represented by true and false):
evil(true, _, true).
evil(false, _, false).
evil([if, E1, E2, E3], Env, Val) :-
evil(E1, Env, false),
symbols(E2),
evil(E3, Env, Val).
evil([if, E1, E2, E3], Env, Val) :-
evil(E1, Env, V),
dif(V, false),
symbols(E3),
evil(E2, Env, Val).
This extends evil/2 to handle equalp. It's even more powerful than Scheme's eq* in that it will equate some closures too:
evil([equalp, E1, E2], Env, true) :-
evil(E1, Env, V),
evil(E2, Env, V).
evil([equalp, E1, E2], Env, false) :-
evil(E1, Env, V1),
evil(E2, Env, V2),
dif(V1, V2).