※ 引述《dharma (达)》之铭言： : 演算法之道里写道： : ...无法判定程式终结，这个结论对程式设计来说意义重大。就是这个缘故，程式永远不 : 会是全自动的，即不可能由程式自己来写程式、启动程式、控制程式。也就是说，像「骇 : 客任务」那样的情景永远也不会出现。而隐含的意义是程式设计永远也离不开程式设计师 : 。... : 书上这个论点 : 是现在学术和产业界的共识吗？ : 是不是只有人类开发出仿生脑 : 才会有真正的人工智慧 : thank 停机问题（halting problem）是计算理论中最基本的常识。 首先，理论上我们简单将程式分类成 1. 若存在某个演算法，对给定的问题如果有解， 可以在有限时间内给出答案，称为「可计算」 computable (或是 semi-decidable） 2. 另一方面，不只是有解的情况，若是没有解也可以在有限时间内回答， 则称为「可判定」 decidable。 而 halting problem 的问题是：给定任意程式 P ，断定它是否会停止。 很明显的这是可计算的问题，因为只要去执行 P ， 若 P 在有限时间内结束，可以 P 在有限时间内得到答案。 但这个解法并不能在有限时间内推断 P 「不会」结束。 （这边提到的程式并不包含有输入的程式。） 以上这个解法不成功，那是否存在另一个程式可以做到呢？也不行。 很久以前就已经有数学证明，不存在这样的程式或机器。 原文接下来的推论，我认为是过於粗糙简略了，按下不表。 不过呢，halting problem 讨论的是「所有可能的程式」， 但可以把问题缩小到一些比较简单能够判定程式， 有些程式语言甚至保证所有的程式都会终止，像是 Agda 或是理论上的语言 polymorphic lambda calculus。 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.162.4.165 ※ 文章网址: http://webptt.com/cn.aspx?n=bbs/Programming/M.1403603605.A.E4A.html