一个无限的成功树，或者不是? [英] An infinite success tree, or not?

问题描述

我得到了以下程序:

edge(a,b).
edge(b,c).
edge(a,d).

path(N,M):- path(N,New),edge(New,M).
path(N,M):- edge(N,M).

并询问是否将证明树算法应用于以下查询:

And asked if when applying a proof tree algorithm to the following query:

?- path(a,X). 

证明树是无限成功树，还是无限失败树?

the proof tree is an infinite success tree, or an infinite failure tree?

现在，在我看来，在构建树的过程中，您会陷入一遍又一遍地应用路径规则 1，创建一棵无限树并且永远不会达到路径规则 2..

Now as I see it, during the building of the tree, you get stuck in applying rule 1 of path over and over again, creating an infinite tree and never getting to rule 2 of path..

从而创建一个无限的故障树.但是我的解决方案说它是一个无限的成功树，我的问题是:我是对的还是我的教授是对的?:]

thus creating an infinite failure tree. but the solution I have says it is an infinite success tree, my question is: am I right or is my professor right? :]

推荐答案

我称之为无限循环.看轨迹:

I would call that an infinite loop. Look at the trace:

?- trace, path(a,X).
Call: (7) path(a, _G394) ? 
Call: (8) path(a, _G511) ? 
Call: (9) path(a, _G511) ? 
Call: (10) path(a, _G511) ? 
...
Call: (147) path(a, _G511) ? 
Call: (148) path(a, _G511) ? 
...
ERROR: Out of local stack

我不熟悉这些术语，但我可能会有所了解.没有产生解决方案，所以我很难说这是一个无限的成功树.即使给定无限的时间和空间，它也永远不会产生成功的解决方案.同时，Prolog 意义上的失败是立竿见影的，而且也不会发生.我不确定是否存在无限失败树这样的东西，除非您将其称为生成无限数量选择点的东西，但所有选择点都失败了.但这里没有任何失败.将其称为真正的含义会更诚实:无限循环.这样的事情存在于成功和失败的领域之外.这就是为什么在 Haskell 中， ⊥ 属于所有类型.也许从这个意义上说你们都是对的.

I'm not familiar with these terms, but I might be able to wing it. No solutions are produced, so it would be hard for me to argue that this is an infinite success tree. Even given infinite time and space it would never produce a successful solution. At the same time, failure in the Prolog sense is immediate, and that isn't happening either. I'm not sure such a thing as an infinite failure tree could exist, unless you'd call that something that generates an infinite number of choice points, all of which fail. But there aren't any failures here. It would be more honest to just call this what it really is: an infinite loop. Such things exist outside the realm of success and failure. This is why in Haskell, ⊥ belongs to every type. Maybe in that sense you're both right.

这篇关于一个无限的成功树，或者不是?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！