日志分类:算法相关

图灵机

时间:2013年09月15日作者:小侃评论次数:0

图灵机是图灵为了研究可计算问题而构思的一个理论装置,你只要想一想有限状态机就可以大概知道图灵机是个什么概念了,只不过图灵机的内存(纸带)是潜无穷的(也就是可以任意长啦,“潜无穷”是古稀蜡人的说辞)。图灵机的定义形象的说来就像老式的电传机:一个读写头,一根纸带(可能任意长),读写头不断读取纸带上的符号,并根据内在的状态转换规则转换当前状态,同时进行一些动作,譬如插除或改写当前字符,向前/向后移动读写头或保持不动等。至于其抽象的定义大抵就是有限状态机的定义了。图灵机的这一定义现在我们看起来似乎是很显然的,然而当时却代表着一种思想上的革命,一种从无到有。图灵机实质上抽象出了我们平素进行机械式计算的核心规律,所以才等价于“一个人+纸笔+一定的规则”进行机械运算呢。这么个理论机器首先就指明了创建计算机的可能性,然而这还不够,如果为了某一个问题就去创建一个特定的图灵机的话效率就太低了。图灵机理论的一个最美妙的结论就是存在“元图灵机(Universal Turing-Machine,直译应为一般图灵机/通用图灵机,然而“元图灵机”更精确地表达了其意思),所谓元图灵机其实就是把图灵机作为运算对象的图灵机,假设有一个元图灵机M,一个图灵机P以及P的输入数据D,那么将(P,D)喂给元图灵机M,M就能够吐出P(D)(即P在D上的结果)。而这便是现在我们所用的计算机的始祖模型,其中M就好比我们的计算机(元图灵机),P则是程序(编码后的图灵机),D则是程序P的输入数据。元图灵机的存在表明了我们可以用一台机器来解决所有图灵可计算(turing-computable)的问题——只要喂给它解决这个特定问题的图灵机编码(程序)以及问题的输入数据即可,该元图灵机就会模拟我们喂给它的那个图灵机P的行为,最终给出结果。元图灵机的存在性为计算机的诞生点燃了一盏明灯,这是图灵机理论中最漂亮的发现。

 

关于图灵机还有两个有名的Halt Problem和Busy Beaver Problem,不过前者更有名,但没有后者有意思,所以具体就不说了,可以google。这两个问题说明了图灵机并不是“万能”的,它只能解决可以“机械地”解决的问题,只不过这个“机械地”定义太过含糊,没有准确地界定,所以有必要精确定义一下图灵机到底能解决哪些问题,换句话说,到底哪些问题是图灵可计算的。这里有一个非常漂亮的证明,是关于哪些数是图灵可计算的,说有无穷多个实数是图灵不可计算的。首先说明一下一个数是图灵可计算的是个什么概念,一个数是图灵可计算的就是说存在一个图灵机,给它一个空纸带,最终它能打印出任意逼近该数的结果。像pi、自然常数E以及所有多项式的根就都是图灵可计算的(可由机械步骤任意逼近),这很好理解,因为我们可以写一个程序来迭代任意逼近它们,譬如E就是一个无穷级数的和。但还有其它实数呢?有没有图灵不可计算的实数?要想弄明白这个问题,先要考虑一共存在多少个图灵机(废话,当然是无穷多个了,但“无穷多”也有一个级别问题:)),为此先将图灵机进行编码,由于图灵机的状态是有限的,将图灵机编码为一个五元组(5-tuple)(Old_State,Symbol,New_State,New_Symbol,Move)的序列(或更多/更少都有可能,这是比较常见的一种编码方式,但总之一定是N-TUPLE,N有限),那么我们来考虑一个N-state(N个状态),M-symbol的图灵机一共有多少种可能,为此,先考虑对应N-state、M-symbol的5-tuple(见上面的定义)有多少个,根据简单的排列组合规律,一共是N*M*N*M*3(最后一个3是指Move的可能性——静止/向前/向后),换句话说,也就是以M,N为参数的一个upper-bounded function。OK,现在来考虑一个图灵机的编码形式,一个图灵机其实就是由一集5-tuple所构成,所以既然N-state,M-symbol的5-tuple一共有N*M*N*M*3个,换句话说,这个由所有可能的5-tuple所构成的集合中一共有N*M*N*M*3个元素,那么这个集合的所有子集合的个数也就是N-state,M-symbol的所有图灵机的个数,根据幂集的定义,这也就是2N*M*N*M*3个。这里为了简单起见,我们暂且固定M为M­­0,即symbol的个数,这样所有M0-state的图灵机的个数就是: 21*M0*1*M0*3+22*M0*2*M0*3+23*M0*3*M0*3+… = ∑2i*M0*i*M0*3。现在我们看到,这个和式的每一项都是coutable的,而Z×Z尚且是可列集,就别说这里每项都有限的情况了,所以很容易就可以和Z建立起单射(injective),换句话说,所有M0-state的图灵机的集合是一个可列集。好了,现在把M0换成变量,既然所有M0-state的图灵机集合都是可列的,而M0又是自然数(可列集),再加上“可列集个可列集”仍然是可列集这一性质,就容易得出一切图灵机构成的集合是可列集这一结论了。那么,这一结论有什么重要意义呢?非常重要,我们知道,实数集是不可列的,其势(或称“基”)为阿列夫1(而Z,即整数集的势则是阿列夫0),所以即便耗尽所有图灵机仍然还是会有“列不出”的实数。要想证明这一点也很简单,只要运用cantor在证明集合论时运用的经典的“对角线”手法,不妨简单描述一下:

