《停机问题(详解)》由会员分享，可在线阅读，更多相关《停机问题(详解)（7页珍藏版）》请在金锄头文库上搜索。
1、停机问题在课堂上，我已经说明了：语言和图灵机分别是不可数集合和可数集合， 因此，图灵机（计算机）不是万能的。接着，我又用“停机问题”作为 具体例子强化了我们对图灵机不是万能的理解。但是，“停机问题”远 不止是为“图灵机不是万能的”这一论断提供了一个具体的例子，它也 为许多关于形式系统的定理提供了例子。在公理系统一文中，我提到了哥德尔的“不完备性定理”，即：一个形 式系统，如果是一致的（=相容的=无矛盾的），那么，就一定存在一个 命题，这个命题在该系统中不能被证明，也不能被否证。换一种说法， 这个命题在该系统中不能被证明，它的反命题在该系统中也不能被证 明。哥德尔是个天才，他的贡献还不止是这个定
2、理，这个定理被称之为“哥 德尔第一定理”。更进一步，还有一个“哥德尔第二定理”，即：任何一个被认为是一致的系统，它的一致性是不能在系统内部得到证明的。理。我的理解，他是在说：世界是不可知的。或者，世界就没有“真理”这件事。一个系统 的一致性不能在这个系统内部证明，那应该怎么知道系统是一致的呢？ 因为，没有一致性，逻辑就破产了。你会说：“既然一个系统的一致性 不能在该系统内部得到证明，我可以通过另一个已经被证明是一致性的 系统来证明这个系统的一致性，就好比你自己无法证明自己是好人，但 是，你可以通过另外一个好人来证明你是好人啊。”明眼人一看就知 道这是很无谓的循环，请问：这“另一个已经被证明是一
3、致性的系统” 的一致性是如何得到证明的呢？如果你回答说：“它的一致性是通过其 它的已经被证明是一致性的系统来证明。”那我继续追问：其它的系 统的一致性又是怎么被证明的呢？你继续回答，我可以同样继续追问， 会有结果吗？类似地，你也无法通过另一个所谓“好人”来证明你是一 个好人，因为，逻辑上，另一个人要证明他自己是好人的话，他遇到的 问题与你没有区别，也是如此无限循环下去的。难道说，世界上就没有一致性的系统吗？事实是：不知道！我们假设我 们有，所有的证明通过上述追问最终都归结到了假设，或者公理，通过 首先承认这些公理的不言自明之正确性，我们才逐渐发展出我们自以为“严密的”逻辑。同样，通过承认“政府
4、”、“嘻嘻TV”、“人民大众” 或“某个人”是好的，才能“证明”你是好人。当然“政府、嘻嘻TV、 人民大众或某个人是好的”也完全是假设。If这样的不断追问和思考你能发现什么？你会发现：科学本身建立的基础 是靠不住的，因为公理（假设）是靠不住的，科学历史上这样的事情屡 次发生：牛顿理论的困境、宇称守恒定理的破产.。类似地，好人 也是靠不住的，因为，政府、嘻嘻TV甚至人民大众的正确性是靠不住 的。人类历史上这样的事也是屡屡发生：政府的无义，苏格拉底被人民大众投票处死也难怪波普尔在猜想与反驳一书中定义：科学命题是“可证伪”而 不是“可证实”的东西。比如，“世界上所有的人都是白人”是科学命题，因为，我
5、们能证伪它，世界上有些人不是白人。“人都是要是死的”也是科学命题，因为它的反说法是：“有些人是长生不老的”，这很容 易被证伪。可是，“上帝是万能的”不是科学命题，因为，我问：“上 帝能不能制造出一块他自己搬不动的石头？”你能怎么回答呢？既然 这样，“上帝不是万能的”应该就是科学命题了喽？也不是，因为你也 没法证伪这句话，原因是我们谁也没见过上帝，因此，既没有实例也没 有进一步的无矛盾的逻辑公理作为出发点去证伪“上帝不是万能的”。 这是悖论，悖论不是科学命题。其实，“上帝问题”是一个宗教信仰问 题，在宗教世界里，“上帝是万能的”本身被当作公理，不言自明，必 须承认这一点才有资格成为信徒。有意思的
6、是:神学理论里，就是在“上 帝是万能的”这样一个“公理”的基础上逻辑得出其他论断的。如果你 承认了“上帝是存在的而且是万能的”这个“公理”，那么神学中的其 他逻辑结论也都是有理有据的，你不得不信。但是，如果你不承认这个“公理”，你还能相信宗教世界里的其他逻辑结论吗？“上帝是否万能？”、甚至“上帝是否存在？”是不可证的，在信徒眼 里，对“上帝是否存在”的证明本身就是对上帝的亵渎。在信徒们眼里， 上帝是存在的，但他的存在不能被我们非信徒感知、也不能被证明，只 能存在于人的精神创造中。既然上帝是人创造出来的（而且是精神产品、 不是实物产品），他的存在就是可有可无的了，也难怪有人信，有人不 信。仔细想
7、想，我们也很幸运，因为，世界是多样的，世界上除了科学 逻辑，还有宗教、艺术、文学、心理学等等，因此，我们才能共同生存 在一起，也才有人坚信好人的存在。女人凭直觉判断，男人凭逻辑判断。 直觉上看，可以相信有些人是好人，但是，前面已经说过了，逻辑上看， 却无法知道世界上有没有好人，因此，凭科学逻辑生活的男人很痛苦！ 女人不是完全不讲逻辑，因而才不至于胡说八道，男人也不是完全没有 直觉，因而才不至于痛不欲生。为什么说是“证伪”而不是“证明”或“证实”呢？简单点说，是因为 在逻辑上和实践中，“证伪”比“证实”更让人安心。习惯上，我们仍 然将“证明”一词挂在嘴边，谢天谢地，我们能“证明”什么？谁知道 呢
8、，就这么稀里糊涂的证明下去吧。如果不让哥德尔第二定理将我们引向不可知论或虚无主义，他也至少告 诉了我们：没有完美的和无所不能的东西。因此，“停机问题”的出现 就很自然了。不论有多少种不同的“停机问题”表述形式，通俗地说就是：“有没有 能判断自己是否停机的图灵机？”答案在课堂上都讲过了：不存在这 样的图灵机。如果有这样的图灵机存在，那么也就意味着有人在睡着的 时候对你说：“我现在睡着了”。你在睡着的时候能告诉我说你自己睡 着了吗？如果是，那我要祝贺你，妖怪！非形式化证明“停机问题是不可判定的”。停机问题：任给一个程序f和一个输入*，是否存在一个判断程序P能判断f对x的计算是 否停止？证明：假定停
9、机问题是可判定的，则存在一个判断程序P能判断任意程序f对输入x计算是 否停止。P(f,x)=true，当f对x计算停止。P(f,x)=false，当f对x计算不停止。再定义一个新程序P1P1(f,x)=while(P(f,x);当f=P 1时(既然P可以判断任何程序是否停机，对P1当然也可以判断)P1(f,x)=P(f,x)当 f!=P 1 时现在讨论P1对任意输入x是否停机：1、若P1停机则P(P1,x)=true，根据P1的定义P1(P1,x)=while(P(P1,x)显然P1是不停机 的，因此得到矛盾。2、若 P1 不停机则 P(P1,x)=false，根据 P1 的定义 P1(P1,x)=while(P(P1,x)；显然 P1 会停 机，也得到矛盾。结论：能判断任意程序对任意输入的判断程序是不存在的。也就是“停机问题是”不可判定的。
