计算无处不在。

走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。

计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。

第一位发现这一点的,便是图灵。

计算的极限》系列

矛盾的自我指涉

在现实中,证明某种东西不存在是非常困难的。要证明某种东西存在,只要举出一个例子就可以了;但要证明某种东西不存在,就要想办法排除所有的可能性,而在现实生活中,这几乎是不可能的。所以,只要能排除那些比较主要的可能性,任务就算完成。但在数学中,情况大不相同:通过形式逻辑的方法,我们可以确实地证明某种数学对象不存在。这都要归功于数学那彻底的抽象化和形式化。

数学家在证明某个数学对象不存在的时候,经常会来一招“欲擒故纵”:首先假设它存在,那么它必然具有某些特定的性质,再利用这些性质,用严密的逻辑推理引出一个不可能的结论。既然结论是不可能的,而逻辑推理又没有问题,那么一定是推理的出发点出了差错:作为推理基础的那个东西,其实并不存在。这种证明方法,就是反证法。

现在,我们尝试用反证法证明停机问题是不可计算的。

按照反证法的格式,我们先反其道而行之,假设停机问题是可以计算的。根据定义,这说明存在一台图灵机P,使得向它输入某个图灵机M的状态转移表编码,以及初始输入I,图灵机P就能在有限步运算内,判断出机器M在输入I上是否会停止。

接下来,我们将要用图灵机P构造一个逻辑上不可能存在的结构,这将是证明的关键。

我们来考虑一个新的图灵机R,它的输入是某个图灵机M的状态转移表编码<M>。图灵机R先“调用”图灵机P,判断图灵机M在初始输入<M>上是否会停止。用现代的计算机语言来说,就相当于调用函数P(<M>,<M>)。如果图灵机P得出的结论是机器M在输入<M>上会停止的话,图灵机R接下来就会进入死循环;否则,如果机器M在输入<M>上不会停机的话,图灵机R就停止。

图灵机R的构造有两个奇怪之处。

首先,在图灵机R的运作中,它尝试判断一台图灵机M在它自身的编码<M>上的运作情况。此时,图灵机M不仅是程序,同时也是数据。这提醒我们,其实程序和数据没有实质的区别。程序只是一种特殊的数据,能够被分析、整理、改写。

事实上,我们每天都在使用处理程序的程序。比如说杀毒软件,其实就是一种扫描程序的程序。它检查每个程序的内容,判断程序中有没有威胁计算机安全的恶意代码。用杀毒软件扫描它自身,实际上就是让这个程序运作在它自身的代码之上。我们也可以用记事本打开记事本的程序本身,或者用压缩软件打一个包含它程序本身的压缩包。这些例子都说明了一个道理:程序就是一种数据。正因为程序就是数据,我们才得以完成图灵机的自我指涉。

其次,在图灵机R的构造中,如果M在输入<M>上停机,那么R就不停机;如果M在输入<M>上不停机,那么R就停机。这就是说谎者悖论的翻版:它的行为要与自己的判断相悖。

这样,我们就凑齐了说谎者悖论的两个要素:自我指涉和自我否定。剩下的,就是如何将这两个要素组合在一起,引出不可调和的矛盾了。

为了引出矛盾,我们来考虑图灵机R在自己的编码<R>上的运行情况。

如果R在<R>上停机的话,R必定没有进入死循环。所以,在调用图灵机P时,得到的必然是“图灵机R在输入<R>上不会停机”,才能避免死循环。但图灵机P的这个结论不符合我们的假设,出现了逻辑矛盾,所以R不可能在<R>上停机。

如果R在<R>上不停机的话,因为图灵机P必定在有限时间内完成计算,所以R必定进入了死循环。而R进入死循环的先决条件是,在调用图灵机P时,得到的是“图灵机R在输入<R>上停机”。而图灵机P的这个结论,同样不符合我们的假设。由于同样的逻辑矛盾,R同样不可能在<R>上不停机。

所以,根据严密的逻辑,我们构造的图灵机R在自己的编码<R>上,既不可能停机又不可能不停机,这是不可能的。另一方面,我们的逻辑推理也是没有问题的。尽管多么不情愿,剩下的可能性只有一种:我们假设的那个能完美解决停机问题的图灵机P,根本不存在!也就是说,停机问题是不可计算的。。

 

【感谢neko(@iNEKO_mini)提供图片】

这个结论,我们称之为停机定理。以上的论述,作为停机定理的证明远远不算严谨,还有很多细枝末节需要填充。但这些细节都是技术性的,并不妨碍主要的思想:矛盾的自我指涉。

停机定理的证明,一如哥德尔不完备性定理的证明,核心是化了妆的说谎者悖论。图灵机的能力如此强大,一台通用图灵机就可以完成一切图灵机的工作,将所有图灵机作为数据处理。也正因如此,图灵机不能解决某些牵涉它自身的问题,否则总会存在一些自我否定的“说谎者”,利用能解决牵涉自身问题的那些图灵机,完成被逻辑所禁止的,致命的自我指涉。图灵机的能力,在必然的逻辑推演下,同时也成了它的枷锁。

不可判定的重复