首先,既然所有图灵机的集合是一可列集,我们就可以用M0,M1,M2,…来表示它们。现在假设Mi能计算出的实数为Ai0.Ai1Ai2Ai3…。那么我们构造一个新的实数B=B0.B1B2B3…,使其满足B1≠A11,B2≠A22,B3≠A33,…,Bn≠Ann。这样构造出来的一个实数B可以保证不与任何Ai相等,同时这个B并不为任何图灵机所计算出来(因为刚才的Ai序列已经耗尽了所有的图灵机)。这某种程度上就表明图灵机的势为阿列夫0(尽管对图灵机并不能称“势”)。

除此之外,函数空间的所有函数也并不都是图灵可计算的,一个函数为图灵可计算其实就代表存在一个图灵机可以模拟该函数的行为。这一结论通过刚才的证明就很好解释了:因为函数空间的势为阿列夫2,比实数集还要大,怎么可能由图灵机来枚举尽呢?要证明也很简单,同样是对角线法,就不说了。

那么,既然我们已经从原则上肯定了有些函数是不可计算的,换句话说,有些函数你虽然知道它是函数,但你就是无法用图灵机来将它模拟出来,用今天的话说,就是无法编程实现!这可比较令人沮丧,居然有无法编程实现的函数。那么究竟能否造出这么一个函数来让人瞧瞧怎么个不能编程实现法呢?这就是所谓的Busy Beaver问题。Busy Beaver问题就是要构造这么一个函数,它用于计算任意一个N-state的图灵机的最大“生产率(Productivity)”,生产率的定义就是给一个图灵机一条空纸带,最终当该图灵机halt的时候数纸带上的1的个数,就是其生产率。所有N-state的图灵机的最大生产率就是指一切N状态的图灵机的生产率中的最大者。很显然,这是一个N的函数。记为L(n)。那么问题是,这个L(n)是否是图灵可计算的?答案是不行!用反证法:假设存在这么一个图灵机B,能够模仿L(n)的行为,那么我们将它接到一个特殊的n-state的图灵机I后面(I的作用是在纸带上留下n个1,作为B的输入,可以证明,这样的I是存在的),这样形成一个新的图灵机IB,这个新的图灵机的作用就是计算L(n),其中n就是I的状态数,也是I的输出,B的输入。我们再在后面接上一个B,得到IBB这么一个图灵机,其效果为L(L(n))。那么现在考虑IBB自身的状态数,是I的状态数(即n)+2倍的B的状态数,假设B的状态数为b(b为有限值),那么IBB的状态数就是n+2b,那么可想而知n+2b状态的图灵机的最大productivity是肯定大于等于L(L(n))的,因为已经有一个图灵机的productivity是L(L(n))了,它就是IBB。这个不等式就是 L(n+2b)>=L(L(n)),由此我们可以推出n+2b>=L(n)(L(i)>=L(j)=>i>=j这一结论易证),又根据n的任意性,我们可以令其等于n+11,于是得 n+11+2b>=L(n+11),而我们知道11状态可以实现出一个将纸带上的1的数目翻倍的这样一个图灵机(试试看吧:)很简单),于是L(n+11)>=2n(只要把前面的n状态用于一个产生n个1的图灵机,后面的11状态做成一个翻倍1的数目的图灵机即可),于是得到n+11+2b>=2n,于是得到11+2b>=n。根据n的任意性,b的有限性,这就得到了矛盾!(其实这里还隐含着另一层意思,即要实现这么一个图灵机,必须要有无穷多个状态才行,即b要任意大,而根据图灵机的定义,b是有限的)。

Church-Turing Thesis大意就是说,在所有以自然数为定义域的函数中,只有那些递归函数(这里递归函数也包括有限步骤的函数)才是图灵可计算的。这一结论界定了图灵机的计算能力。乃是非常重要的。其实想想也很直观,一个无穷不循环的函数自然需要无穷多个状态才能计算了。而一个图灵机的状态是有限的,在这个有限空间中转来转去最终肯定是坠入循环,这就好像两整数相除一样,要么除尽,要么无限循环小数,用鸽弄原理可以很容易地证明。

 

来简单说说C++ Template的图灵完备性(turing-complete,更准确地说是turing-equivalent,因为turing-complete一般是指一个问题是turing-computable的)。要想证明一门语言的图灵完备性从原则上来说就是要证明它可以解决图灵可计算的所有问题。或者构造出一种转换途径,能够把任何图灵可计算问题的解决方法转换为这门语言的程序。但这里还有一个更取巧的方法,用这门语言实现一个Universal Turing Machine(其实差不多就是有限状态机啦)。C++ Template就可以做到这一点,实际上这早已有人做过了。另外,一般来说一门语言只要有if判断,递归或循环结构以及最基本的赋值能力和四则运算就是图灵完备的了,而C++ Template恰巧这些都具备,其中if判断和递归结构是借助模板偏特化能力实现的,估计语言的设计者当初也没有料到这一点会给现代C++带来这么大的影响:)

 

另外,严格来说,现今任何计算机其实都不是turing-equivalent的,因为它们的内存是有穷的。而图灵机的内存则是潜无穷的。只不过只要不出现内存不耗尽的情况都一样啦:)

标签:,分类:算法相关

逻辑与图灵机

时间:2013年09月15日作者:小侃评论次数:0

一切从逻辑开始

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

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

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

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

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

哥德尔的答案分两部分。

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

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

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

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

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

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

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

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

复杂的简单机器

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

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

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

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

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

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

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

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

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

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

所有机器的机器

