OKCoin

计算的极限:逻辑与图灵机

大猫(bitPaul) 发布在 其它文章 1 4256

【 题记】 纪念那些伟大的数学开拓者

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

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”。状态转移表就是由一系列这样的简单规则组成的。可以说,状态转移表就相当于图灵机的源代码。

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

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

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

—————-

来源:科学松鼠会

版权声明: by nc" sa 作者保留权利。文章为作者独立观点,不代表巴比特立场。

评论:1

您需要登录后才可以回复 登录|注册