0

停止問題を実現する Haskel 関数が存在するとします。

halt :: Integer->Bool

x が定義されている場合は True に評価され、それ以外の場合は False に評価されます。

Haskell でこの関数を別の関数で呼び出していると仮定しましょう。

fHalt x = halt (x+1)

この状況で何が起こるのか、そして fHalt が単調な場合はどうなるのだろうかと思っています。私には2つの可能な答えが生じます：

  1. Haskell は、事前定義された演算子 (つまり、(+) に対しても) に対して厳密な評価を使用します。fHalt が現在 BOT で評価されている場合、私の推測では、BOT+1 を最初に評価する必要があり (BOT になります)、全体的な評価は終了せず、BOT になります。

  2. 何らかの形で Haskell が内部 (x+1) が終了しないと判断した場合 (これは停止問題のために不可能です)、結果は False になり、fHalt は単調性に違反します。

私の質問は、Haskell で定義された実現不可能な停止関数を既に暗示していたので、この時点でイライラしています。答え1.が正しいと思いますが。

4

2 に答える 2

6

The question's presupposition is, of course, false.

But we should at least be sure that

fHalt undefined = halt (undefined + 1)

just because we expect the beta-law to hold without exception.

Now, if this hypothetical halt existed, it should be able to detect that

undefined + 1 = undefined

shouldn't it? Of course, it wouldn't be Haskell which figures that out, but the magic in the halt function.

于 2014-08-13T08:08:15.003 に答える
0

Haskell は、事前定義された演算子 (つまり、(+) に対しても) に対して厳密な評価を使用します。

いいえ、一般的ではありません。ただし、特に実装+については厳密であり、さらに推論が機能します（もちろん、存在する誤った前提から始まるため、あまり役に立ちません）。Integerhalt

于 2014-08-13T08:11:34.693 に答える