图灵机非常简单,只要明白了它的运作过程,任何一个受过足够训练的计算机系本科生都可以写出一个模拟图灵机运行的程序。只消输入状态转移表和纸带的输入内容,程序就可以一步一步模拟相应的图灵机在纸带上爬来爬去的过程。对于一些熟悉图形编程的程序员来说,做个模拟动画也问题不大。即使不用计算机,靠人手一步步操作,也是一件小孩子也能完成的事。图灵机就是这么简单的一种机器。

虽然看上去简单,但实际上图灵机能做的事情远远超出一般的想象。只要有足够长的纸带和足够好的耐心,今天的电脑能做的计算,一台精心设计的图灵机也能完成。诀窍在于,电脑中的电路是有限的,电路的状态也是有限的,我们可以用图灵机去模拟电脑中的电路状态。只要有足够长的纸带,那就可以模拟出足够大的寄存器、内存和硬盘;而CPU中的电路,虽然所有可能的状态极其多,但终究是有限的,可以用图灵机模拟,虽然这台图灵机的状态转移表将会有着令人头痛的大小,以及令人偏头痛的复杂程度。但是,从原则上来说,用图灵机模拟一台电脑是完全可能的,虽然每次“读写内存”时,读写头都需要花长得令人咋舌的时间在纸带上来回奔波。

也就是说,从原则上来说,只要配备适当的输入和输出设备,以及极其好的耐心,我们完全可以用图灵机上网、玩游戏甚至执行自己写的程序。特别地,存在一台特定的编写程序专用的图灵机T,我们可以在纸带上写程序,将它输入到T,然后T就能执行这个程序。那么,如果我们将方才本科生写的那个可以模拟任意图灵机运行的程序(暂且把它称为程序P),写在纸带上输入到T中,让T去执行的话,原本的机器T就摇身一变,变成了一台可以根据输入的状态转移表来模拟任何一台图灵机的图灵机。

更精确地说,因为程序P的长度是有限的,我们可以将它直接写进原来机器的状态转移表,得到一台新的机器UTM。UTM会在纸带上读取两样东西:一台图灵机M的状态转移表的二进制编码,以及作为M的初始输入的纸带数据。然后,UTM会根据M的状态转移表和初始输入数据,在纸带上模拟M的运作过程。换言之,UTM是一台可以模拟任何图灵机的图灵机。它是所有机器的机器,所谓的通用图灵机(Universal Turing Machine)。当然,通用图灵机并不是唯一的,只要一台图灵机能完成根据状态转移表模拟任意图灵机的任务,它就是通用图灵机。

【一台通用图灵机,数据具体格式请参见来源:http://rendell-attic.org/gol/utm/utmprog.htm】

通用图灵机的想法,在如今这个计算机泛滥的时代,似乎并不新鲜。但在图灵的1935年,电子计算机甚至仍未问世,机械计算机还只能执行内设的一套指令。即使是Charles Babbage和Ada Lovelace的超越时代的设想,其中执行外部程序的概念也相当含混不清。在这种历史背景下,要归纳出通用图灵机这个概念,本身就需要极为丰富的想象力,而且这种图灵机是否存在,这是个远非显然的问题。而图灵不仅设想到了这个概念,而且正确地判断出它的存在性,这需要何等非凡的直觉!

但单纯的直觉终究不能令人信服,数学家讲究的是逻辑和证明。而要证明通用图灵机的存在,最直接的方法莫过于直接给出一个通用图灵机的实例。这并不简单,如果读者想尝试一下的话,我建议先尝试构造一个能做二进制加法的图灵机。为了降低难度,可以假设纸带上有第三种符号,表示空白,但即使如此,要构造一个能做加法的图灵机,远比想象中的困难。可想而知,通用图灵机的构造肯定更为复杂繁琐。即使是图灵,他在一开始给出的构造也是有问题的,而这些问题甚至在后来的勘误中也没有成功修正。比构造更麻烦的是证明给出的图灵机的确是一台通用图灵机,在图灵解决希尔伯特可判定性问题的论文中,有关通用图灵机的构造和证明占了相当大的篇幅。这部分非常繁复琐碎,而且其中还有错误,如果细细研读的话,绝对有诱发剧烈偏头痛的危险。

幸运的是,无论细节多么复杂,图灵的想法还是被逻辑学家们接受了。一旦领会到图灵机的能力,接受了通用图灵机的构想,再检查几个能完成基本任务的图灵机之后,大部分数学家都会认为通用图灵机的确存在,尽管他们并不一定会细看图灵的详细构造。而现代电子计算机的发展,更是验证了通用图灵机的存在:每一台电脑都相当于一台通用图灵机。

通用图灵机的存在,从侧面说明了图灵机这个计算模型的强大之处:图灵机作为一类机器,其中一个特例就可以模拟整个类别中的任意一台机器,宛如能折射大千世界的一滴水珠。但在这种强大的背后,隐隐也暗藏着不安定的因素。哥德尔不完备性定理告诉我们,有时候越强大的数学理论,因为能表达的概念太多,甚至连理论的命题和证明都能表达,反而会导致不能被证明的真命题的存在。如果一个系统足以描述它自己,那魔法般的自指将是不可避免的。图灵机如此强大,它的其中一台就可以模拟所有图灵机,会不会导致不能用计算来回答的问题存在呢?

很不凑巧,答案是会。

无法计算的问题

在哥德尔不完备性定理的证明中,哥德尔构造了一个描述了本身不可证明性的自指命题,通过这个命题完成了他的证明。要想照葫芦画瓢的话,那些关于图灵机本身的问题,将会是很好的候补。

关于图灵机,最简单的问题是什么呢?回想一下图灵机的运作过程,一台图灵机从初始状态开始,根据纸带上的内容,一边不断变换状态,一边更改纸带的内容,如此往复永无休止,除非它遇上了表示停机的那个状态,才能从这机械的计算过程中跳出,获得静息的安乐。一个自然的问题是:一台图灵机什么时候会停机呢?

