纯 Prolog 图灵完备，如果是，为什么不能实现列表交集? [英] Is pure Prolog Turing-complete, and if so, why can't it implement list intersection?

问题描述

关于这个主题的维基百科部分是一团糟.它指出:

Pure Prolog 基于图灵完备的一阶谓词逻辑 Horn 子句的子集.Prolog的图灵完备性可以通过模拟图灵机来展示:

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

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

好的，所以 Prolog 是图灵完备的.没有人怀疑这一点.纯 Prolog呢?

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

如果纯 Prolog 实际上是图灵完备的，那么 我们怎么可能'不实现列表交集(第二个列表中的成员过滤的第一个列表)吗?所有实现都至少使用以下之一:!、+、findall、call 直接或间接.

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.

推荐答案

为什么我们貌似无法实现列表交集(第一个列表按第二个列表中的成员资格过滤)在里面吗?所有实现都至少使用以下之一:!、+、findall、call 直接或间接.

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.

请注意，使用 if_/3 的答案根本不需要任何剪辑.剪切(或 if-then-else)仅出于性能和稳健性的原因(即捕获确定的情况并在意外使用的情况下发出错误信号).您可以将其全部扩展为没有任何此类结构的版本.它将以相同的方式终止，但在当前实现中效率较低.

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.

这里是 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 的所有使用都使得这样的扩展是可能的.

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.

至于图灵完备性，这已经使用单一规则建立.请参阅 this question 以及其中包含的参考资料，这是怎么可能的(这真的不是那么直观).

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

这篇关于纯 Prolog 图灵完备，如果是，为什么不能实现列表交集?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！