【提出问题和解决问题的人】

2012,图灵诞辰100周年,献给这位伟大的开拓者。

计算无处不在。

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

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

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

计算的极限》系列

一切从逻辑开始

1900年的巴黎,在世纪交替之际,希尔伯特提出了他著名的23个问题。其中第二个问题——算术系统的相容性——正是他那雄心勃勃的“希尔伯特计划”的最后一步。这位数学界的巨人,打算让整个数学体系矗立在一个坚实的地基上,一劳永逸地解决所有关于对数学可靠性的种种疑问。一切都为了回答三个问题:

数学是完备的吗?也就是说,面对那些正确的数学陈述,我们是否总能找出一个证明?数学真理是否总能被证明?

数学是一致的吗?也就是说,数学是否前后一致,不会得出某个数学陈述又对又不对的结论?数学是否没有内部矛盾?

数学是可判定的吗?也就是说,能够找到一种方法,仅仅通过机械化的计算,就能判定某个数学陈述是对是错?数学证明能否机械化?

希尔伯特明确提出这三个问题时,已是28年后的1928年。在这28年间,数学界在算术系统的相容性上没有多少进展。但希尔伯特没有等太久,仅仅三年后,哥德尔就得到了前两个问题的答案,尽管这个答案不是希尔伯特所希望看到的。

哥德尔的答案分两部分。

第一,任何包含了算术的数学系统都不可能同时拥有完备性和一致性,也就是说,如果一个数学系统包含了算术的话,要么它是自相矛盾的,要么存在一些命题,它们是真的,但我们却无法证明。这说明,希尔伯特的前两个问题不可能同时为真。在这里,“算术”有着精确的含义,就是皮亚诺公理,一组描述了自然数的公理。

第二,任何包含了算术的数学系统,如果它是一致的,那么我们不能在它的内部证明它本身的一致性。这说明,我们没有希望解决第二个问题。

这就是著名的哥德尔不完备性定理,与其说它回答了希尔伯特的前两个问题,不如说它阐述了为什么我们根本不可能解决这两个问题。

哥德尔的证明非常精巧。他先将所有的数学陈述和证明符号化,然后给每个符号串赋予一个数字,这个过程被称为哥德尔配数法。借助数学归纳法,我们可以建立针对所有自然数的陈述,而这样的陈述本身对应着一个数字,这个数字也符合陈述本身的要求。换言之,这个陈述陈述了它本身的性质。哥德尔正是通过这样魔法般的自指,完成了他的证明。这个证明之所以重要,是因为它第一次提供了一套完整的数学工具和方法,用于证明有关数学证明的不可能性。这本身就是数学的一次重大胜利,说明数学的力量强大得可以用纯粹逻辑的方法,证明它本身的力量是有界限的。在数学的领地上,有些东西我们不知道,也不可能知道。

希尔伯特的前两个问题已经解决,只剩下最后一个问题。然而,如果一个数学系统不完备的话,它显然不可能是可判定的,因为机械化的计算本身也可以看成一种证明,而在一个不完备的系统中,真理不总能被证明。所以,最后一个问题只对完备的数学系统有意义。

所幸,完备的数学系统是存在的。同样是哥德尔,他证明了所谓“一阶谓词演算”的逻辑系统是完备的,这被称为哥德尔完备性定理。一阶谓词演算是一个比较弱的逻辑系统,在其中我们甚至不能有效唯一地描述算术。比如说,自然数系统符合皮亚诺公理的一阶版本,但它并不是唯一的,还有无数种所谓“非标准模型”同样符合这套一阶系统。在一阶谓词演算中,对于一套公理系统,如果一个命题在所有的模型中都正确,那么必定可以形式地证明这个命题,这就是一阶谓词演算的完备性。在一阶谓词演算中,真理总能被证明。

在这个弱得多的逻辑系统中,我们有了完备性,真的命题必定可以被证明。那么,它是不是可判定的?我们能不能找到一种机械计算的方法,判定其中数学陈述的对错?数学称述的真假,是否可判定的?这个问题,就是希尔伯特的可判定性问题。

注:希望更深入了解哥德尔不完备性定理的读者,可以重温旧文《希尔伯特之梦,以及梦的破灭》

复杂的简单机器

在纽曼教授的数理逻辑课上,图灵第一次听到希尔伯特的可判定性问题以及哥德尔不完备性定理。那是1935年的春天,他刚刚完成在剑桥国王学院的四年本科学习,以优异的成绩被选为学院研究员,正准备在数学界大显身手,数理逻辑自然而然吸引了他的兴趣。图灵清楚地意识到,解决可判定性问题的关键,在于对“机械计算”的严格定义。考究希尔伯特的原意,这个词大概意味着“依照一定的有限的步骤,无需计算者的灵感就能完成的计算”,这在没有电子计算机的当时,算是相当有想象力又不失准确的定义。

但图灵的想法更为单纯。什么是“机械计算”?机械计算就是一台机器可以完成的计算,这就是图灵的回答。

用机器计算的想法并不新鲜。17世纪的莱布尼兹就曾设想过用机械计算来代替哲学家的思考,而19世纪的Charles Babbage和Ada Lovelace就设计出了功能强大的“分析机”,只可惜Babbage欠缺管理才能,这台超越了时代的机器始终没有完全造好。但图灵需要的机器,跟先驱设想的机器稍有不同。它必须足够简单,简单得显然能造出实物,也可以用一目了然的逻辑公式描述它的行为;它又必须足够复杂,有潜力完成任何机械能完成的计算。图灵要找的,是一种能产生极端复杂行为的简单机器。