更严格地说,会不会停机并不是图灵机本身的属性,它跟纸带的初始输入也有关系。对于同一台图灵机,不同的纸带输入也可能导致不同的结果和行为。比如说,我可以设计一台图灵机,它的任务只有一个:一步一步向右移动,寻找输入中的第一个1。如果输入纸带上全是0的话,那么,这台图灵机自然不会停止;但只要纸带上有一个1,那么它就会停止。所以,真正严谨的问题是:给定一台图灵机M以及一个输入I,如果我们将I输入M,然后让M开始运行,这时M是会不停运转下去,还是会在一段时间后停止?我们将这个问题称为停机问题。

初看起来,停机问题并不难。既然我们有通用图灵机这一强大的武器,那么只需要用它一步步模拟M在输入I上的计算过程就可以了。如果模拟过程在一段时间后停止了,我们当然可以得出“M在输入I上会停止”这个结论。问题是,在模拟过程停止之前,我们不可能知道整个计算过程到底是不会停止,它可能会在3分钟后停止,可能要等上十年八载,更有可能永远都不会停止。换句话说,用模拟的方法,我们只能知道某个程序在某个输入上会停止,但永远不能确定那些不停止的状况。所以说,单纯的模拟是不能解决停机问题的。

实际上,停机问题比我们想象中要复杂得多。

举个例子,我们可以编写一个程序GC,它遍历所有大于等于6的偶数,尝试将这样的偶数分成两个素数的和。如果它遇到一个不能被分解为两个素数之和的偶数,它就停机并输出这个偶数;否则,它就一直运行下去。用现代的工具编写GC这样的程序,对于计算机系的学生最多只能算一次大作业;用图灵机实现的话,也不是什么极端困难的事。然而,GC是否会停止可是牵涉到了哥德巴赫猜想。如果哥德巴赫猜想是正确的,每个大于等于6的偶数都能分解为两个素数之和的话,那么GC自然会一直运行下去,不会停机;如果哥德巴赫猜想是错误的话,必定存在一个最小的反例,它不能分解为两个素数之和,而GC在遇到这个反例时就会停机。也就是说,GC是否永远运行下去,等价于哥德巴赫猜想是否成立。如果我们能判定GC是否会停止,那我们就解决了哥德巴赫猜想。

数学中的很多猜想,比如说3x+1猜想、黎曼猜想等,都可以用类似的方法转化为判断一个程序是否会停止的问题。如果存在一个程序,能判断所有可能的图灵机在所有可能的输入上是否会停止的话,那么只要利用这个程序,我们就能证明一大堆重要的数学猜想。我们可以说,停机问题比所有这些猜想更难更复杂,因为这些困难的数学猜想都不过是一般的停机问题的一个特例。如果停机问题可以被完全解决,我们能写出一个程序来判断任意图灵机是否会停机的话,那么相当多的数学家都要丢饭碗了。

停机问题如此复杂,机械的计算看起来没有足够的力量来完全解决它。停机问题似乎是不可计算的。但要想严格证明这个结论,似乎仍要求助于深藏在图灵机之中,那魔法般的自指。

矛盾的自我指涉

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

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

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

按照反证法的格式,我们先反其道而行之,假设停机问题是可以计算的。根据定义,这说明存在一台图灵机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,根本不存在!也就是说,停机问题是不可计算的。。

 

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

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

不可判定的重复

实际上,图灵一开始并没有证明停机定理。他证明的是:不存在这样的程序,能判断任意图灵机是否会至少打印出一个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.
(特别地,如果《数学原理》中的系统是ω-一致的话,它的可判定性问题是不可解的。)

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

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

函数构成的世界

【图片来自Wikipedia】

丘奇作为图灵在数学上的前辈,思考的问题自然比图灵要深远得多。图灵考虑的问题,仅仅是希尔伯特的可判定性问题,而丘奇当时思考的,是如何重构数学的基础。

当时正是第三次数学危机勃发之际,数学界各路人马对数学基础应该置于何处争论不休。当时公理化集合论刚刚建立,作为新事物,自然有人持观望态度,而丘奇就是其中一位,他觉得自己可以创造一个更好的理论,以此作为数学的基础。与其选择集合与包含这两个概念,他选择了数学中另一个重要的概念:函数。

数学家眼中的函数,比你想像的要广泛得多。在中学数学中,说到函数,自然会联想起它在平面直角坐标系的图像。这是因为中学数学中的函数,大部分情况下不过是从实数到实数的映射而已。而数学家眼中的函数,可能与程序员眼中的函数更相似:它们更像是一个黑箱,从一边扔进去某个东西,另一边就会吐出来另一个东西。

我们并没有限定能扔进黑箱的东西。事实上,将黑箱本身扔进黑箱也是可以的。对这种把戏,数学家们再熟悉不过了,在泛函分析这一数学分支中,数学家们就经常研究一种叫“算子”的数学概念,在某些特殊情况下,就是那些将一个函数变成另一个函数的函数。所以,不去限定能扔进黑箱的东西,似乎也没什么问题。

总而言之,函数就是将一个函数变成另一个函数的东西。那么,要用符号表达这么普遍的函数概念,我们需要什么呢?

首先,就像在方程中我们用x, y, z等等符号表示未知数,我们也希望能用符号表示未知函数。我们将这些表示未知函数的符号称为变量。