实际上,图灵一开始并没有证明停机定理。他证明的是:不存在这样的程序,能判断任意图灵机是否会至少打印出一个1。这里的“1”可以换成任意的符号。这个证明的方法要稍复杂些,不过本质上仍然是通过自我否定与自我指涉来制造悖论。而事实上,许多(但不是所有)有关图灵机的问题,都能用同样的方法被证明是不可计算的。这样,图灵手上就握有一套不可计算的问题,可以开始进攻希尔伯特的问题。

我们回顾一下希尔伯特的问题。哥德尔证明了,所谓的“一阶谓词演算”是完备的。也就是说,在这个数学系统中,每个真理都能被证明,“真”和“能被证明”这两个概念是一致的。希尔伯特的可判定性问题是:是否存在一种计算过程,可以在有限步运算内,判断在这个完备的数学系统中每个命题的真假?

一阶谓词演算作为数学系统,在能力上实在是比不上数学家们常用的逻辑系统:它连自然数都不能很好地定义。但图灵发现,这个稍弱的数学系统已经足以表达图灵机的运行过程。对于每个图灵机M,通过巧妙然而机械化的操作,图灵都能构造出一阶谓词演算中的一个命题U(M),使得U(M)成立当且仅当图灵机M会至少打印出一个1!也就是说,命题U(M)是否为真与图灵机M的运行过程息息相关。

剩下的证明就如同探囊取物了。如果希尔伯特的可判定性问题是可以计算的话,必定存在一台图灵机H,可以在有限时间内,判断每个命题的真假。对于一台图灵机M,我们要知道它是否会至少打印出一个1,可以先机械化地计算出与M有关的命题U(M),然后用图灵机H去判断U(M)的真假,从而判断图灵机M是否会至少打印出一个1。也就是说,利用图灵机H,我们可以用计算回答一个不可计算的问题,而这是不可能的。所以,图灵机H并不存在,希尔伯特的可判定性问题的答案只有三个字:不可能。

希尔伯特的期望,又一次化为泡影。逻辑弄人。

图灵确信自己解决了希尔伯特的判定问题后,很快将他的想法写成了论文,它的题目是:

论可计算数,及其在可判定性问题上的应用》(On Computable Numbers, With an Application to the Entscheidungsproblem)

他将论文交给了数理逻辑课的纽曼教授。这篇论文在纽曼教授的桌上放了几个星期。当教授终于有时间细读图灵的论文时,一开始根本不敢相信希尔伯特的问题竟然能通过对如此简单的机器的论证而解决,但无懈可击的逻辑论证最终战胜了怀疑。这无疑是划时代的工作,最终埋葬了希尔伯特的宏伟计划。

但正当纽曼教授联系各方,想办法发表图灵的论文时,从大西洋彼岸的普林斯顿,寄来了一篇论文:

初等数论中的一个不可解问题》(An unsolvable problem of elementary number theory)

它的作者是丘奇(Alonzo Church),普林斯顿大学的一位年轻数学教授,当时在数理逻辑这一领域已经小有名气。而这篇文章的最后一句话是:

In particular, if the system of Principia Mathematica be ω-consistent, its Entscheidungsproblem is unsolvable.
(特别地,如果《数学原理》中的系统是ω-一致的话,它的可判定性问题是不可解的。)

对于图灵来说,这绝对不是一个好消息,因为这正是他的结果。

那么,丘奇又是如何得到这个结论的呢?

0
相关文章