这并非易事,但图灵做到了,据说这是他某次长跑过后,在某块草坪上发呆的成果。他设计了一类机器,然后定义“机械计算”为“这类机器可以完成的计算”。他设计的这类机器,正是日后以他名字命名的图灵机。

图灵机的示例。绿点指示处为当前状态,每条规则的4项分别是:当前位置读入的字符、当前位置写入的字符、纸带的移动方向、将要转移到的状态。

图灵机的结构非常简单,它由两部分组成:一个读写头,还有一条两边无限延长的纸带,纸带被划分为小格,每格中只能有0和1两种符号。读写头的限制则稍微宽松一些,虽然每次只能对着纸带上的一个格子,但它本身可以处于不同的状态,虽然状态的数目是有限的。在所有状态中,有一个特殊的“停机”状态,读写头一旦处于停机状态,就会停止运作;但如果读写头一直没有到达停机状态的话,它就会永远运转下去。

整台图灵机的秘密在于读写头的状态转移表,它指示着读写头的状态和当前读写头正对格子的符号如何变化。它只有一种非常简单的规则,就是“如果在状态A的读写头对着符号x,那么对当前格子写入符号y,将纸带左移一格/右移一格/保持不动,然后转移到状态B”。状态转移表就是由一系列这样的简单规则组成的。可以说,状态转移表就相当于图灵机的源代码。

实际上,我们平时笔算乘法的思维过程,跟一台图灵机的运转非常相似:在每个时刻,我们只将注意力集中在一个地方,根据已经读到的信息移动笔尖,在纸上写下符号;而指示我们写什么怎么写的,则是早已背好的九九乘法表,以及简单的加法。如果将一个笔算乘法的人看成一台图灵机,纸带就是用于记录的纸张,读写头就是这个人和他手上的笔,读写头的状态就是大脑的精神状态,而状态转移表则是笔算乘法的规则,包括九九表、列式的方法等等。这种模式似乎也适用于更复杂的机械计算任务。如此看来,图灵机虽然看起来简单,但它足以作为机械计算的定义。

既然图灵机如此简单,能不能将它“升级”,赋予更多的硬件和自由度,使它变得更强大呢?比如说,让它拥有多条纸带和对应的读写头,而纸带上也不再限定两种符号,而是三种四种甚至更多种符号?的确,放宽限制之后,在某种程度上,对于相同的任务我们能设计出更快的图灵机,但从本质上来说,“升级”后的图灵机能完成的任务,原来的图灵机也能完成,虽然也许会慢些。也就是说,这种“升级”在可计算性上并没有意义,放宽限制后的机器能计算的,原来的机器也能完成。既然计算能力没有质的变化,无论采取什么样的结构,用多少种符号,都无所谓。

图灵机的一大优点,就是它的简单。只要给出状态转移表,任何一个人都可以模拟一台图灵机的计算。对工程师而言,在现实中用机械建造一台图灵机也并非什么难事。对于程序员来说,写一个模拟图灵机的简单程序更是不在话下。但如此简单的机器,它又能做什么呢?它真的能充当“机械计算”的定义吗?

(未完待续)

0
为您推荐

15 Responses to “计算的极限(零):逻辑与图灵机”

  1. ttt说道:

    哥德尔的证明那一段,真的是看起来好牛逼,就是完全没理解

    • silverwzw说道:

      想看懂的话,可以查看刘未鹏大牛的“金色对角线”一文.......那是我唯一看到的相对通俗的语言而不是符号推演来推导哥德尔不完备定理的。

  2. 郑 然说道:

    通过这篇文章,依稀看到了“自指”的思想,或许如同当年第一次接触“函数”的思想一般,并未深刻体会其中的精妙,但却是姐作者之手,推开了一扇的新的大门。

  3. cy说道:

    啊~昨天还刚在guokr看到lz的一个神解释啊~期待下一节!

  4. cy说道:

    这个是原创么?
    标题是计算的极限——带learning的heuristic算法算这个范围么?

  5. 幻风说道:

    上边的哥德尔和图灵还行,下边的Hilbert怎么就剩了个image?……注明下好点吧。

  6. SillyDaddy说道:

    标题的“零”很亮!

  7. 朗晴星说道:

    -_-b,完全看不懂数学相关的文字,从初中开始数学就烂的不行的人飘过……

  8. darcyyang说道:

    之前Google的图灵机LOGO很不错~~~

  9. 神性复苏说道:

    图灵机,一个由无限延伸的纸带控制的灵魂。这鸿蒙之初的原始机器智慧,仅用读写和涂抹就解决了图灵停机、判定性、哥德尔、丘奇的全部问题!

  10. 血族使天说道:

    写的非常好,就是悲催的现在都没有1

  11. 8.smqm.net说道:

    这方面著作国内太少了,真的理解也需要看外国著作,但翻译上总感觉语言不太对路

  12. 御宅暴君说道:

    晕,成了坑啊

    不过第一次通过这文章了解到图灵机的真谛,震撼到了,真他妈的强大!

  13. shadows说道:

    看到这个话题就想起以前看到过的经典著作:
    《哥德尔、埃舍尔、巴赫:集异璧之大成》(Gödel, Escher, Bach: an Eternal Golden Braid)

  14. 穷梦说道:

    《烛影摇红·图灵机》
    学算蒙童,笔毫稿纸雌黄备。
    乘除加减幂开方,算法依需配。
    落笔擦除进位,看纸间、繁花乱缀。
    就班按部,得数自来,妇孺通会。

    纸带长长,图灵机去摹人类。
    机头左右纸间回,读写方格馈。
    移步循规列队,算法控、机行纸退。
    莫轻言陋,电脑虽奢,礼行三跪。

Leave a Reply for darcyyang