其次,如果我们手上有两个函数M和N,那么我们自然希望研究函数N被函数M“处理”之后会变成什么。也就是说,既然M是一个函数,能将一个函数变成另一个函数,那么M会将N这个函数变成什么呢?即使不知道具体的过程,我们也希望能表达最后的结果。所以,我们将N被M处理后得到的结果记为(MN)。这被称为函数的应用(application)。

最后,也是最抽象的概念,就是函数的抽象(abstraction)。

我们可以用变量x来表示未知的函数,自然也可以用x来构造更多的函数。比如(xx)就表示函数x应用到自己身上的结果,而((xx)y)就表示将刚才得到的结果应用到另一个未知函数y上得到的结果,如此等等,不一而足。如果我们将变量x替换成一个具体的函数f,那么这些包含变量x的表达式就会变成包含具体函数f的表达式。

也就是说,如果我们有一个包含变量x的表达式M,对于任意一个函数f,我们可以将它对应到一个新的表达式,记作M(f),而这个新的表达式是将M中的所有x替换成f所得到的。比如说,如果M=(xx),那么M(f)=(ff),M((yy))=((yy)(yy)),等等。

一个表达式也是一个函数。我们从表达式M出发,可以得到把一个函数f对应到另一个函数M(f)的方法,而这正是一个函数。也就是说,我们能从一个表达式“抽象”出一个函数。我们将这个函数记作λx.M,x是我们所要考虑的自由变量。

【注:在这里,我们只能替换那些所谓的“自由变量”。粗略地说,自由变量是那些之前没有被抽象过的变量。详细的技术细节略显繁复,而且也有办法绕过,所以于此略过。】

从这三点基本要求出发,丘奇开始定义他的λ演算。他将他考虑的这些函数称为“λ项”,而所有的λ项都可以从以下三种途径构造而成:

1. (变量)所有变量x,y,z,…都是λ项。
2. (应用)如果M和N都是λ项,那么(MN)也是λ项。
3. (抽象)如果M是一个λ项而x是一个变元,那么λx.M也是一个λ项。

接下来,丘奇定义了一些λ项之间的转换法则。

首先是α重命名,这项转换可以使我们在遵循一定的规则下,任意变换λ项中的变量名称,而不改变λ项本身的意义。也就是说,λ项中变量的名称无关紧要,无论是x, y, z还是苹果、香蕉、榴莲,又或者是小庄、游游、李清晨,项的本质是不变的。

然后是最重要的β规约:

(λx.M)f→βM[x←f]

在这里,M[x←f]实际上是M(f)的严谨记法,表明了我们要替换的变量。而β规约实际上就是根据定义计算函数的一个过程。

最后,还有一个η变换。它的实质是所谓的外延性,也就是说,如果两个项对所有函数的作用都是相同的话,那么就认为这两个项是相同的。

这么几条简单的法则,就是丘奇的λ演算的全部内容。

那么简单的法则,很难想象λ演算能表达什么复杂的数学概念,这看起来不过是符号的简单推演而已。但既然同样简单的图灵机中也暗藏玄机,那说不定λ演算也有它自己的复杂内涵。

分崩离析的世界

丘奇最初建立λ演算的目的,是希望将它作为一种逻辑推理的方法。我们可以将某些逻辑公理表达为λ项;对于某个逻辑命题,我们可以先将其转化为λ项,再根据λ演算的法则将它不断简化,而命题正确与否就蕴含在计算结果之中。

通过这种方法,丘奇成功地在λ演算的框架下表达了不少的数学系统。λ演算看起来是如此的成功,甚至达到了无所不能的程度。

但如果我们还记得哥德尔的教训的话,无所不能有时并不一定是什么好事,因为在数学和逻辑的领域中,对于有意义的逻辑系统,强大的表达能力必然伴随着坚不可摧的限制。如果一个系统无所不能,那么更大的可能是它本身就自相矛盾。就像一个理论,如果对的也好错的也罢,正面反面都能解释得通,那相当于完全没有解释。

果然,几乎在丘奇向学术界展示他的λ演算的同时,克林(Kleene)和科里(Curry)就证明了,作为一个逻辑推理系统,λ演算在本质上就存在着矛盾,它是不一致的。通过适当地构造一些λ项,克林和罗瑟(Rosser)成功地利用λ演算找到了一切命题的证明,甚至包括那些错误的命题!一个连错误的命题都能证明的逻辑系统,也就是说一个不一致的逻辑系统,没有任何意义。

值得一提的是,上面这几位后来都成为了数理逻辑界的大人物。克林和罗瑟是丘奇的学生,而科里则师从希尔伯特。我们后面还会讲到这位科里教授,他的事迹之一就是有整整三个不同的编程语言是以他的名字命名的,连中间名都用上了,影响力可见一斑。

事实上,丘奇当初在筑建λ演算之时,就已模糊地认识到了这个问题,但他觉得这只是一种幻象,通过某些适当的限制,就能摆脱这些恼人的问题。但丘奇错了,实际上这是一个本质性的问题。

那么,问题的根源在何处?

我想,读过本系列之前文章的读者应该都猜到了,又是那绕不过去的自我指涉!

自指

但是,自我指涉在什么地方呢?

还记得λ项是什么东西呢?它的原型是函数,但不是一般的函数。在定义λ项之时,我们允许它将任意的λ项转化为另一个λ项。既然是任意的λ项,那么当然也包括它自己。如果将λ项看成程序的话,那又是一个可以将自己当作输入数据的程序。与图灵机不同的是,在λ演算之中,根本没有数据和程序之分,一切都是λ项,它们既是程序,也是数据。

λ演算的能力不止于此。考虑所谓的Y组合子:

Y=λx.(λy.x(yy))(λy.x(yy))

将它应用到任意一个函数$f$时,我们会得到:

