分享

如何通俗地解释停机问题(Halting Problem)?

 pgl147258 2014-06-25

本人数学和编程都不是太好。

苏椰的回答(22票)】

感谢邀请。通俗地说,图灵当年想要证明希尔伯特的可判定性问题,也就是说,是否存在一种通用的机械过程,能够判定任何数学命题的真假。于是图灵就设计了一种假想的机器,也就是图灵机。他首先证明,图灵机就覆盖了所有的“机械过程”,如果存在一个问题,图灵机判定不了,那么就说明,不存在这种“通用的”过程,这样就证明了原问题。

然后,图灵就设计了一个问题,确实是图灵机判定不了的,这个问题就是:对于一个输入,让图灵机判定自己是否能够在有限的时间内停下来。

图灵证明,这个问题是图灵机回答不了的,所以原问题得以证否。至此,希尔伯特的三大问题,全部得到了证否(前两个是由哥德尔证否的)。因为这个问题设计得非常巧妙,所以在历史上留下了名字,叫“停机问题”。

顺便说一下,图灵当时设计这个图灵机,完全只是为了辅助他证明这个问题而已,这个机器是假想的,不存在的,就像画一条辅助线。可是后来他又发现,虽然这个机器不能解决所有的问题,但确实能够解决很多问题,而且真的是可以造出来的。于是……

图灵就成为了“计算机科学之父”。

【paradisor的回答(8票)】

有幸受邀,诚惶诚恐。

停机问题描述起来还是很简单的:正如@陳浩 所引,问题是对于某程序P,给出某输入I,求解此程序P是否会到达终止状态。

停机问题无解的证明也是很简单的,稍受过训练的人就该想到,这里面存在“自指”问题。证明就是构造反例即可:如果存在一个判断停机问题的程序H(H需要的输入是一个程序),我们再构造一个新的程序K,这个程序调用H但是与H的输出正好相反:如果K的输入经H判断为停机,则K不停机;如果K的输入经H判断为不停机,则K停机。现在矛盾出现了:如果我们把K输入K(即用H判断对于程序K,给出输入为K),那么K停机么?如果按逻辑推演,答案应该是:如果K不停机则K停机;如果K停机则K不停机。矛盾出现了。唯一解决矛盾的解释是:不存在这样万能的H。

停机问题和说谎者悖论/理发师悖论是一脉相承的,说谎者/理发师悖论归根结底是定义了一个集合S={a|a is not in a}。补上这个漏洞的唯一方法是拒绝集合的自指。同样停机问题也说明了,不存在一个判定一切程序的程序,因为这个程序本身也是程序。

可能会有人联想到哥德尔不完备性定理,哥德尔不完备性定理是很复杂的问题,我不敢说太多。但是我个人认为停机问题和哥德尔不完备定理是本质类似的。哥德尔不完备定理的核心是:包含“可数无穷”概念的公理系统里面存在不能证真也不能证伪的命题,证明也是非常类似地构造了一个“声称不可自证”的命题,然后问这个命题本身是否可自证。

停机问题的“现实”意义是说明了程序不是无所不能的,说实话这不算多大的意义,因为正常人都不会觉得编程万能(画外音:死程拯救世界!)。如果说它在数学上的理论意义,个人认为停机问题不存在超越集合论内容的意义。如果真有人想较真停机问题(画外音:死宅拯救世界!!!),请先从集合论学起。

近日睡眠不足,临键盘乱按,不知所言:-)

【谢然的回答(1票)】

关于此问题,请看Matrix67大牛的文章

http://www.matrix67.com/blog/archives/901 

看完你一定会理解的

原文地址:知乎

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多