35 Responses to “计算的极限(二):自我指涉与不可判定”

  1. ChanneW说道:

    杀!
    长期关注,静待下文。

  2. 卓克说道:

    不知道这篇是否和前面有关,提个意见,应该在文章第一段描述和定义下什么是【停机】

    • fwjmath说道:

      请参阅文章开头《计算的极限》系列链接中的文章《计算的极限(一)》。

  3. 卓克说道:

    有个建议,文章第一段中应该定义好【停机】的概念

  4. tl说道:

    作者用很简单的语言,解释了计算理论里面一个很核心的问题。赞!

  5. cyler123说道:

    看到丘奇,我想到lambda验算了

  6. cyler123说道:

    wiki的停机问题页面有一句“停机问题本质是一阶逻辑的不自洽性和不完备性,类似的命题有理发师悖论、全能悖论等。”

    这里我糊涂了。。。。

  7. jjx874说道:

    作者想用计算机的相关语言包装一下“万能的上帝能否造出一块自己举不起来的石头”的故事,可惜反证法用得不够严谨……

    》尽管多么不情愿,剩下的可能性只有一种:我们假设的那个能完美解决停机问题的图灵机P,根本不存在!也就是说,停机问题是不可计算的。

    可能性2:调用图灵机P的图灵机R不存在
    可能性3:R不能调用自身的编码

    • wb说道:

      数学里解决集合论悖论时用到的手段就是通过限制自指的范围来使集合论顺利进行,但在这里你说的可能性2、3等只是不可计算问题可能的原因之一,反证法还是严谨的。

    • fwjmath说道:

      可能性2不存在,因为可以显式地从图灵机P构造图灵机R。
      可能性3不存在,因为没有理由R不能接受输入,因为根据定义,P显然可以接受。

      这些都只是技术细节,在叙述过程中被适当地简化了。有疑问的读者应该可以自己轻易地填补这些细节。

      • jjx874说道:

        对于可能性2 我没看到到任何“显式”的证明,要是能构造出R,那么,请给出R的编码。
        对于可能性3 “有理由”R不能接受输入,理由是:建立在此之上的反证法推出了一个矛盾。

        最后,这个不是技术“细节”,而是“关键”,整个证明的关键在于构造图灵机R,但恰恰对于构造的可能性没有证明。

        我的疑问来自于我看这个证明的漏洞,补漏的事儿是作者和编辑去干的,而不是找出漏洞的人去干。

        • cyler123说道:

          这个证明不是编辑做的,编辑是转述给不懂这个学科的一般人听的。一般人有两种选择,1、相信他(毕竟逻辑上是通的),2、找一下原始证明来看,读懂它。PS:如果你推翻了原始证明,恭喜你,你要发达了!

        • cyler123说道:

          另外,明显你不知道函数式编程和lambda演算。没事,这篇文章的后即就要讲丘奇和lambda演算了。

        • stecue说道:

          对于2,证明过程就是构造R的过程啊。构造R的唯一障碍就在于P。R只不过是P的简单调用。如果P存在而无法被调用,不就等价于P不存在么。

        • Naima说道:

          Deep thinking - adds a new diinsemon to it all.

    • stecue说道:

      可能性3的限制是你自己加上去的。根据R的构造,R的输入仅仅受限于P。只要P可以接受作为输入,R当然可以接受作为输入。P如果不能接受,也就说明不存在针对所有停机问题的算法。

  8. zero28说道:

    如果P不是确定的,是根据输入M构造的,即是P=F(M)而由于图灵机的种类是无限的,而因此有可能不能找到一个图灵机输入X使X=F(X),这样会怎么样。用自我指涉破自我指涉?求找BUG

    • stecue说道:

      没看懂,你证明了构造不出P不就是说停机问题没有通用算法么。

  9. 高级诈骗师说道:

    完全看不懂。我想这个领域已经不在科普范畴之内了,看懂的估计都是专业人士,非专业人士想看懂几乎没可能。

  10. codepiano说道:

    还是觉得刘未鹏那篇写的好

  11. 杰楠说道:

    自己做点击就自动解压的压缩包,解压后在可以运行一个文件,那个文件就解压是自己,结果解压好东西后他又运行自己再解压,无限循环了,这么玩过同学,最后只能强关电脑。。

  12. 我是马甲说道:

    如果图灵机P得出的结论是机器M在输入上会停止的话,图灵机R接下来就会进入死循环;否则,如果机器M在输入上不会停机的话,图灵机R就停止。

    关于这个,求白话解释。。。。

    • Illusiwind说道:

      我用正常人类的语言解释下吧。
      首先有三个图灵机,M P R,其中P是我们假定存在的那个“可以判定任何一个图灵机在给定输入的情况下是否会停机”的图灵机。M是任意一个图灵机,那么当然P就可以判断M里边输入给定数据是否会停机。当然给定数据包括M本身,所以P可以判定M输入自己是否会停机。R是另一个图灵机,它里边调用了P,并且当P的结果是 停机 的时候它就死循环,当P的结果是死循环的时候它就停机——这就是它的功能。
      现在我们在R里输入它自己,R。那么此时R会先调用P判定这一过程是否会停机。如果P说它会停机,那按照R的功能,R就会死循环——与P的判断矛盾。如果P说它会死循环,那R就会停机——照样矛盾。所以不存在这样的P。证毕▊
      这个要是还看不懂就没办法了。

      • 快乐的帅驴子说道:

        R唯一的功能就是在判断停机时死循环,在判断不停机的时候停机?它死循环的时候处理的是什么?

        • 黄某某说道:

          同问,死循环的时候做啥?

          • Idddd说道:

            死循环不做任何处理,就是死循环

            M: 要被判断的图灵机,可以为任意图灵机

            P:假设的可以判断任意图灵机是否停机的图灵机

            R: 构造的新机器,用于推出矛盾
            R 的结构如下:
            输入参数:M
            结果=用P 判断 M
            如果 结果=停机
            死循环
            否则 (也就是 结果=不停机)
            停机

            用R判断R本身,即可播出矛盾

          • Eduardo说道:

            That's way more clever than I was exgntciep. Thanks!

  13. Illusiwind说道:

    擦,要上λ演算了么?

  14. 快乐的帅驴子说道:

    为什么判断停机就会死循环?

    • Idddd说道:

      进入死循环,是人为构造的

    • Iddddddd说道:

      while(true)
      {}
      这个死循环是人为故意弄的,目的就是整那台机器

    • 秋云说道:

      因为不能调用下一个状态只能在本状态陷进死循环吧,貌似跟操作系统中断原理很像

  15. 不好说说道:

    事实胜于雄辩,不如设计一个模型 模拟一下。

  16. 右京样一说道:

    “用现代的计算机语言来说,就相当于调用函数P(,)。”
    这里错了吧,应该是相当于调用P(M, )?