Yf=(λx.(λy.x(yy))(λy.x(yy)))f
→β(λy.f(yy))(λy.f(yy))
→βf((λy.f(yy))(λy.f(yy)))
=f(Yf)

这样不停替换下去,得到的结果就相当于将函数$f$应用到自身任意多次。λ演算的能力,特别是在自我指涉方面,于此可见一斑。

正是如此强大的表达能力,使得作为逻辑系统的λ演算一无所能。如果还记得图灵机是怎么在停机问题上失效的话,实际上利用相似的技巧,对于任意的命题,我们可以构造一个λ演算中的证明,无论命题本身是对是错。

后来Curry的工作在更深刻的意义上揭示了这一点。他概括了λ演算的某些特性,然后证明了对于无论什么逻辑系统,只要它拥有这些特性,那么它必然是不一致的。而这些特性,也恰好是会碍事的那部分自我指涉所需要的。

于是,作为一个逻辑模型,λ演算一败涂地。

但丘奇没有就此止步。虽然λ演算不能如他所愿成为数学的推理基础,作为一个计算模型似乎倒也不错。我们可以将一个计算过程看成函数,将输入数据转化为输出数据的函数。于是丘奇将“可有效计算”定义为“可以用λ演算表达的函数”。这时,自我指涉的特性就成为了不可多得的优点,因为这实际上说明λ演算有强大的计算能力。利用自我指涉的特性,通过相似的构造方法,丘奇同样解决了希尔伯特的可判定性问题,得到了与图灵相同的结论。

丘奇在构想λ演算之时,瞄准的是更为基本的数学基础模型,但它却成为了可计算性的模型,真可谓“无心插柳柳成荫”。这就是图灵看到的那篇论文的由来。

不难想象图灵当时读到这篇论文时的心情。如果将数学比作攀山,当你千辛万苦登上一座处女峰,却蓦然发现山顶已经插上了别人的旗帜,你大概会觉得一切都似乎失去了意义。

但数学毕竟不是攀山,不同的路径可能有不同的景致,要论高下为时尚早。况且要比较两者,要先知道两者解决的到底是不是同一个问题。虽然图灵和丘奇解决的都是同一个问题,但他们对“可计算性”各自做了不同的假定。图灵认为“可计算的问题”就是图灵机可以解决的问题,而丘奇则认为那应该是λ演算可以解决的问题。

问题是,图灵机和λ演算这两个计算模型,它们解决问题的能力一样吗?两种视点下的可计算性,到底是殊途同归,还是貌合神离?

分类:算法相关

希尔伯特之梦,以及梦的破灭

时间:2013年09月15日作者:小侃评论次数:0

一个天才质疑了另一个天才,并最终证明:数学家研究的“有意义”的数学命题也可能是不可判定的。

Wir müssen wissen, wir werden wissen.

我们必须知道,我们必将知道。
你听到的,正是80年前,1930年,希尔伯特在他退休时演讲的最后六个单词,也是鼓舞一代数学家的六个单词。尽管当时第三次数学危机仍然阴魂不散,但他们坚信,数学大厦的基础是坚实的。他们也坚信,任何数学真理,只要通过一代又一代人的不断努力,都能用逻辑的推理将其整合到数学的大厦中。

这是何等的气魄!这是何等的梦想!

但就在演讲前夕,他的同胞哥德尔,作出了一个断言,彻底打碎了这个梦。

希尔伯特计划

 

希尔伯特

 

希尔伯特是一位名副其实的数学大师,有人将他称为“数学界最后一位全才”,他看待数学的眼光也是相当深刻的。

师从林德曼,希尔伯特在23岁便以一篇关于不变量理论的论文跻身数学界。他的证明方法在当时相当具有争议性。

在这篇论文中,他使用了非构造性的证明,也就是说他只能证明某个数学对象的存在性,却无法将它具体指出。比如说,一个报告厅有100个座位,有99位听众进去了,我可以断定一定有一个空座位,这就是一种非构造性证明。但我没办法将具体的空座位指出来,希尔伯特也无法具体构造所要证明的对象,所以当时也受到了一些数学家的批评。

另外,他的证明依赖于对无穷的对象使用排中律,从而遭到了不少人的质疑。

排中律,说的就是一件事非真即假,这再明白不过了,为什么还有反对的意见呢?

比如说这样一个命题:π中含有任意长度的连续数字9。如果我们接受排中律的话,这个命题非真即假。但无论这个命题是真是假,我们都无法在实际上验证,因为要验证这个命题,我们都要将π无穷地计算下去,而这是不可能做到的。所以,人们对于将排中律用到这种无穷的情况仍有顾虑,因为这不是他们的直觉能掌握的范围。

我们不知道是否因为这件事,希尔伯特动起了为整个数学寻求一个坚实基础的念头,但我们可以知道,在经过多年在不同数学领域富有成果的涉猎后,希尔伯特将目光投向了整个数学。对平面几何学的严格公理化可能是他在这方面的第一个尝试,但他的思考绝不仅限于几何。他的目标是将整个数学体系严格公理化,然后用元数学——证明数学的数学——来证明整个数学体系是坚实的。

为了这个目标,他制定了著名的希尔伯特计划。

首先,将所有数学形式化,让每一个数学陈述都能用符号表达出来,让每一个数学家都能用定义好的规则来处理这些已经变成符号的陈述。这使数学家可以摆脱自然语言的模糊性,取而代之的是毫无含糊之处的符号语言。比如说,我们如果想说“存在一个集合是空的”,我们就必须解释什么是存在,什么是空,等等。但如果用符号表达这句话的话,就成了:axiom of empty set,这就毫无含糊之处了。

