3

不可能解决停机问题的标准证明通常是这样的

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

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

这个证明要求您递归地调用停止函数，但是是否可以创建一个停止函数，只要它本身不被调用，它就总是计算正确的结果？

4

2 回答 2

2

该证明不需要递归。你错过了重点！你不叫悖论，而是像高阶函数一样传递它。在 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应该像 my 一样采用函数参数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 程序都被简化为仅图灵完备的程序（例如，没有,and .）：

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

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

于 2014-06-07T00:13:35.853 回答
0

当然可以，但是您必须记住，计算理论是理论性的，并且在无限和物理不可能的情况下起作用。

function paradox1() {
   if (does_halt(paradox2())
       return true;
   else
       return false;
}
function paradox2() {
   if (does_halt(paradox3())
       return true;
   else
       return false;
}
function paradox3() {
   if (does_halt(paradox4())
       return true;
   else
       return false;
}
function paradox4() {
   if (does_halt(paradox5())
       return true;
   else
       return false;
}
etc etc etc _infinitely_

这是一个有效的图灵机式程序，它更清楚地说明了如何不可能知道未来会无限发生什么。

于 2014-06-06T18:31:57.723 回答