问题描述
关于这个主题的维基百科部分是一团糟.它指出:
Pure Prolog 基于图灵完备的一阶谓词逻辑 Horn 子句的子集.Prolog的图灵完备性可以通过模拟图灵机来展示:
(强调)
然后它继续显示使用非 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.
推荐答案
请注意，使用 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 图灵完备，如果是，为什么不能实现列表交集?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！