然后,证明数学是完整的,也就是说所有真的陈述都能被证明,这被称为数学的完备性;证明数学是一致的,也就是说不会推出自相矛盾的陈述,这被称为数学的一致性。完备性保证了我们能证明所有的真理,只要是真的就可以证明;一致性确保我们在不违背逻辑的前提下获得的结果是有意义的,不会出现一个陈述,它既是真的又是假的。

最后,找到一个算法,可以机械化地判定数学陈述的对错,这被称为数学的可判定性。

如果这个计划完成了,那意味着什么?首先,一致性是很重要的,因为我们不能接受比如说“哥德巴赫猜想既对又不对”这样的结论,一致性就保证了自相矛盾的情况不会出现。在保证数学的一致性这个前提下,我们又有数学的完备性,也就是说只要是真的都可以证明。这其实就是说,对于任意一个数学猜想,不管它有多难,只要假以时日,通过一代又一代人的努力,总是可以知道这个猜想对不对,并且证明或否定它。换句话说,我们知道,在数学中,通过逻辑,我们必定能知道我们想要知道的东西,这只是个时间问题。

我们必须知道,我们必将知道。

这是个雄心勃勃的计划,但希尔伯特并不认为这是不可能的。他提出,先在基础的数学系统进行这样的形式化,然后再将其推广到更广阔的数学系统中,最后实现整个计划。于是,整个计划便归结于在算术系统中进行这样的形式化,并且在它的内部证明它的完备性、一致性和可判定性。算术系统可以说是非常基础的,我们做算术,对自然数做加法、乘法和数学归纳法,就都用到了这个系统。但我们平时只是凭直觉来理解这个系统,而数学家追求的是用逻辑的方法来定义它,这样他们才会觉得安心。

这似乎不太困难。算术系统并不是一个很复杂的系统,它早在1889年就被皮亚诺归结成一个有5条公理的系统,其中只有最后一条数学归纳法公理比较复杂。我们可以想象,希尔伯特本人也认为这是可以解决的问题。他将算术公理系统的相容性列入了他那23道希尔伯特问题中,位列第二,希望20世纪的数学家能给出一个证明。这份1900年写出的问题表,后来证明是相当具有前瞻性的,即使情况并不一如希尔伯特预计的那样。

1931年,仅仅在他退休一年之后,希尔伯特第二问题即告解决,尽管解决的方式是希尔伯特所没有预料到的。

逻辑弄人。

哥德尔不完备性定理

 

哥德尔

 

可以说,哥德尔粉碎了希尔伯特计划。

在希尔伯特退休之时,哥德尔才刚刚登上数学舞台。在某种意义上,正是希尔伯特间接将哥德尔引领到数理逻辑这个领域的。在希尔伯特和他的学生阿克曼合著的《数理逻辑原理》中,他们提到了这样一个问题:在形式系统中,真的命题是否都是可证明的?这正是哥德尔博士论文的主题。在这篇论文中,哥德尔证明了一阶谓词演算是完备的,这就是不太著名的哥德尔完备性定理。一阶谓词演算是一种能力比较弱的数学系统,如果只是应用它的话,我们连自然数都定义不了,就更别说做算术了。自然,哥德尔的目光是不会仅仅局限于此的。

在完成博士论文之后,哥德尔便着手探索更一般的数学系统。一年后,也就是1931年,他对算术系统的探索即告胜利。这个胜利,也就是希尔伯特计划的失败。他的结论,就是哥德尔不完备性定理,一共有两个。

第一,他证明了,对于任意的数学系统,如果其中包含了算术系统的话,那么这个系统不可能同时是完备的和一致的。也就是说,要是我们能在一个数学系统中做算术的话,那么要么这个系统是自相矛盾的,要么有那么一些结论,它们是真的,我们却无法证明。

第二,他证明了,对于任意的数学系统,如果其中包含了算术系统的话,那么我们不能在这个系统内部证明它的一致性。这就是希尔伯特第二问题答案的一部分。

其实,这里“任意的数学系统”之中的“任意”并不是完全的任意。这些系统必须是可以显式地规定出来的,用数学的术语来说就是可有效生成的。但对于我们熟悉的像欧几里德公理这样的形式系统来说,这的确是相当任意了。

哥德尔证明这两个定理的武器,就是希尔伯特在他的计划中使用的武器:形式化。在哥德尔的证明中,他先将所有的数学陈述以及它们的证明用符号形式地表达出来,然后利用哥德尔自己发明的一个重要技巧——哥德尔数化——将所有这些陈述和证明变为一个个的自然数。那么,借助数学归纳公理,我们可以递归地建立针对所有自然数的陈述,而一个这样的陈述同时又是一个自然数,所以它描述了自己。换句话说,这个陈述陈述了它自己。

自指

自指

这种自指的情况,在数学上很有用,也非常凶险。它是不少悖论的源泉。第一个例子当然是说谎者悖论:“这句话是错的”。第二个就是罗素悖论,它引起了第三次数学危机,这也可以说是希尔伯特计划的一个动因。

我们来看看它的一个通俗版本,叫理发师悖论。

在一个小镇内,只有一名理发师,他在理发店门外公布了这样一个原则:只为不会自己理发的人理发。那么,他的头发谁理呢?要是他自己理的话,他就会自己理发了,那么根据他的原则,他不应该为自己理发;要是他不给自己理发的话,根据他的原则,他倒是应该给自己理发。逻辑似乎在这里失效了。

这种逻辑上的混乱局面,背后就是罗素悖论:定义一个集合,它包含所有不包含自身的集合,它是否包含自身?从上面的分析,我们可以看到,一切问题在于“包含自身”这种自指的描述。后来,在策梅洛和弗兰克等逻辑学家的努力下,通过在集合论中添加正则公理等限制,才将这种危险的自指从集合论中排除。当然,这是后话了。

