prolog - 是纯Prolog Turing-complete，如果是，为什么不能实现列表交集？

Question

The Wikipedia section on this topic是一个烂摊子。它指出:

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:

(强调)
然后它继续显示使用非 Horn 子句( ! 和 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).

好的，所以 Prolog 是图灵完备的。没有人怀疑这一点。纯 Prolog 怎么样？
如果纯 Prolog 实际上是图灵完备的，那么如何 we seemingly can't implement list intersection (按第二个列表中的成员资格过滤的第一个列表)在其中？所有实现至少使用以下之一: ! , \+ , findall , call直接或间接。

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.

请注意 answer using if_/3 根本不需要任何切割。切割(或 if-then-else)只是出于性能和健壮性的原因(即捕获确定的情况并在意外使用的情况下发出错误信号)。您可以将其全部扩展为没有任何此类结构的版本。它将以相同的方式终止，但在当前实现中效率较低。
以下是 if_/3 的纯化版本和 (=)/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).

并且，如果您不接受 call/2和 call/1 (毕竟两者都不是一阶逻辑的一部分)，您必须相应地扩展每次使用。换句话说， if_/3 的所有用途是这样的，这样的扩展是可能的。
至于图灵完备性，这已经使用 建立起来了。单规则 .见 this question以及其中包含的引用资料这是如何可能的(这真的不是那么直观)。