终於觉得自己比较有时间可以回文了。 :) 首先 halting problem 是什麽，我就不赘述了，因为我不想要把课本一整章抄上来， 而且我也没自信把问题的描述简化以後，原本不懂的人还看得懂，这样的简化没意义。 为了要保持描述的流畅性，下面写的可能会把几个相似但不同的概念混用， 专有名词的使用上面可能会比较不精确，有兴趣的人可以再查书来分别这些名词。 简单来说， Turing 那个时代的数学家们在思考的问题是「计算」到底是什麽。 这当然是一个定义问题，当时 Turing 试着对「计算」作定义，他的定义是， 他设计了一个假想的「计算模型」，也就是广为人知的 Turing machine ， 然後他定义 Turing machine 的运算过程就是「计算」。在有了定义以後， 下一个要问的问题当然是，那 Turing machine 到底「多能算」，也就是说， Turing machine 能够解决的问题到底包含哪些范围。 Turing machine 虽然是一个假想的计算模型，但它其实非常强大。一般的问题难不倒它， 因此 Turing 为了证明 Turing machine 也有它的极限，特意去找算不出来的问题， 这边所谓的算不出来，或说无法回答，或说 undecidable ，就是没有任何一个演算法， 可以在任意给定一组输入值的情况下，决定这个问题是 Yes 还是 No 。 而 Turing 找的问题就是 halting problem ，这个问题的输入是「任意一个程式」加上 「该程式的任意一组输入值」，而要回答的问题是这个程式搭配这个输入值会不会停。 略过证明过程，总之 Turing 证明了不可能设计出一套演算法来解决这个问题。 因为 halting problem 是要问 Turing machine 的计算极限，而不是问人的极限， 所以在考虑 halting problem 的时候，去问人能不能用直觉去判断云云， 基本上不是 halting problem 的重点。而且就算使用者可以强迫程式终止， 但 halting problem 要能解，必须要是「任意输入值」该演算法都能回答， 当然也就包括「使用者不强迫终止」的这种输入状态。只要有一个 case 不能解， 那麽整个 halting problem 就是不能解。当然靠经验去预估计算时间， 超过预估的时间就终止等等，这也都没回答到问题，因为 halting problem 要问的， 不是「这个程式应不应该会停」，而是「这个程式在这组输入下会不会停」。 Turing 等人所关心的问题，其实根本不是特定的程式会不会停， 当然他们也不在意真的掉到无穷回圈的时候应该要怎麽跳出来， 也不那麽在意怎麽样写程式才不会掉到无穷回圈里面。 另外要补充的是，事实上我们现在所使用的电脑，都不满足 Turing machine 的需求。 因为 Turing machine 假设具有无限长的 Tape ，或说无限大的记忆体。 但现在的电脑的记忆体都是有限的。 所以虽然没有一个演算法可以判断： 「一个程式搭配一组输入值在 Turing machine 执行会不会停？」 但是其实存在一个演算法可以判断： 「一个程式搭配一组输入值在记忆体有限的电脑上执行会不会停？」 所以回到 dharma 板友一开始问的问题，演算法之道所写的到底对不对。 其实我不知道，因为如果我们不把 halting problem 摆在 Turing machine 上问， 而是把 halting problem 摆在一个给定记忆体大小的电脑上来问， 那其实我们可以判定程式会不会终结。但即使如此，程式就能全自动吗？我不知道。 而反过来说，虽然强如 Turing machine 的机器都有它的极限， 无法回答所有的问题。但「人」同样也有自身的极限，也有很多问题不能回答。 似乎也没有理由说明不能解 halting problem ，就不可能程式自己来写程式， 或是不可能像骇客任务那样，或者程式设计永远离不开程式设计师。 -- 活着的目的是为主活 然後为主死 死亡的目的是为主死 然後为主活 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.224.213.10 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/ask-why/M.1425304225.A.882.html