这种自指的性质,尽管危险,但在哥德尔的妙手中,它就变成了证明的利器。他构造了一个命题,这个命题说的正是它自身的不可证明性。如果用类似说谎者悖论的语言来表达的话,就是:“不存在对这个命题的形式证明。”如果它是真的,那么它是不可证明的,说明系统是不完备的,因为存在一个真的而又不可证明的命题。如果它是假的,那么存在一个它的证明,这样它应该是真的,说明系统是自相矛盾的、不一致的。这就是哥德尔的第一个不完备性定理:如果有自然数的话,完备性和一致性不可得兼,这个系统要么自相矛盾,要么存在不能证明也不能否证的命题。

然后,我们来仅仅考虑一致性的问题。假定系统是一致的,也就是说不会自相矛盾的,那么我们刚才提到的命题就是不可证明的。如果我们能在系统内部证明系统的一致性的话,我们就相当于在系统内部证明了那个命题,这与不可证明性是矛盾的。也就是说,我们做了错误的假设:能在系统内部证明系统本身的一致性。由此,哥德尔证明了他的第二个不完备性定理。

他的这两个不完备性定理,对于希尔伯特计划是个沉重的打击:计划的第二步被证明是无法实行的。如果我们假定数学不会自相矛盾的话,我们就必须承认数学是不完备的,也就是说有这么一些数学命题是不可判定的:我们既不能证明它们为真,也不能证明它们为假。但很多数学家仍然认为,这并不威胁数学的正常发展,因为他们觉得有意义的数学命题极不可能是这样的。换句话说,数学家们仍然相当乐观。

同样是哥德尔,这次连同科恩,给这些数学家敲响了警钟:数学家研究的“有意义”的数学命题也可能是不可判定的。他们解决的又是一个希尔伯特问题:由康托尔提出的连续统假设。这个问题位于列表之首,是一个纯粹的集合论问题。哥德尔证明了连续统假设和策梅洛-弗兰克集合论是相容的,也就是说二者之间没有矛盾;科恩证明了从策梅洛-弗兰克集合论出发不能证明连续统假设。这两个结果综合起来,其实就说明了连续统假设在策梅洛-弗兰克集合论中是不可判定的。要是你知道策梅洛-弗兰克集合论正是解决第三次数学危机的武器和现代数学的逻辑基础,你就会明白这到底意味着什么。

哥德尔的魔鬼第一次露出了真面目。希尔伯特第一问题竟然就是不完备性定理中预言的那类不知真假的怪异命题的一个实例,这实在令人泄气。

既然希尔伯特计划的第二步都被证明是不可行的,那么第三步也就没有必要继续下去了。第三步是寻求一个能机械证明所有数学定理的程序,著名的停机定理也否定了这种可能性。停机定理的证明相对比较简单,也是利用自指的技巧,证明这样程序是不可能存在的。

至此,希尔伯特那宏伟的计划宣告全盘失败。

有些事情,我们确实不知道,即使对于数字,这是逻辑说的。

余波

既然对全部数学真理进行形式化是不可能的,数学家们只好退而求其次,尝试形式化他们熟悉的数学。法国的布尔巴基学派在这方面似乎走得最远。这是在巴黎高师的一帮数学家,继承了希尔伯特的一些理念,目标是将所有已知的数学在集合论的坚实基础上重建。他们出版了九本这方面的专著,每一部都以严密的公理化方法吸引着后来者的目光。他们的每本著作都会经过多次的修订,据说明年他们又会出版一本新修订的著作。

布尔巴基办公室门牌,fwjmath拍摄

布尔巴基办公室门牌,fwjmath拍摄

令希尔伯特在天国的灵魂有所安慰的是,算术系统的一致性被证明了。这个证明用到了不在算术系统内的超限归纳法,它可以被视为一种加强版的数学归纳法,是用在无穷序数上的。这其实就假定了策梅洛-弗兰克集合论的一致性。当初康托尔建立无穷集合论时,曾遭到不少人的攻击,这时希尔伯特挺身而出,为康托尔和他的无穷集合论疾呼:“没人能将我们从康托尔创造的乐园中赶出来。”如今,康托尔的无穷集合论衍生出来的超限归纳法反过来又部分实现了希尔伯特的梦,这是冥冥之中的安排,还是希尔伯特的敏锐眼光所致?恐怕没人能说得清楚。

但哥德尔的魔鬼仍在肆虐。越来越多的数学问题被证明是不可判定的,这些不可判定的问题也越来越初等。乍看起来并非不可捉摸,但到头来却不可判定。比如说,如果我们用可数种颜色对每一个实数染色,是否必定存在4个互不相等的数a,b,c,d,使得它们的颜色都相同,而又满足a+b=c+d?这看起来怎么也不像没有一个确切结论的问题,但有人证明了它实际上和连续统假设的否定是等价的,也就是说,在策梅洛-弗兰克集合论内,它也是不可判定的。这就给数学家们心头压上了一块大石:谁也不知道自己辛辛苦苦做了十几年的题目,会不会突然有一天被证明是在现有数学体系中不可判定的。

尽管这样,哥德尔的不完备性定理仍然带给我们很多教益。至少我们知道了,有些东西我们不可能知道。在哥德尔的这个划时代的证明之后,数学家对数学的基本工具——证明——有了新的认识。专门研究数学证明的证明论,在他的启发下蓬勃发展。但是,哥德尔教给我们最重要的一点是:

数学,如同人生,如同爱情,有些东西是真的,你却永远无法证明。