recursion - 如果您不调用它本身，是否可以创建一个停止函数？

Question

无法解决停机问题的标准证明通常是这样的

//does_halt() takes a function as input and returns true if it will ever finish computing

function paradox()
    {if does_halt(paradox())
        {
          while(true){}
        }
    }        

这个证明要求你递归地调用暂停函数，但是有没有可能制作一个暂停函数，只要它不被自己调用就总是计算出正确的结果？

Answer 1

该证明不需要递归。你没有捕获重点!您不调用 paradox，而是像高阶函数一样传递它。在Scheme中使用这个函数及其用法:

;; does operation passed as x to 2 and 5
(define (do2by5 x)
  (x 2 5))

;; examples    
(do2by5 +)    ; ==> 7
(do2by5 *)    ; ==> 10
(do2by5 expt) ; ==> 32

如你所见，我没有申请 + , *或 expt在我的例子中。我只是将它作为参数传递。它是 do2by5使用它。在您的悖论中，自从您添加 () 以来，您似乎将其称为悖论。到名字。这是错误的，因为 does_halt应该像我的 do2by5 一样采用函数参数.这是我在 Scheme 中编写它的方式:

;; this procedure does not halt!
(define (forever)
  (forever))

(define (paradox x)
 (if (halt? paradox) ; see I'm not calling it but passing it
     (forever)
     'im-finished))

现在真正的果汁当然是 halt?当然不可能实现和 paradox是你不能做这样的功能的证明。

停止问题 tvivia:
许多人不明白的是，您实际上可以制作 halt?对于生活在有限大小内存中的有限大小代码，如果您必须调查的资源合理地大于可以容纳分析程序的最小机器。例如。作为一个例子，这里是一个所有 3 字节的 BrainFuck 程序，它被简化为只有图灵完备(例如，没有 , 和 .):

(define (bf3halt? x)
  (not (member x '("+[]" "-[]"))))

对于更大的示例，您可以在虚拟环境中运行程序散列内存状态和程序计数器。如果您再次遇到相同的内存和程序计数器，您将陷入无限循环并且可能返回 false。 (现在你看到 halt? 的内存需求可以达到 code size 的参数乘以运行时参数的内存消耗)