Question

:-  p(f(X),f(f(Y)),f(f(b))).

p(f(a),f(X),f(f(X))).
p(f(a),f(a),f(f(X))).
p(X,f(f(Y)),X) :- p(Y,f(f(Y)),f(f(X))).
p(f(X),Y,Z) :- p(X,f(Y),f(f(Z))).

我认为,我有证据证明,他采用上岗培训,需要几个分门别类,其中一些是:

p(f(X),f(f(X)),f(f(b))) grows (i.e. does not halt) is a corollary from:

p( X, f^n(X), f^(n+1)(b) ) grows (i.e. does not halt)

p(f^k(b),f^l(b),f^m(b)) fails if 0 <= k < m.

p(f^k(b),f^l(b),f^k(b)) fails if l-k mod 3 = 0

where f^n(X) means n iterations: f(f(...f(X)...)).

我将努力完成举证,但想知道是否有更简单的非吸入证据。通过阻止我接受标准程序词典:对条款的先后顺序,(尽管在这种例子中不相关)对次级目标进行左对手执行。

Answer 1

In Prolog we talk usually about universal and existential termination. Universal termination being the more relevant. A goal G_0 terminates universally, iff G_0, false fails finitely. So let s consider the following failure-slice of your program:

:-  p(f(X),f(f(Y)),f(f(b))), false.

p(f(a),f(X),f(f(X))) :- false.
p(f(a),f(a),f(f(X))) :- false.
p(X,f(f(Y)),X) :- false, p(Y,f(f(Y)),f(f(X))).
p(f(X),Y,Z) :- p(X,f(Y),f(f(Z))), false.

If this failure slice does not terminate, then also the entire program does not terminate. This is one of the desirable properties of pure Prolog programs.

显然,<代码>Y和Z对终止都没有任何影响。两者(在这一失败的案例中)都是中性的终止。因此,如果方案受到约束(明确和地面),仍然首先导致终止方案。仅作一推,第一个<代码>f(X)被删除,一个(别名)变量仍保持不变。因此,这项方案(有问题)并不普遍终止。 iii

Now for existential termination. That is, while the program does not terminate universally it may still find a solution. Think of a query like

?- length(L,N).
   L = [], N = 0
;  L = [_A], N = 1
;  L = [_A,_B], N = 2
;  L = [_A,_B,_C], N = 3
;  ... .
?- length(L,N), false.
   loops.

which does not terminate universally, but still produces useful answers and thus terminates existentially.

传统的终止往往有捷径: 如果没有解决办法,方案不会普遍终止,那么,方案也不存在成因终止。这将是一场快枪! 这里的情况并非如此。一种解决办法是:

?- p(f(f(a)),f(f(b)),f(f(b))).
   true
;  false.

并且还有很多。因此,该方案是否将找到解决办法,仍然开放。

现在,这是一件奇怪的事情: 第3条没有目的(非终止除外)。我注意到这一点,增加了一个外围参数,使循环深化:

% p([n],_,_,_).
p([a],f(a),f(X),f(f(X))).
p([b],f(a),f(a),f(f(X))).
p([c|L],X,f(f(Y)),X) :- p(L,Y,f(f(Y)),f(f(X))).
p([d|L],f(X),Y,Z) :- p(L,X,f(Y),f(f(Z))).

?- length(L,N), p(L, A1,A2,f(f(b))).
   L = "a", N = 1, A1 = f(a), A2 = f(b)
;  L = "b", N = 1, A1 = f(a), A2 = f(a)
;  L = "da", N = 2, A1 = f(f(a)), A2 = f(f(b))
;  L = "db", N = 2, A1 = f(f(a)), A2 = a
;  L = "dda", N = 3, A1 = f(f(f(a))), A2 = f(f(f(b)))
;  L = "ddda", N = 4, A1 = f(f(f(f(a)))), A2 = f(f(f(f(b))))
;  L = "dddda", N = 5, A1 = f(f(f(f(f(a))))), A2 = f(f(f(f(f(b)))))
;  L = "ddddda", N = 6, A1 = f(f(f(f(f(f(a)))))), A2 = f(f(f(f(f(f(b))))))
;  L = "dddddda", N = 7, A1 = f(f(f(f(f(f(f(a))))))), A2 = f(f(f(f(f(f(f(b)))))))
;  ... .

So when using the third rule initially once, there are no solutions to be found, and the program will not terminate. Thus proving that this part will find no solutions is tantamount to proving that the goal p(X,f(f(X)),f(f(f(f(b))))) has no solution.

I have not done this part, but it seems that the argument can be narrowed down to the observation that the first argument will always be of the form f*a, but the second of the form f*b and thus there cannot be a solution.

友情链接