Fuleige 弗雷格
（F.L.）G. Friedrich Ludwig Gottlob Frege (1848～1925)
    德国数学家、逻辑学家。1848年11月8日生于德国维斯马,1925年7月26日卒于巴德克莱茵。1873年毕业于格丁根大学，获博士学位。1874年起即在耶拿大学任讲师，1879年任教授，1918年退休。在耶拿大学执教的四十余年间，致力于数学基础、数学哲学和逻辑理论的研究。
　　弗雷格于 1879年出版了《概念语言》一书，所谓“概念语言”是一种表意语言，用它进行推理最易于察觉隐含的前提和有漏洞的步骤。由于弗雷格认为算术定理可由纯逻辑规律出发证得，为了保证推理过程的绝对严格性，他特地建立了这一符号语言。他成功地引入了数学中的函数概念，建立了量词理论。这样就构作了一种基本自足的逻辑演算即一阶谓词演算。从而给出了历史上第一个严格的关于逻辑规律的公理系统。嗣后，他又出版了《算术基础》（1884）和《算术的基本规律》 （卷I,1893；卷Ⅱ，1903）。在这些著作中他首创从逻辑出发来定义数和自然数，并从逻辑规律出发推导出一系列算术定理。尽管弗雷格明确地提出了数学可以化归为逻辑的思想，但没有全面地进行从逻辑推导数学的研究，因而他未能象B.A.W.罗素和A.N.怀特海在《数学原 理》中那样精详论证、充分展开逻辑主义的纲领（见数 学基础），但弗雷格仍不失为逻辑主义的创始人之一。 逻辑主义的主要代表人物罗素，甚为称颂弗雷格的工作。 弗雷格晚年从事数学哲学和逻辑理论的研究。 　
　　　　　　　　　　　　　　　　　（徐云从）

弗雷格
大连理工大学  杜瑞芝
弗雷格，F．L．G．(Frege，Friedrich Ludwig Go-ttlob)1848年11月8日生于德国维斯马(Wismar)；1925年7月26日卒于巴德克莱茵(Bad Kleinen)．数学、逻辑学、哲学．
　　弗雷格出生的年代正值德国民主革命开始．维斯马是一个远离德国政治中心的小商业城镇，革命风潮对这里影响很小．弗雷格出生在一个信奉路德教的中产阶级家庭，在血统上是混杂的(部分是德国的，部分是波兰的)．其父亚历山大•弗雷格(AlexanderFrege)开办了一所女子学校．他去世后这所学校就由他妻子来管理．1869年，母亲奥古斯特•弗雷格(Auguste Frege)送弗雷格到耶拿大学就读．当时弗雷格就把数学作为自己的主要兴趣，但也选修了化学、物理和哲学．他的老师——数学家、物理学家E．阿贝(Abbe)及时发现了他的才能，成为他毕生信念的支持者．在阿贝的帮助下，他离开耶拿，来到格丁根大学继续深造．1873年，在数学家E．谢林(Schering)的指导下，弗雷格以论文“论平面上虚影的几何图形”(Ueber eine geometrische Darstellung derim ginaren Gebilde in der Ebene)获得哲学博士学位．该论文通过对平面上虚影图形性质的讨论，阐明了几何学基于直觉的观点．他在格丁根还参加了著名哲学家R．H．洛采(Lotze)的讲座．洛采的逻辑观念，特别是他对纯逻辑的看法，对弗雷格逻辑思想的形成有着重要的影响．
　　弗雷格在格丁根大学获得博士学位之后，又回到耶拿大学．在阿贝的帮助下，他于1874年以论文“基于量值概念外延的演算方法”(Rechungsmethoden，die sich auf eine Erweitung desGr ssenbegriffes gr nden)获得了无薪大学讲师的资格①．在这篇论文中，弗雷格提出了用于运算的量值概念，并断言算术真理产生于量值概念．1879年，弗雷格的《概念语言》问世之后，他又一次在阿贝的推荐下成为耶拿大学的编外教授．1896年成为荣誉教授．弗雷格在耶拿大学执教40余年，讲授过数学的各分支学科及有关的逻辑系统，举办过“概念符号”讲座，他一直致力于数学基础、数学哲学和逻辑理论的研究．1918年退休．
　　弗雷格首先是作为一位数学家和逻辑学家而闻名于世的．他在数学上的主要成就，是使自C．F．高斯(Gauss)以来所建立的数学体系更精确和完善，确立了算术演算的基本规则．他第一个建立了初步自足的命词演算系统和量词理论，首次提供了现代意义下的数理逻辑的一个体系，因而成为数理逻辑的奠基人．他提出数学可以化归为逻辑的思想，成为逻辑主义的创始人．弗雷格还是一位杰出的哲学家．他的绝大部分著作都具有明显的哲学特征．他认为：“一个好的数学家，至少是半个哲学家；一个好的哲学家，至少是半个数学家．”他直接把传统哲学对思维内容和认识能力的探讨，转向对语言表达形式和语言内部框架的考虑．他认为对语言意义的分析，是哲学研究的主要任务．弗雷格对哲学任务的重新规定，标志着当代西方分析哲学的开端．因此他被誉为当代分析哲学的真正奠基者．
　　弗雷格的主要著作有：《概念语言》、《算术的基础》、《函项与概念》(Function und Begriff，1891)、《论意义和所指》( ber Sinn und Bedeutung，1892)、《论概念和对象》( berBegriff und Gegenstand，1892)、《算术的基本规律》1—2卷(以下简称《基本规律》)．
　　弗雷格的科学生涯大致可以分为五个时．
　　在第一个时期，弗雷格主要从事纯逻辑的研究．其研究成果总结在1879年出版的《概念语言》中．用数学方法研究逻辑问题，一般认为是由G．W．莱布尼茨(Leibniz)提出的文字学设想开始．他提出过有关思维演算的思想．莱布尼茨的这种先驱性想法没有及时得到应有的发展．在淹没了一个世纪之后，19世纪英国的两位数学家A．德摩根(De Morgen)和G．布尔(Boole)用代数的方法建立了逻辑代数．但这种逻辑代数与亚里士多德(Ar-istotle)的形式逻辑本质上是相似的．在1874—1879年间，弗雷格攻读了布尔学派和一些哲学逻辑学家的著作．除上文提到的洛采外，18世纪德国哲学家A．特伦德伦堡(Trendelenburg)的著作对弗雷格也有较大的影响．通过特伦德伦堡的工作使弗雷格了解到莱布尼茨关于逻辑语言的观点．弗雷格还追随特伦德伦堡，把他的逻辑符号系统称作“概念语言”．弗雷格用心研究莱布尼茨和I．康德(Kant)的逻辑学和数学哲学方面的著作，有选择地接受了两位哲学家的思想．在弗雷格晚年，他是这样描述自己的研究动机的：“我开始是搞数学．在我看来，这门科学急需更好的基础：……语言逻辑的不完善对这种研究是一种障碍．我在《概念语言》中寻求弥补．所以，我就从数学转向了逻辑．”
　　经过5年的沉思，弗雷格完成了一部划时代的著作——《概念语言》．在这本书里，弗雷格把从洛采和特伦德伦堡，以及从莱布尼茨和康德那里得到的观点，变成一种全新的逻辑．这本不足80页的小书是弗雷格的不朽之作．弗雷格在此建立的逻辑有效地终结了亚里士多德逻辑两千多年来一直占据的统治地位，完成了始于几百年前G．伽利略(Galilei)破除亚里士多德物理学的进程．在《概念语言》中，弗雷格创造了一种表意的语言，即“纯粹思想的语言”．正如他在这本书的副标题中所说——它可以使我们完全精确地表达判断的概念内涵．弗雷格认为，真理分为两种，一种真理的证明必须以经验事实为根据，例如物理学中的定理．另一种真理的证明似乎可以纯粹从逻辑规律出发．他认为算术命题就是属于后一种的．在探讨如何根据思维的逻辑规律经过推理以得到算术命题时，必须绝对严格，要防止未被查觉的直观因素渗入，因此必须使推理过程没有漏洞．他觉得日常语言是表达严密思想的障碍．当所表达的关系越复杂时，日常语言就越不能满足要求．因此他创造了这种概念语言．他说，用这种语言进行推理，最有利于觉察隐含的前提和有漏洞的步骤．这种语言和日常语言相比，就好像机械手和人手相比，或者像显微镜和肉眼相比一样．利用这种语言，弗雷格成功地构造了一个严格的逻辑演算体系．下面简要介绍一下弗雷格逻辑演算的内容．
　　1．弗雷格严格区别了命题的表达和断定．他认为，我们只有能够表达一个思想，理解一个思想，才能对它加以断定．他引进断定符号“├”．“├┌”表示“┌是被断定的”．其中垂直短线“｜”称为判断短线，水平短线“—”称为内容短线．“—┌”是一个整体，它只表达可断定的内容，即命题的表达．而“├┌”才表示命题的断定．如“├┌”表示“不同的磁极相互吸引”这一断言，而“—┌”只是表达了不同磁极相互吸引这一思想，而对这一思想的正确性没有任何判断．
　　2．弗雷格明确提出真值蕴涵的思想并指出它与日常语言的区别．他采用否定和蕴涵作为基本的逻辑联结词．他用小竖线“ ”放在内容短线下面表示否定．“┬┌”表示“非┌”．符号 表示“△蕴涵┌”．他列举了┌和△的四种可能的真值组合：(1)┌肯定，△肯定；(2)┌肯定，△否定；(3)┌否定，△肯定；(4)┌否定，△否定．用符号“ ”表示以上第三种可能不实现而其余三个可能性中的每一个都可实现．弗雷格说，当┌为真时，△蕴含┌常可被断定，在此情形下，△可以是任一命题，其具体内容完全无所谓．┌和△不必有因果关系，与日常语言中的“如果……则”不同．
　　3．弗雷格引进一个内容同一的符号．设┌和△为任意名称，即不一定是命题记号，他规定，“├(┌≡△)”的意思是“名称┌和名称△有相同的概念内容，使得┌总是能由△替换，反之亦然”．他还指出，由他的新符号所联结的名称不仅代表它们的内容而且代表名称自身．后来，他改用符号“=”，“=”不被看成两个名字之间的关系，而是看成名字的指称之间的关系．“=”用于专门的指称，相当于等词；用于命题的指称(真值)，则相当于现在的等值符号．
　　4．弗雷格把数学中的函数概念引入逻辑演算，从而建立了量词的理论．他采用变目和函项两个术语，┌表示变目，记号Φ(┌)表达变目┌的一个不确定的函项．记号Ψ(┌，△)表达按顺序所取的两个变目┌和△的一个函项．假定如下一种函项：当它由变目填满时，它表达可能的判断内容．于是，“├Φ(┌)”读作“┌有性质Φ”，“├Ψ(┌，△)”读作“┌与△有关系Ψ”．弗雷格使用这种符号的主要优点是，它能够比普通语言所提供的方式更令人满意地表达一般性．在此基础上，弗雷格引进了全称量词和存在量词

　　表示“不管怎样取函项的变目，函项总是一个事实”．即“凡a都是Φ．在这里，全称量词是基本概念，存在量词则通过全称量词而表达为

　　它表达“至少有一个a是Φ”．
　　5．弗雷格建立了9条公理，用现代的符号表示为：
　　(1)├a→(b→a)，
　　(2)├(c→(b→a))→((c→b)→(c→a))，
　　(3)├(d→(b→a))→(b→(d→a))，
　　(4)├(b→a)→(┐a→ ┐b)，
　　(5)├ ┐┐a→a，
　　(6)├a→ ┐┐a，
　　(7)├(c=d)→(f(c)→f(d))，
　　(8)├c=c，
　  
　　公理以外有四条变形规则：
　　
　　(2)代入规则，弗雷格使用了但没有严格地陈述．
　　
　
　　假定a并不在表达式Г中出现，而且a仅处于Φ(a)的变目空位中．
　　
　　a不在┌和△中出现，Φ(a)中的a只处于变目空位中．事实上，这条规则是第三条规则的推广．
　　弗雷格在上述公理和规则的基础上，进行了大量的推演，成功地构造了一种基本自足的逻辑演算，从而给出了历史上第一个严格的关于逻辑规律的公理系统——现代的逻辑系统．它实质上包含了作为现代数理逻辑基础的两个演算系统——命题演算系统和一阶谓词演算系统．
　　不幸的是，弗雷格这本划时代的小册子被数学家和哲学家们忽视了．他在《概念语言》中建立的新逻辑没有马上被人理解．其中使用复杂而陌生的符号来表达新奇的概念，确使读者望而生畏．德国数学家E．施罗德(Schrder)发表长篇文章，对该书进行全面批评．事实上，直到B．A．W．罗素(Russell)1901年开始发现弗雷格著作的价值之前，《概念语言》几乎没有读者．
　　《概念语言》出版之后，弗雷格的创造生涯进入第二时期．在这一时期，弗雷格开始形成逻辑主义的观点．在最初几年，他由于自己的著作没有受到重视而大受挫折，没有发表任何作品．但他仍然在重新思考和深刻挖掘自己的哲学和数学观点，并逐渐形成了他的数学哲学的三个主要原则：第一，他反对在数学基础问题上的经验主义，否认数学来源的经验基础，强调数学真理的先天性；第二，他认为数学真理是客观的，这种客观性基于数学的非经验的基础．在他看来，客观性是思想的必要条件；第三，他主张一切数学最终都可化归为逻辑，数学概念可以定义为逻辑普遍要求的概念，数学公理可以从逻辑原则中得到证明．这第三条原则后来被罗素作为逻辑主义的基本主张而广为传播，弗雷格因此成为逻辑主义的创始人之一．
　　弗雷格在《算术的基础》中力图作为逻辑的延展去建立数学．为此，首先要从逻辑推出算术．为使大家能够理解他的著作，他对自己的观点及关于数和算术所流行的各种哲学观点作了非形式的说明．然后他指出，要从逻辑推出算术，首先必须给出数和自然数的定义．
　　弗雷格接受他的前辈的观点：所有大于1的自然数可由指出它们的前趋即用“2=1+1”，“3=2+1”一类等式来定义．但他认为，这些定义是不完全的，因为使用了“数1”和“加1”这两个未定义的概念．他考察了从欧几里得(Euclid)到G．康托尔(Cantor)以来的许多数学家的著作，发现关于数的定义是相当混乱的．他指出在此之前所见到的一切关于数的定义都含有基本的逻辑错误．他说：“数是什么？这是一个最根本的问题．如果我们对这个问题都不能做清楚的回答，岂不是一个笑话？”又说：“数学的本质就在于，一切能证明的都要证明，而不是通过归纳法来验证．因此，我们也应考虑如何来证明关于正整数的命题．”
　　弗雷格发展了《概念语言》中关于数学序列的理论．在那里他用“遗传性”定义了“y属于从x开始的f-序列”和“y是x的f-后裔”，为自然数的定义和说明数学归纳法作了理论和技术上的准备．弗雷格给出的自然数的定义的核心在于使用了“一一对应”的概念：属于两个概念F和G的对象借助于关系Φ一一对应，如果(1)每一个属于概念F的对象对于属于概念G的一个对象，有关系Φ；(2)对于属于概念G的每一个对象，存在一个属于概念F并与前者有关系Φ的对象；(3)对所有x，y和z而言，如果x对y和z有关系Φ，那么y和z就是同样的；(4)对所有x，y和z而言，如果x和y对z有关系Φ，那么x和y就是同样的．
　　弗雷格在此基础上构造了以下三个定义：
　　(1)“概念F与概念G是等数的”与“存在一个关系Φ，使得属于概念F的对象与属于概念G的对象一一对应”其意义是相同的．
　　(2)属于概念F的数是“与概念F等数”这一概念的外延．
　　(3)“n是一个数”与“存在一个概念使得n是属于它的数”其意义是相同的．
　　接着他又定义了“n在自然数序列中是m的直接后继”：“存在一个概念F和一个归于它的对象x，使得属于概念F的数是n，属于概念‘归于F但不同于x’的数是m”．这实质上是后继函数的定义．
　　在这些工作的基础上，弗雷格取0作为数列的起点，提出如下定义：
　　0是属于概念“不同于自身”的数，
　　1是属于概念“同于0”的数，
　　2是属于概念“同于0或同于1”的数，
　　3是属于概念“同于0或同于1或同于2”的数，
　　……
　　可见，1在自然数序列中是0的直接后继，2在自然数序列中是1的直接后继，等等．
　　事实上，弗雷格所用到的“一一对应”概念与康托尔所谓的集合的“等价”意义是一样的，弗雷格指出，他的数与康托尔理论中集合的“势”或“基数”是相同的．两个概念同数，就是两个集合等价．概念“与概念F等数”的外延，就是与集合F等价的一切集合构成的集合．所以弗雷格实际上是把数定义为集合的集合，或类的类．利用康托尔的语言，概括弗雷格关于数的定义：
　　(1)一个集合的基数是所有等价于它的集合的集合．
　　(2)0=df•｛^｝(空集合的单元集)
　　1=df•｛0｝
　　2=df•｛0，1｝
　　3=df•｛0，1，2｝
　　弗雷格的后续函数的定义实际上是说：后续函数把等价集合的集合m映射到一个新的集合的集合Φ(m)(即n)，Φ(m)中的每一个集合是由在m中的某一个集合加上一个新分子而得到．
　　 由此可见，自然序列中的每一个数，有一个直接后继的数．这样，自然数就由0和后继函数而确定下来．
　　有逻辑学家评论，弗雷格的这个定义系统是哲学技巧中极其卓越的成就．人们也很容易理解，为什么弗雷格认为他至少使得算术化归为逻辑是可能的．
　　在《算术的基础》的最后几页，弗雷格指出，其他类型的数，也可以用类似的方式加以定义．实数和复数同样可以刻画为概念的外延．在《基本规律》的第二卷中，他阐明了这个方案是如何实施于实数的．
　　康托尔在1884年也给出数的定义，但弗雷格的定义比康托尔的更为精确．
　　弗雷格从逻辑出发定义了数和自然数，他对自然数的归纳定义也是对数学归纳法的最好说明．他认为，借助于上述定义，自然数的概念就被化归成了逻辑的概念；自然数的理论则可以借助于上述定义和逻辑得到建立，这样，算术理论就被“逻辑化”了．
　　弗雷格在他的第三时期集中精力写作《基本规律》．原计划写三卷，实际上只完成两卷(1893，1903)．弗雷格准备在这部专著中，从逻辑出发去展开除了几何学以外的全部数学．他认为，逻辑的原则是完全可靠的，一旦完成了上述工作，数学“就被固定在一个永恒的基础上了．”
　　1893年，出版了《基本规律》第一卷，它是《算术的基础》的理论的严谨发展，书中改进了《概念语言》符号系统，提出了不同的公理，阐述了高阶谓词演算．从《概念语言》到《基本规律》，弗雷格的逻辑发生了三个主要变化：(1)他在自己的系统中加上了函项的值域这一概念；(2)区分了意义的两个方面，即“所指”和“意义”；(3)更为严格地规定了与对象相对的函项的性质，明确提出了“第一层函项”和“第二层函项”的区别．第一层函项就是以前所定义的函项，其变目是对象，第二层函项就是函项的函项，其变目是函项，例如在Mβ(F(β))中，Mβ就是第二层函项，其变目是F．弗雷格还把概念分为第一层概念和第二层概念．这些逻辑上的变化在《基本规律》第一卷之前的5篇文章①中就已经提出并作了解释．
　　 弗雷格在《基本规律》第一卷中建立了另一个逻辑系统——二阶谓词演算，提出了新的公理．他用‘xF(x)代表F(x)的值域，例如，若F(x)表达“x是人”，则它的值域‘xF(x)就表达“人类”．他还引进代表定冠词的函项符号＼x．如＼’xF(x)读为“那个具有性质F的x”．用现在的符号表示弗雷格的新公理如下：
　　
　　在这个新系统中，除分离规则和代入规则之外，弗雷格还把原来系统的一些公理和定理作为新的推理规则．在这一系统中处理了命题演算，谓词演算，类理论和关系理论，更重要的是进行了推导算术的工作．
　　《基本规律》第一卷出版后，再次受到冷遇．只有G．皮亚诺(Peano)在1895年作了评述，但他对这本书的内容没有足够的理解．这再一次使弗雷格深感痛苦．然而，弗雷格并没有放弃自己的目标，他继续撰写《基本规律》第二卷，其中主要论述实数的理论，并用较多的篇幅批评当时流行的观点．
　　但是，弗雷格并没有完成他的计划．因为要理解数学科学的性质，除了算术以外，还必须考虑无穷集合的理论——集合论．弗雷格没有深入研究集合论，没有接触到关于无穷集合的各种问题，特别是悖论问题．1902年，正当弗雷格等待《基本规律》第二卷付印的时候，他收到了罗素6月16日写给他的信．信中首先称颂他的工作：“就我所知，您的工作是我们时代中最好的．”“在许多具体问题上，我发现您的著作都进行了讨论、区分和定义，这使其他逻辑学家的工作黯然失色．”具有讽刺意味的是，罗素的来信既标志着弗雷格的工作开始得到承认，也宣告了他的独创性工作的终结．因为罗素在他的信中接着写道：
　　“只有在一点上我遇到了困难①，……由于下述矛盾：令W为不能论断自身的谓词的谓词，W可以论断自身吗？每种回答都隐含着它的否定①，因而人们必须得出，W不是一个谓词．同理，没有不包含自身的作为整体的类的类．由此我得到，在某种条件下，一个可定义的集合没有构成一个整体．”
　　 罗素当时并没有完全认识到他的发现是怎样严重地威协着弗雷格的逻辑主义纲领．但是，弗雷格本人毫无疑问地认识到这个矛盾的潜在致命力．他对罗素来信的反映迅速而强烈，他马上复信[15]：
　　“您发现的矛盾引起了我极大的震惊，我几乎可以说是惊愕不已，因为它动摇了我建立算术基础的企图，……我的《基本规则》第二卷看来是有缺陷的．我无疑要补充一个附录，对您的发现作出论述．”
　　在1903年，弗雷格出版了带有一个后记(写于1902年10月)的《基本规则》的第二卷．他在后记中不无悲哀地写道：
　　“对于一个科学工作者来说，最不幸的事情莫过于：当他完成他的工作时，发现他的知识大厦的一块基石突然动摇了．正当本书的印刷接近完成之际，伯伦特•罗素先生给我的一封信使我陷入这种境地．这封信是关于我的公理V的问题．我本人从来没有掩盖这条公理缺乏其他公理所具有的并必为逻辑规律所正当要求的自明性．
　　……
　　成为问题的恰恰不是我建立算术的特殊方式，而是算术是否完全可能有一个逻辑基础．”
　　弗雷格的第四时期是在极度消沉中度过的．这一时期长达十几年．最初，他相信能有补救的办法使他的系统避免矛盾．他首先提出一种设想：可能有一些概念没有相应的类．然后他用修改第Ⅴ公理的办法来阻止罗素悖论的衍生．但是，后来逻辑学家的工作证明，他所做的努力并不足以使他的系统避免不一致．他还打算论述集合论的逻辑悖论(1906)．经过几年的努力之后，弗雷格似乎不那么相信能够找到解决矛盾的办法．虽然他没有公开放弃自己的主张，但也不再做进一步的努力．至到1918年，弗雷格才彻底放弃把算术化归为逻辑的一切希望，放弃了《基本规律》第三卷的写作计划．从此以后，他又进入了新的研究时期．他的研究兴趣仍在数学基础上，并很自然地转向几何学，提出了几何学是整个数学的基础的主张．弗雷格在1903年以后发表的论著很少．
　　虽然弗雷格的逻辑主义纲领没有实现，但是他的独创性工作对数学和哲学的发展都产生了重要影响．他的成就在有生之年没有得到广泛的承认，只是通过少数几位有洞察力的人的努力，他的思想才逐渐得到理解，并通过他们的工作得到发展．
　　首先认识到弗雷格工作重要性的是罗素．罗素在他的《数学原理》(Principles of mathematics，1903)的附录中，对弗雷格的逻辑进行了深入细致的研究，对弗雷格的从《概念语言》到《基本规律》第一卷等论著作了广泛详尽的评论．罗素发展了弗雷格的思想，他和A．N．怀特海(Whitehead)在《数学原理》(Principia mathematica，1910)中精详论证，充分展开了逻辑主义纲领．书中可以看出弗雷格的明显影响，甚至罗素与弗雷格不同的观点也是受到弗雷格著作中难点的启示而提出的．罗素表示：“在逻辑分析问题上，我们主要是从弗雷格获得教益．”稍后，罗素的学生和朋友L．维特根斯坦(Wittgenstein)成为弗雷格的崇拜者．这位20世纪的著名思想家明确指出，他的哲学工作的两个来源是“弗雷格的巨著和我的朋友罗索的著作”．30年代末期，由弗雷格本人的学生L．卡尔纳普(Carnap)以及美国逻辑学家A．丘奇(Church)的倡导，弗雷格的逻辑理论，特别是关于意义和所指的学说重新引起人们的研究兴趣[27]．1950年，《算术的基础》英译本出版，在使用英语的数学家中产生很大影响．
　　1918年以前，弗雷格一直安静地生活在耶拿这座小小的大学城内．他身材矮小，性格胆怯羞涩．弗雷格的工作长期得不到理解和承认．一般认为，他的著作对于大多数数学家来说是过于哲学化了，而对大多数哲学家来说又过于数学化了．弗雷格的著作长期受到冷遇，在相当长一段时间内，哲学杂志和数学杂志都拒绝发表他的论文．由于得不到专业上的承认，他在耶拿大学当了好多年的编外教授．弗雷格还经受了长远计划失败的体验．所有这一切使他变得比较内向．他长期远离自己的数学和哲学同事．但是，弗雷格全心全意追求真理，从不追求个人名声；他屡受拙折而不放弃自己的奋斗目标；他勇于承认自己的失败并另辟蹊径提出新的主张．弗雷格这种追求真理的执著精神和科学态度值得后人学习．

苹果树下的散步

欧洲有个古老的传说：一辆著名的战车，被一根山茱萸树皮编制的绳索牢牢地捆住了。你要想取得统治世界的王位吗？那就必须解开这个绳结。无数聪明、强悍的勇士满怀希望而来，垂头丧气而去，因为绳结盘旋缠绕，绳头隐藏难寻。一天，亚历山大也慕名来到这里，他略略思索一下，便果断地抽出宝剑，一剑把绳截成两段。难解的绳结就这样轻而易举地被“解开”了。亚历山大因此享有对整个世界的统治权。

1888年9月6日，人们惊喜地获悉：十多年来许多数学家为之奋斗的著名难题——果尔丹问题，终于被一位当时尚名不见经传的青年人攻克了。他运用的方法和途径是那样的出人意料、令人折服，就像亚历山大解开绳结一样；也正如这位显赫的君主在辽阔的欧亚大陆上留下旷世战功，这位年轻人穷尽毕生心血和才华，在广阔的数学领域里纵横捭阖，遍及现代数学几乎所有的前沿阵地，在整个数学的版图上，到处都刻下他那光辉的名字。他就是数学世界的亚历山大——大卫•希尔伯特！

哥尼斯堡是德国一座古老而美丽的城市，康德、哥德巴赫是这座城堡的荣誉和骄傲，著名的七桥问题更使之名扬欧洲。1862年1月23日，希尔伯特就诞生在这座富有学术传统的城市里。受家庭的熏陶，早在中学时代，希尔伯特对数学就表现出浓厚的兴趣，并立志把数学作为自己奋斗的专业。

1880年秋，希尔伯特进入哥尼斯堡大学。这里的学术空气浓厚而且自由，非常适宜希尔伯特的生活习性和学习要求。这段时间内，他同两位年轻的数学家的交往使他受益终生。一位是比他大3岁的胡尔维茨，在希尔伯特还是学生时，这位见多识广的青年就已是副教授；另一位是闵可夫斯基，虽比希尔伯特小两岁，但已荣获巴黎科学院大奖而名扬国际。他们三位一体，情投意合。他们每天下午“准5点”相会于校园旁边的苹果树下，互相交流彼此的学习心得、制订计划、探索未知领域。对于每一个重大问题，他们总是分头准备、认真思考，并各抒己见，有时也会争得面红耳赤。据说，曾有一位前来哥尼斯堡大学访问的外地学者，这天偶然经过苹果园，忽然听到里面传出几个人互不相让的争吵声，他驻足而观，发现三位年轻人比比划划，旁若无人。这位好心的人觉得有必要去劝解一下，但马上就知道自己的担心是多余的。那正是希尔伯特三人在讨论问题。

苹果树下的小路清晰地向远方延伸。他们通过日复一日的无数次散步，漫游了数学世界的每一个角落。这种数学家们特有的学习方式给他们其中的每一位带来了希望、成功和友谊。

苹果树下的散步使希尔伯特利用有趣而又容易接受的学习方式像海绵吸水那样接受数学知识，并以最简洁、快速的方法到达数学研究的前沿阵地。胡尔维茨渊博、系统的知识，闵可夫斯基快捷、灵敏的思维，无不令希尔伯特如醉如痴，也激励着他更加如饥似渴地学习、思考。这段时光为希尔伯特打下了牢固而全面的基础，他也因之能在以后的岁月里频频出击，并获得数学麦加——哥廷根大学的教授席位。

善疑名问会将学习引向深入，开放性的学习方式有利于塑造创造性的品质，相互影响、彼此促进的环境是培养人才群体的基本要素。这是“苹果树下的散步”给予的启迪。难道我们今天的教育、教学就不可以有所借鉴吗

哥德尔，K．F(G del，Kurt Friedrich)1906年4月28日生于奥匈帝国的布尔诺(今属捷克斯洛伐克)；1978年1月14日卒于美国普林斯顿．数学、逻辑学、数学哲学．
　　哥德尔的父亲在青年时代即从维也纳迁移到兴旺的纺织工业基地布尔诺定居，他富有自力更生的创业精神，后来成了那里一家主要纺织厂的管理方面的领导者．哥德尔的母亲一家由莱茵河地区到布尔诺从事纺织工业，她曾在布尔诺一所法语学校读书，受过较好的教育，她终生对文化事业保持兴趣，她生育了哥德尔兄弟二人，哥德尔的哥哥比他大四岁，后来成了一位放射学家．
　　哥德尔有一个幸福的童年，但他胆小又爱吵闹，在六七岁时患了急性风湿性关节炎，危害了他的健康，特别是影响了他的心脏．他的才智很早就显露出来了．由于他经常提出各式各样的问题，家里人常称他为“为什么先生”(Mr Why)．1912年，他六岁时进入布尔诺的巴黎学校上学．从1916年到1924年，他的学习成绩优秀，特别是在数学、语言和神学方面表现尤为突出．
　　第一次世界大战直接影响了哥德尔及其家庭，虽然布尔诺地区远离战争前线，但战后，1918年奥匈帝国解体了，出现了新国家：奥地利、捷克斯洛伐克、匈牙利等．1924年哥德尔毕业于布尔诺大学预科，然后到维也纳大学学习．当时，维也纳作为1919年新创立的奥地利共和国的首都，是当时的政治、经济、文化中心．1929年哥德尔成了奥地利的公民．在维也纳大学，哥德尔先学物理，后主攻数学．他参加了以攻读B．罗素(Russell)的专著《数学的哲学导论》(Introduction to mathematical philosophy，1919)为中心的讨论班．在1926—1928年期间哥德尔也参加了维也纳 M．施利克(Schlick)的哲学小组，但他并不赞成逻辑实证论观点，1929年他逐渐离开了这一小组，但他仍与该组成员R．卡纳普(Carnap)保持一般的接触．哥德尔离开石里克小组的主要原因是他已建立了自己的独到的哲学观点．
　　哥德尔的老师、数学家P．富特温勒(Furtw ngler)对他有很大的影响．他的导师H．哈恩(Hahn)的研究兴趣主要是现代分析、集合论、拓扑、逻辑、数学基础和科学哲学，在知识背景方面直接影响了哥德尔．但是，哥德尔在确定自己的研究方向时，起重要作用的两个因素是卡纳普的数理逻辑讲演，D．希尔伯特(Hilbert)和W．阿克曼(Ackermann)的专著《理论逻辑原理》(Grundzge der theoretischen Logik,1928)．在这本书的1928年版(即第二版)中著者列举了一阶谓词演算的完全性这个未解决的问题．哥德尔把这一问题作为自己的主攻方向．1929年夏季，当时只有23岁的哥德尔肯定地解决了这一问题：证明了一阶谓词演算的完全性定理．由此，在1930年2月他获得了博士学位．随后，他进一步研究希尔伯特方案，希望用有穷方法证明数学形式系统的协调性问题，主要是关于算术、分析和集合论等系统的协调性问题．1930年8月26日哥德尔向卡纳普等人通告了他的不完全性结果，即数论形式系统如果是协调的，则它是不完全的，并且它的协调性在系统内是不可证明的．1930年9月7日哥德尔在柯尼斯堡召开的数学讨论会上第一次正式公布了他的上述结果．同年10月23日在维也纳科学院他也报告了他的上述结果．哥德尔的不完全性结果与希尔伯特的猜想相反，并且从根本原则上否定了希氏方案．希氏学派的主要成员冯•诺伊曼(von Neumann)、P．伯奈斯(Bernays)先后认识到了哥德尔上述结果的巨大的潜在意义，希尔伯特也不得不重新修改了他的方案．从1930年起，哥德尔与冯•诺伊曼、伯奈斯、E．F．策梅罗(Zermelo)、A．塔斯基(Tarski)等著名数理逻辑学家建立良好的关系．冯•诺伊曼出生于匈牙利，比哥德尔仅大三岁，但他当时已在证明论、集合论、分析学和数学物理等方面作出了重要结果，因而名噪一时．伯奈斯是希尔伯特的助手与合作者，策梅罗是集合论公理系统的首创者，塔斯基是波兰逻辑学家，由于他的形式语言真值概念的工作而成名．他们的交流促进了数理逻辑的发展，扩大了这一学科的影响，并使哥德尔开创的方向成了这一学科的主要倾向．在1933年3月经过简短的教学实习，哥德尔出任维也纳大学的无薪水讲师．同年9月30日赴美国讲学，作为普林斯顿高级研究院的客座成员，他报告了他的不完全性结果．同年12月哥德尔在美国数学会年会上报告了“数学基础的现状”． 1934年4月18日哥德尔在纽约哲学学会上的讲演题目是“包含算术的任意形式系统内不可判定命题的存在性”．接着4月20日在华盛顿科学院讲了“数学能够证明协调性吗？”同年5月26日至6月3日乘船返回欧洲．1935年5月在维也纳大学他讲授数理逻辑课程，其间曾于6月19日在蒙格尔的学术讨论会上介绍他的证明长度的论文．1935年9月至12月哥德尔第二次访问美国．10月间他向冯•诺伊曼通报了他的选择公理相对协调性证明．由于健康原因，他向普林斯顿高级研究院辞职回维也纳治病，1936年他主要在治疗疾病．1937年哥德尔在维也纳大学讲授公理集合论课程，并发现了广义连续统假设相对集合论公理协调性证明的关键步骤．
　　1938年9月20日，哥德尔与安迪(Adele Nimbursky)女士结婚．安迪比哥德尔大六岁，早在1927年哥德尔才21岁时他们就相爱了．安迪是位舞女并且曾经结过婚，对于他们的相爱，哥德尔的父母极力反对．尽管哥德尔的父亲在1929年已病故，他们仍推迟了多年才结婚．婚后半个月，1938年10月6日哥德尔把妻子留在维也纳，独自应邀第三次赴美国讲学，10月15日到达普林斯顿高级研究院．直至12月他都在讲述选择公理、连续统假设相对协调性结果，其间《美国科学院学报》(Proceedings of theNational Academy of Science， U．S．A，24，pp．556—557)宣布 了他的结果．同年12月28日哥德尔在美国数学学会第45届年会上报告了“广义连续统假设的协调性”．1939年《美国科学院学报》(同上，25，PP．220—224)发表了哥德尔的论文“广义连续统假设的协调性证明”(Consistency－proof for the generalized con－tinuum－hypothesis)．同年6月14日—20日，哥德尔乘船由美国返回维也纳．虽然，哥德尔当时已解决了几项重大的数学问题，三次应邀赴美国讲学，他已成为世界知名的数理逻辑学家，但他在维也纳大学仍然是一个无薪水的讲师．9月25日他申请晋升为正规的讲师，无人理采．这样，哥德尔就不得不寻找到美国定居的途径了．1940年1月哥德尔偕夫人安迪离开维也纳到美国定居．1938年3月13日希特勒已吞并了奥地利，哥德尔离开纳粹统治下的维也纳使他从此有了一个进行研究工作的安定环境．从此，他再也没有回过欧洲．
　　1940年春，哥德尔到达普林斯顿高级研究院，成了该院的成员．同年普林斯顿大学出版社出版了哥德尔的专著《广义连续统假设的协调性》(The consistency of continuum hypothesis)，这是根据他于1938至1939年在普林斯顿高级研究院讲演的原稿整理的，全名应是《选择公理、广义连续统假设与集合论公理的相对协调性》(The consistency of the axiom of choice and of thegeneralized cantinuum－hypothesis with the axioms of set theo－ry)．1941年4月他在耶鲁大学的讲演是“在什么意义下直觉主义逻辑是构造的？” (In what sense is intuitionistic logic cons－true tive？)1942年作出了“在有穷类型论中选择公理的独立性证明”(Proof of the independence of the axiom of choice in－finite type theory)．1944年发表了“罗素的数理逻辑”(Russell＇smathematical logic)．1946年在普林斯顿200周年纪念会上就数学问题作了讲演．1947年发表了重要的数学哲学论文“什么是康托尔的连续统问题？”(What is Cantor＇s continuum problem？)
　　哥德尔在普林斯顿最亲密的朋友是著名物理学家A．爱因斯坦(Einstein)和数理经济学家O．摩根斯顿(Morgenstern)．他们经常散步和闲谈．1948年4月2日他们三人一起到美国移民局，一起取得美国国籍，成为美国公民．哥德尔与爱因斯坦一直是最亲密的朋友，直至爱因斯坦1955年去世．虽然他们两人在性格上有很大的差别，爱因斯坦爱社交，活泼开朗，而哥德尔严肃认真、相当孤独，但是他们都是直接地全心全意地探求科学的本质．1943年后，哥德尔逐渐把注意力转向数学哲学乃至一般的哲学问题．当然他也还不断地关注逻辑结果，比如1958年他研究了有穷方法的扩充，1963年审阅并推荐了P．J．科恩(Cohen)的重要论文“连续统假设的独立性”(The independence of the continuumhypothesis)．1973年评述了A．鲁宾逊(Robinson)创立的非标准分析．哥德尔这些工作对数理逻辑的发展都起了重要的作用．
　　1953年哥德尔晋升为普林斯顿高级研究院的教授．
　　1951年哥德尔获得爱因斯坦的首次奖，以后多次获得荣誉称号，如哈佛、洛克菲勒等著名大学的荣誉博士、英国皇家学会国外会员、法国研究院的通信成员．哥德尔于1966年还拒绝接受奥地利科学院授予他的荣誉成员称号．1975年9月18日他获得了美国总统奖，当时的总统是福特．
　　哥德尔妻子安迪于1981年在普林斯顿去世，他们没有子女．
　　我们曾经指出，哥德尔是亚里士多德(Aristotle)和G．W．莱布尼茨(Leibniz)以来最伟大的逻辑学家．但是，这决不仅仅是由于他的聪明才智所决定的，更重要的是数学、逻辑学发展到20世纪所面临的问题、面临的任务并由此而出现了一大批优秀的逻辑学家，哥德尔是其中最突出的代表．19世纪在微积分基础工作中出现了A．柯西(Cauchy)、K．魏尔斯特拉斯(Weierstrass)、R．戴德金(Dedekind)和G．康托尔(Cantor)这样一批大数学家，他们十分重视数学的逻辑严谨性．G．弗雷格(Frege)又建立适应数学论证的谓词演算，在逻辑学中首次引进全称量词和存在量词的概念．1900年巴黎数学家大会上希尔伯特提出了23个未解决的数学问题，其中第一个问题是康托尔的连续统假设是否成立，第二个问题是算术公理的协调性．他指出，在关于公理系统所能提出的问题中，最为重要的是：证明这些公理不互相矛盾，就是说，以它们为基础而进行的有限步骤的逻辑推演，决不会导致矛盾的结果．1900年前后，先后在康托尔集合论中发现几个令人吃惊的悖论．这样，出现了数学基础的危机，为解决这种危机，L．E．J．布劳威尔(Brouwer)提出了在数学中取消无穷对象、取消数学论证中无限制地使用排中律的直觉主义建议，由此形成了数学基础研究中的直觉主义学派．罗素提出了把数学还原为逻辑，形成了逻辑主义学派．罗素与A．N、怀特海(Whitehead)合著的《数学原理》(Principia mathematica)一书中完全应用了数理逻辑的方法，从一些逻辑概念和数学公理出发实际上推导出很大一部分数学，而这是沿着弗雷格、G．皮亚诺(Peano)的思路开始的．希尔伯特强调数理逻辑在数学基础研究中的巨大作用，但他不赞成逻辑主义，更反对直觉主义．在希尔伯特看来，悖论的根源不在于实无穷，而在于对实无穷的错误认识．希尔伯特认为直觉主义否定实无穷，否定排中律等等，是对数学“这门科学大砍大杀”，就会使数学“失去大部分最宝贵的财富”．希尔伯特及其学派制定了一个保卫数学建立其严谨基础的方案，人们称之为希尔伯特方案．这一方案是要将数学理论进行形式化处理，建立相应的形式公理系统，用有穷方法研究系统的完全性、协调性和判定性等问题．这些形式公理系统共同的逻辑基础是谓词演算，当时已证明了谓词演算的可靠性(或称一致性)，即任一逻辑定理在所有的解释(或称赋值)下都是真的(称之为普遍有效的)．但是，谓词演算是否具有完全性呢？也就是说，谓词演算中普效命题是否是逻辑定理呢？这是1920年前后人们关注的一未解决的重大问题，直至1928年在前述的希尔伯特与阿克曼的专著第二版中仍然是末获得解决的问题．1929年哥德尔肯定地解决了这一问题，证明了谓词演算的完全性定理．这一结果，对于希尔伯特方案是一有力的支持，因为它表明了希尔伯特所依据的逻辑基础是既可靠又完全的一门独立的数学理论．
　　哥德尔完全性定理在谓词演算的语法概念与语义概念之间架起了一座桥梁．这里语法概念指形式系统，语义概念指数学模型．这就是说，哥德尔定理是在形式系统与数学模型之间架起了一架桥梁．
　　形式系统的一合式公式(或称命题，也称语句)集合 S叫做协调的，如果此系统内不存在一合式公式A，使得从S出发公式A与A的否定式 A都是可证的．S不是协调的就叫它是不协调的．一不空集合M及M上定义的关系、函数等一起可以构成一结构．形式系统的一命题A，在结构M上做解释，对于这一解释而言，命题A经解释后在结构M中是真的，就称结构M为A的一模型．若S中每一命题经解释后在结构M中都是真的，就称M是S的一模型．显然，结构、解释、模型都是语义概念．依据上述概念，哥德尔完全性定理是说：对于谓词演算的任一命题集合S而言，都有：
S是协调的当且仅当S有模型．
　　这里所讲的谓词演算是一阶古典谓词演算，也称为狭谓词演算，“一阶”是相对“高阶”而言的，即量词的变域是个体域，而不能是谓词，也不能是函数词，“古典”是相对“直觉主义”或“各种非经典或非标准”而言的．
　　哥德尔完全性定理是当代模型论的基本定理之一，由它导出了一系列重要结果．
　　还应当指出，哥德尔完全性定理是对形式系统的整体特征性定理(而不是系统内的形式定理)，这种定理称之为元定理或元数学定理．按照希尔伯特方案和当时人们的思想观念，元定理应局限在有穷方法内给出证明，排中律与无穷过程是不能被使用的．然而，这一定理是很强的，用有穷方法是不可能给出证明的．哥德尔看出了这一问题，大胆地采用无穷方法找出问题的答案，给出了定理的证明．对此，哥德尔曾在致王浩的信中说道，他解决了完全性在于他的哲学思想先进，不拘泥于有穷方法，而并不是他的数学技巧比别人高明(见 Wang Hao，From mathematics to philosophy)．在哥德尔晚年，王浩是他的最好的朋友之一，他们之间就数学基础和哲学问题有许多内容深刻的交谈．
　　哥德尔不完全性定理是更令人吃惊的．如前指出，不完全性是指形式算系统而言的，也可以说是指皮亚诺算术系统P而言的．哥德尔证明：如果P是协调的，则有一算术的形式命题A即A为P中一命题)，并且A与 A在P中都不可证明的．这与希尔伯特的猜想完全相反．希尔伯特猜想，不仅形式数学系统的基础逻辑——谓词演算是完全的，而且每一个形式数学系统也是完全的，特别是皮亚诺算术系统P也应当是完全的，它的命题集合总是可以一分为二，一部分是P的定理集合(即其中每一元都是P的定理，不妨把定理集合记为T)，另一部分是P的可驳集合(即其中每一元都是P的否定理，即它的否定式是P的定理，不妨把P的可驳集合记为R)．希尔伯特猜想，系统P的命题集合恰好就是T与R的并集合：T∪R．这就是说，皮亚诺公理系统巳完全刻画了算术系统．但是，哥德尔否定了希尔伯特的猜想，从而否定了希尔伯特方案．哥德尔具体地严谨地证明了存在一命题A，A和它的否定式 都不在T中，也不在R中．也就是说，P的命题集合不可能按照其元(即命题)是可证可驳的原则分为两部分，这是一重大的结果．哥德尔怎样获得这一结果呢？
　　为了证明上述定理，哥德尔区分了形式系统内外的几个层次和它们间的联系．第一步，形式系统的概念是使用无数学概念建立起来的．这些元数学概念是若干个符号的规定、转换和说明．第二步，是把元数学概念通过配数方法(这一方法也是哥德尔给出的)给出算术化处理，用自然数的函数与关系把它们描述出来，并证明这些函数与关系的机械性质，即它们是递归函数与递归关系．第三步，证明递归函数与递归关系在形式数论系统内都是数词可表达的．哥德尔通过这些精湛的数学技巧，从错综复杂的联系中弄清“命题A在P中是可证的”、“公式序列Г是命题A在P中的一证明”等关于形式系统P的元数学概念都可以算术化为关于自然数间的关系与函数．并且它们又都是在P中可表达的，从而他构造了他的定理所要求的命题AP，并得到了上述不完全性定理的证明．由此，哥德尔证明：AP，与 AP在P中都是不可证明的，从语法上讲，AP与 AP都是不可证的，而从语义上，AP与 AP必然有一个是真的(事实上由哥德尔的构造过程可知，AP是真的)．因此，哥德尔第一次澄清了真与可证是两个不同的概念．对于形式系统而言，可证性是一个较为机械的思维过程，而真理性则是一个能动的和超穷的思维过程，二者不能混为一谈．此外，命题AP对自己也是有所断定的，这就反对了罗素与怀特海关于命题不能对自己有所断定的意见．
　　上述哥德尔不完全性定理在文献中常称为哥德尔第一不完全性定理．哥德尔还证明了另一个定理，文献中称之为第二不完全性定理，这一定理是说，如果系统P是协调的，那么它的协调性在系统P中是不可证明的．它的证明是通过把“P是协调的”这一元数学概念加以算术化，然后在P中形式化，得到它的形式公式可记为“con(P)”．我们再把第一定理的证明，即
(*)“若P是协调的，则AP是不可证的”
　　加以形式化，也就是把(*)的整个证明在系统P内形式化，则我们应获得
(**)P con(P)→AP．
　　现在，设P con(P)，这时，由(**)叫将获得P AP，这就得到与第一定理相矛盾的结论．从而就得到了第二定理的证明．
　　哥德尔的上述结果对逻辑学和数学特别是数学基础产生了巨大的影响，使逻辑学、数学基础学在新的起点上获得了新的发展，揭示了机械的与非机械的思维活动的基本性质，论证了形式系统的逻辑标准与局限性问题，这些都是人类认识史上的重大结果．对于机械的思维活动，哥德尔在证明不完全性定理时，采用了递归方法并开展详尽的论述．根据J．埃尔布朗(Herbrand)和哥德尔的意见，S．C．克林(Kleene)对一般递归函数理论作了深入的研究，A．丘奇(Church)建立λ演算理论，A．M．图灵(Turing)建立另一种机械性思维过程，以描述算法，现在人们称之为图灵机器．人们很快就证明：上述几种机械性思维过程的概念和理论都是等价的，可以相互转换的．近年来，人们进一步发现了一系列可以相互转换的算法概念与理论，并且愈来愈展现出他们在计算机领域内的巨大作用．
　　关于连续统假设相对于集合论通常公理系统的协调性证明以及在证明过程中所创立的可构成性方法，是哥德尔的又一重大贡献．连续统问题是康托尔首先提出的，这涉及到无穷集合、无穷基数中一些根本问题．在许多无穷集合的比较中，以什么为标准呢？康托尔提出按一一对应来区分集合的“大小”，与自然数集合有一一对应关系的集合称为可数集合，诸如此种集合的基数定义为 ，把所有具有基数为 的集合收集在一起所组成的哪个集合的基数为 ，以此类推，可以获得无穷基数序列：

　　其中α为任意的序数．另一方面，实数集合的基数，也就是自然数集合的所有子集合所构成的哪个集合的基数为2，康托尔证明它大于，然而它究竟等于式(1)中哪个基数呢？因为式(1)是一严格递增的基数序列，并且2大于，因此，就有

　　1878年康托尔猜想式(2)中的等号应当成立．也就是说，他猜想：

　　就是康托尔的连续统假设．1883年，康托尔在他的论文“关于无穷线性点集合(5)”( berunendliche lineare Punktmannigfaltig－keiten 5，Mathematische Annalen，21(1883)，pp 545—586)中，希望不久将能够公布他的猜想的严格证明．随后，他还一再声明将公布他的证明．但是，直至1918年1月6日康托尔去世，他也没有把他的证明公布于众．大概是他发现了原来的证明有错误而未公开发表．
　　1900年夏季在巴黎举行的第二次国际数学家代表大会上，希尔伯特做了题为《数学问题》(Mathematische Probleme， Archivder Mathematik und Physik，Series 3，1，pp．44—63，213—237)的演说，提出了前面曾经说过的23个未解决的问题，向20世纪的数学家们提出挑战．其中第一个问题就是“证明连续统假设”．他说：“康托尔关于这种集合的研究，提出了一个似乎很合理的定理，可是尽管经过坚持不懈的努力，还是没有人能够成功地证明这条定理．这一定理就是：每个由无穷多个实数组成的系统，亦即实数集合R的无穷子集合(或点集合)，或者与自然数1，2，3，……组成的集合对等(即有一一对应的关系)，或者与全体实数组成的集合对等，从而与连续统(即一条直线上的点的全体)相对等；因此，就对等关系而言，实数的无穷子集合只有两种：可数集合和连续统．”他接着又说：“由这条定理，立即可以得出结论：连续统所具有的基数，紧接在可数集合的基数之后；所以，这一定理的证明，将在可数集合与连续统之间架起一座新的桥梁．”1925年，已经63岁、身患多种病的希尔伯特又提出了试图证明连续统假设的大纲，这就是他1926年的论文“论无穷”( ber das Unendiche，Mathematische Annalen，95，pp．161—190)．遗憾的是他的证明有漏洞，证明是错误的．这一切都表明连续统问题是很有意义的、难度很大的问题．1934年波兰学者W．谢尔品斯基(Sierpinski)出版他的专著《连续统假设》(Hypothese du continu)，揭示了在分析数学中有12个数学命题与连续统假设等价，有81个命题是它的直接推论．这就更突出了它的重大意义．对于这一问题，哥德尔所取得的重大进展是连续统假设与集合论的通常公理系统(包括选择公理)是协调的，也就是说，集合论的通常的公理系统(包括选择公理)推不出连续统假设的否定式．在证明过程中，哥德尔引进了可构成集合、可构成公理等重要概念．对于任意一集合S而言，集合S1叫做S的可定义子集合，如果有一公式(x1，…，xn，x)和S的元素a1，…，an，使得
S1=｛x|x∈SΛ(a1，…，am，x)｝
　　成立，令S＇为S的所有可定义子集合所组成的集合．令
L0= ， (4．1)
La+1=(La)＇， (4．2)

　　一集合x叫做是可构成的，如果存在一序数α，使得x∈La．
　　可构成公理是说，每一集合都是可构成的，常常记做V=L．哥德尔首先证明通常集合论公理(不包括选择公理)都在L中成立，然后证明，可构成公理蕴涵选择公理与连续假设．文献中常把选择公理记做 AC(Axiom of Choice的缩写)，连续统假设记做CH(Continuum Hypothesis的缩写)，并且把通常的集合论公理系统理解为策梅罗-弗伦克尔(Zermelo－Fraenkel)系统(通常简记为ZF，不包括选择公理，当把它理解为包括选择公理时，也常记做ZFC)．使用上述记号，就有
V=L→ACΛCH， (5)
　　在ZF中可证明．第三步，哥德尔还证明了：V=L在L中成立．从而就得到了选择公理与连续统假设在L中成立．因为V=L并非是一真命题，只是在L中真，所以AC与CH也并非真命题，它们只是在L中真．哥德尔的结果给人们一种宽慰，不会因为使用选择公理增加不可靠性，也就是说，人们使用ZF公理所建立的数学理论没有矛盾时，再进一步地使用选择公理，即在使用ZFC时所建立的数学理论也没有矛盾．哥德尔建立的AC与ZF的相对协调性证明也是一项重大结果．
　　哥德尔的结果还有更广泛的结论，这就是在L中不仅CH成立，而且广义连续统假设(Generalized Continuum Hypothesis，常缩写为GCH)也成立．其中GCH是F．豪斯多夫(Hausdorff)在1908年提出的，对于任意的序数a，应有等式

　　成立．事实上，康托尔在1883年也曾说应有

　　成立．显然，式(3)与(7)都是式(6)的特殊形式．哥德尔在前边提到的1940年的专著中证明的是V=L→ACΛGCH．他的结果较之更为广泛．
　　哥德尔创立的可构成方法开辟了集合论研究的新方法、新方向，文献中常称为内模型方法．1940年以后人们对它进行了系统的研究，获得了极小内模型等重要结果，在这些结果与方法的基础上，P．J．科恩(Cohen)1963年创立了力迫方法，证明了广义连续统假设、选择公理相对于通常集合论公理的独立性结果．当我们用符号“ ”表示“推不出”时，哥德尔的定理就是：

而科恩的定理是：

　　这就是100多年以来，人们对选择公理与连续统假设的主要结果．康托尔提出的连续统的势到底等于什么呢？或者说，2 到底是无穷基数序列式(1)中哪一个呢？这仍然是一个未解决的重大的数学问题．关于这一点，哥德尔早在1947年的哲学性论文“什么是康托尔的连续统问题？”(What is Cantor＇s Continuum prob－lem？)中就指出：“康托尔连续统问题，不论采取什么哲学观点，不可否认地至少保持这个意义：去发现它是否有一个答案，如果有，那么是什么答案，是能从所引用的系统中所陈述的公理推导出来的．”
　　“自然，如果按这个方法解释，那么(假定公理的协调性)对于康托尔猜测就先验地存在着三种可能性：它是可证明，或者是可否证的，或是不可判定的．”
　　哥德尔的结果说明不可能是“否证的”，科恩的结果说明不可能是被“证明的”，因此，就是“不可判定的”了．哥德尔着重指出，从所采取的集合论公理对康托尔猜测的不可判定性的证明，“决不是问题的解决”．它仍然是当代数学的一大难题．这在某种程度可归之于纯数学的困难．此外，哥德尔说：“看来这里还含有更深刻的原因，并且只有在对它们中出现的词项(如“集合”、“一一对应”，等等)和支配这些词项的使用的公理的意义进行(比数学通常作的)更深刻的分析，才能得到这些问题的完全解决．”在哥德尔看来，如果我们所解释的集合论的原始词项的意义被认为是正确的话，那么就可以得出，集合论的概念和定理描述了某个完全确定的实在(即论域)，在其中康托尔猜测必然或者是真的，或者是假的．“因此，从今天所采取的公理得出康托尔猜测的不可判定性，只是意味着这些公理没有包括那个实在的完全描述．”他又说：“可能存在就其证明的结果来说是如此丰富的其它公理，它照亮整个领域并产生这样强有力的解决问题的方法(并且，只要是可能的，甚至可以构造地解决它们)，使得不论它们是否是内在必须的，至少应在如同任何已经完全建立的物理理论同等的意义上接受它的．”哥德尔在分析了与连续统假设有关的许多数学命题之后指出：
　　“与大量的蕴涵连续统假设的否定似乎真的命题相反，没有一个已知的似乎真的命题蕴涵连续统假设．”因此，在新的系统中，“有可能否证康托尔猜测”．
　　哥德尔40年前的论断，仍然是当今集合论学者关心的课题．以S．斯拉(Shelab)为代表的一批学者提出了一条称为正常力迫的公理，由此可推出 ．但是，正常力迫公理是否具有公理的资格，也是当前人们极为关心的问题．
　　我们不难看到，哥德尔在“什么是康托尔的连续统问题”这一哲学论文中是紧紧抓住连续统这一难题展开的，他所揭示的观点对于数学研究是有指导意义的，他的思想极为深刻．哥德尔在他的另一篇哲学论文“罗素的数理逻辑”(Russell’s mathematicalIogic，1944)中着重分析了罗素的逻辑思想的发展，指出了数理逻辑在实际发展中曾采取的方法，“…最重要的简单类型论和公理化集合论，它们二者至少在这个范围内是成功的，即它们允许推导现代数学同时避免一切已知的悖论．但许多迹象只是更加清楚地表明，一些原始的概念尚需进一步阐明”．哥德尔进一步发挥了莱布尼茨的思想：“人类将有一种新的工具，同任何视觉工具对视力的帮助相比，更大大增强推理的能力．”哥德尔等人开创的机械思想过程的研究和现代计算机的结合正在不断地发展着新型的推理工具．
　　哥德尔的工作还有许多方面有引人注目的创造成果，比如：(1)加速度定理，或称证明长度定理，在1936年的论文“关于证明的长度”( ber die L nge von Beweisen)中哥德尔建立了类型、强度都逐一增加的系统：S1，S2，…，Si，Si＋1，…．主要结果是：在Sn与Sn+1(n∈ω)中都存在诸命题，它们在系统Sn与Sn+1中都是可证的．但在Sn+1的证明长度要比Sn中的长度短得多．人们认为，这一结果对于计算机科学可能产生重要的影响．(2)关于判定问题的可解情况，哥德尔发表了论文“对于理论逻辑判定问题的一个特别情况”(Ein Spezialfall des Entschei－dungsproblems der theoretischen Logik，1932)和“关于谓词逻辑演算的判定问题”(Zum Entscheidungsproblem des logischnFunktionenkalküls，1933)，解决狭谓词演算中可判定的命题类的最重要表达形式．所谓狭谓词演算的判定问题就是要寻找一个一般的方法，对于任意给定的命题，我们都可以在有穷步骤内判定它是否是可满足的．1936年，图灵证明了狭谓词演算是不可判定的．在图灵之前，人们一方面寻求可判定的特殊类，一方面寻求归约类(即将狭谓词演算的整个公式类归约到这一特定的类，如前束范式类就是一个旧约类)．阿克曼已经指出前束词

  归约类．这就建立了关于可满足性的可判定类与归约类之间的一个明确
　　都是归约类的结果(参见王浩《数理逻辑通俗讲话》，科学出版社，1981)．此外，哥德尔还对直觉主义逻辑等领域有重要工作，这里不一 一列举了．
　　综上，我们不难看出，哥德尔的工作影响和推动了数理逻辑近60年的发展，使它从较为分散的研究工作扩大为独立的系统的学科，并且产生了若干研究分支，对计算机科学与技术已经产生并将继续产生深刻的影响．他作为亚里士多德、莱布尼茨以来的最伟大的逻辑学家影响将是深远的．

本论题之等价形式
本论题的另外一种说法就是逻辑和数学中的有效或机械方法可由图灵机来表示。通常我们假定这些方法必须满足以下的要求：
1. 一个方法由有限多简单和精确的指令组成，这些指令可由有限多的符号来描述。
2. 该方法总会在有限的步骤内产生出一个结果。
3. 基本上人可以仅用纸张和铅笔来执行。
4. 该方法的执行不需人类的智慧来理解和执行这些指令。
此类方法的一个范例便是用于确定两个自然数的最大公约数的欧基里德算法。
“有效方法”这个想法在直觉上是清楚的，但却没有在形式上加以定义，因为什么是“一个简单而精确的指令”和什么是“执行这些指令所需的智力”这两个问题并没有明确的答案。 (如需欧几里得算法之外的范例，请参见数论中的有效结果。)
本论题之起源
在他1936年的论文“论可计算数字，及其在判定性问题(Entscheidungsproblem--德语，译者注)中的应用”中，阿兰•图灵试图通过引入图灵机来形式地展示这一想法。在此篇论文中，他证明了“判定性问题”是无法解决的。几个月之前，阿隆佐•邱奇在“关于判定性问题的解释”(A Note on the Entscheidungsproblem)一文中证明出了一个相似的论题，但他采用但是递归函数和Lambda可定义函数来形式地描述有效可计算性。Lambda可定义函数由阿隆佐•邱奇和史蒂芬•克林(Stephen Kleene) (Church 1932, 1936a, 1941, Kleene 1935)提出，而递归函数由库尔特•歌德尔(Kurt Gödel)和雅克斯•赫尔不兰特(Jacques Herbrand) (Gödel 1934, Herbrand 1932)提出。这两个机制描述的是同一集合的函数，正如邱奇和克林(Church 1936a, Kleene 1936)所展示的正整数函数那样。在听说了邱奇的建议后，图灵很快就证明了他的图灵机实际上描述的是同一集合的函数(Turing 1936, 263ff).y
本论题之成功
之后用于描述有效计算的许多其他机制也被提了出来，比如寄存器机器(register machine), 埃米尔•波斯特(Emill Post)的波斯特体系，组合可定义性(combinatory definability)以及马尔可夫算法(Markov 1960)等。所有这些体系都已被证明在计算上和图灵机拥有基本相同的能；类似的系统被称为图灵完全。因为所有这些不同的试图描述算法的努力都导致了等价的结果，所以现在普遍认为邱奇-图灵论题是正确的。但是，该论题不具有数学定理一般的地位，也无法被证明；如果能有一个方法能被普遍接受为一个有效的算法但却无法在图灵机上允许，则该论题也是可以被驳斥的。
在20世纪初期，数学家们经常使用一种非正式的说法即可有效计算，所以为这个概念寻找一个好的形式描述也是十分重要的。当代的数学家们则使用图灵可计算(或简写为可计算)这一定义良好的概念。由于这个没有定义的用语在使用中已经淡去，所以如何定义它的问题几经不是那么重要了。
哲学内涵
邱奇-图灵论题对于心智哲学(philosophy of mind)有很多寓意。有很多重要而悬而未决的问题也涵盖了邱奇-图灵论题和物理学之间的关系，还有超计算性(hypercomputation)的可能性。应用到物理学上，该论题有很多可能的意义：
1. 宇宙是一台图灵机(由此，在物理上对非递归函数的计算是不可能的)。此被定义为大邱奇-图灵论题。
2. 宇宙不是一台图灵机(也就是说，物理的定律不是图灵可计算的)，但是不可计算的物理事件却不能阻碍我们来创建 超计算机(hypercomputer)。比如，一个物理上实数作为可计算实数的宇宙就可以被划为此类。
3. 宇宙是一台超计算机, 因为建造物理设备来控制这一特征并来计算非递归函数是可能的。比如，一个悬而未决的问题是量子力学的的事件是图灵可计算的，尽管我们已经证明了任何由qubit所构成的系统都是(最佳)图灵完全的。约翰•卢卡斯(和罗格•本罗泽(Roger Penrose)曾经建议说人的心灵可能是量子超计算的结果。
实际上在这三类之外或其中还有许多其他的技术上的可能性，但这三类只是为了阐述这一概念。
补充材料
• Hofstadter, Douglas R., Gödel, Escher, Bach: an Eternal Golden Braid, Chapter 17.
参考文献
• Church, A., 1932, "A set of Postulates for the Foundation of Logic", Annals of Mathematics, second series, 33, 346-366.
• Church, A., 1936, "An Unsolvable Problem of Elementary Number Theory", American Journal of Mathematics, 58, 345-363.
• Church, A., 1936, "A Note on the Entscheidungsproblem", Journal of Symbolic Logic, 1, 40-41.
• Church, A., 1941, The Calculi of Lambda-Conversion, Princeton: Princeton University Press.
• Gödel, K., 1934, "On Undecidable Propositions of Formal Mathematical Systems", lecture notes taken by Kleene and Rosser at the Institute for Advanced Study, reprinted in Davis, M. (ed.) 1965, The Undecidable, New York: Raven.
• Herbrand, J., 1932, "Sur la non-contradiction de l'arithmetique", Journal fur die reine und angewandte Mathematik, 166, 1-8.
• Kleene, S.C., 1935, "A Theory of Positive Integers in Formal Logic", American Journal of Mathematics, 57, 153-173, 219-244.
• Kleene, S.C., 1936, "Lambda-Definability and Recursiveness", Duke Mathematical Journal 2, 340-353.
• Markov, A.A., 1960, "The Theory of Algorithms", American Mathematical Society Translations, series 2, 15, 1-14.
• Turing, A.M., 1936, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936-37), pp.230-265.
• Pour-El, M.B. & Richards, J.I., 1989, Computability in Analysis and Physics, Springer Verlag.

英国现代计算机的起步的是从纳粹德国的“谜”开始的。“谜”（Enigma）是一种密码电报机，由德国人在一战和二战之间研制成功。“谜”能把日常语言变为代码，通过无线电或电话线路秘密传送。它是一个木箱子，配有一台打字机，箱上有26个闪烁不停的小灯泡，与打字机键盘的26个字母相对应。“谜”的设计无懈可击，有一套极精密的解码设置，非一般的电报密码所能比拟。在内行人看来，平白如话，但在旁人，又是无从索解的天书。因此，这台看似平常的机器，有了“谜”的称号。这样，德国的“谜”引起了英国情报部门高度的兴趣。常规的解码方式奈何不了“谜”，怎么办？

这时，天才的数学家图灵出现了。1931年图灵进入剑桥大学国王学院，开始了他的数学天涯。一到那里，图灵开始崭露头角，毕业后去美国普林斯顿大学攻读博士学位，在那里就发明过一个解码器（Encipher），二战爆发后回到剑桥。

在剑桥，图灵是一个妇孺皆知的怪才，常有出人意表的举动。他每天骑自行车到离公寓3公里的一个叫布雷奇莱公园（Bletchley Park）的地方上班，因常患过敏性鼻炎，一遇花粉，鼻涕不止，图灵就常戴防毒面具骑车上班，招摇过市，成为剑桥的一大奇观。

他的自行车链条经常在半道上掉落，要是换了别人，早就去车铺修理了。而图灵偏不，他在琢磨，发现这链条总是踏到一定的圈数时下滑，图灵在骑车时就特别留心计算，于是能做到在链条下滑前一刹那戛然停车！让旁人叹服不已，以为是在玩杂耍。后来他居然在踏脚旁装了一个小巧的机械计数器，到圈数时就停，好换换脑筋想些别的问题。图灵的脑袋转得比自行车飞轮还快。

用图灵的脑袋来破译德国的“谜”看来不是什么难事。二战爆发后，图灵成为英国外交部通信部门战时公务员，主要负责解码。他果然不负众望，成功破译了“谜”。而德国人还蒙在鼓里，还以为他们的“谜”能一直迷下去，照用不误，泄露了大量的核心机密，在战事上屡屡遭挫，战后，图灵被授予帝国勋章。至于图灵如何破译“谜”的，由于英国政府严格的保密法令，一直没有公之于世。所以图灵破译“谜”也成为一个“谜”。

早在30年代初，图灵就发表了一篇著名的论文《论数字计算在决断难题中的应用》，他提出了一种十分简单但运算能力极强的理想计算装置，用它来计算所有能想象得到的可计算函数。它由一个控制器和一根假设两端无界的工作带组成，工作带起着存储器的作用，它被划分为大小相同的方格，每一格上可书写一个给定字母表上的符号。控制器可以在带上左右移动，控制带有一个读写头，读写头可以读出控制器访问的格子上的符号，也能改写和抹去这一符号。

这一装置只是一种理想的计算模型，或者说是一种理想中的计算机。正如飞机的真正成功得力于空气动力学一样，图灵的这一思想奠定了整个现代计算机的理论基础。这就是电脑史上与“冯·诺依曼机器”齐名的“图灵机”。

图灵机被公认为现代计算机的原型，这台机器可以读入一系列的零和一，这些数字代表了解决某一问题所需要的步骤，按这个步骤走下去，就可以解决某一特定的问题。这种观念在当时是具有革命性意义的，因为即使在50年代的时候，大部分的计算机还只能解决某一特定问题，不是通用的，而图灵机从理论上却是通用机。在图灵看来，这台机器只用保留一些最简单的指令，一个复杂的工作只用把它分解为这几个最简单的操作就可以实现了，在当时他能够具有这样的思想确实是很了不起的。他相信有一个算法可以解决大部分问题，而困难的部分则是如何确定最简单的指令集，怎么样的指令集才是最少的，而且又能顶用，还有一个难点是如何将复杂问题分解为这些指令的问题。

此后图灵在国家物理学实验室（NPL）工作，并继续为数字式计算机努力，在那里人发明了自动计算机（Automatic Computing Engine，ACE），在这一时期他开始探索计算机与自然的关系。他写了一篇名为《智能机》的文章于1969发表，这时便开始有了人工智能的雏形。

图灵相信机器可以模拟人的智力，他也深知让人们接受这一想法的困难，今天仍然有许多人认为人的大脑是不可能用机器模仿的。而在图灵认为，这样的机器一定是存在的。图灵经常和其它科学家发生争论，争论的问题就是机器实现人类智能的问题，在今天我们看来这没有什么，但是在当时这可不太容易被人接受。他经常问他的同事，你们能不能找到一个计算机不能回答的问题，当时计算机处理多选问题已经可以了，可是对于文章的处理还根本不可能，但今天的发展证明了图灵的远见，今天的计算机已经可以读写一些简单的文章了。

图灵相信如果模拟人类大脑的思维就可以做出一台可以思考的机器，它于1950写文章提出了著名的“图灵测试”，测试是让人类考官通过键盘向一个人和一个机器发问，这个考官不知道他现在问的是人还是机器。如果在经过一定时间的提问以后，这位人类考官不能确定谁是人谁是机器，那这个机器就有智力了。这个测试在我们想起来十分简单，可是伟大的思想就源于这种简单的事物之中。

现在已经有软件可以通过图灵测试的子测试，软件这个人类智慧的机器反映应该可以解决一些人类智力的问题。在完成ACE之前，图灵离开了NPL，它在曼彻斯特大学开发曼彻斯特自动计算机（Manchester Automatic Digital Machine，MADAM）。他相信在2000年前一定可以制造出可以模拟人类智力的机器，图灵开始创立算法，并使用MADAM继续他的工作。

图灵对生物也十分感兴趣，他希望了解生物的各个器官为什么是这个样子而不是那个样子，他不相信达尔文的进化论，他觉得生物的发展与进化没什么关系。对于生物学，他也用它钟爱的数学进行研究，它的研究对他进行计算机的研究有促进作用。它把生物的变化也看做是一种程序，也就是图灵机的基本概念，按程序进行。最后，这位伟大的计算机先驱于1954年6月7日去世，他终生未娶。

查尔斯·霍尔

                   ---从QUICKSORT、CASE到程序设计语言程序设计语言的公理化

    学过“数据结构”或“算法设计与分析”的人都知道著名的快速排序算法QUICKSORT；编过程序的人大概也都用过实现条件转移的最方便的语句CASE语句。但是你知道这个算法和这个语句是谁发明的吗?它们的发明者就是1990年IEEE计算机先驱奖和1980年图灵奖的获得者英国牛津大学计算机科学家查尔斯·霍尔(Charles AntonyRichard Hoare)。当然霍尔之所以获得这两项大奖决不仅仅是因为他发明了QUICKSORT和CASE，而是因为他在计算机科学技术的发展中，尤其是在程序设计语言的定义和设计、数据结构和算法、操作系统等许多方面都起了重要的作用，有一系列发明创造，QUICKSORT和CASE只是其中的一小部分而已。

    霍尔于1934年1月11日诞生于英国南部。在坎特伯雷(Canter·bury)的国王学校(King’s Sch001)度过中学阶段以后，进入牛津的莫顿学院(Merton College)学习数学，1960年取得硕士学位。之后他进入伦敦一家不大的计算机生产厂家Elliott Brothers公司，为该公司的Elliott 803计算机编写库子程序，从此开始他的计算机生涯。QUICK，SORT就是他在那个时候用原有的SHELLSORT(以算法的发明人D．L．Shell命名的通过调换并移动数据项实现排序的一种算法，发明于1959年)编程时分析了它的缺点而发明出来的。QUICKSORT具有“快刀斩乱麻”的特点，能迅速地对乱序作大幅度调整，特别适合于因多次追加、删除而变得杂乱无章的数据集合。QUICKSORT是利用“分治法”(divide and conquer)进行算法设计的一个成功范例，它的发明是霍尔在计算机方面的天才的第一次显露，受到老板的赞赏和重视。第二年，霍尔接受了一个新的任务，为公司的新机型Elliott 503设计一个新的高级语言。但就在其时，他弄到了一份Algol 60报告的复印件，还参加了一个由狄克斯特拉(E．W．D耻stra，首届计算机先驱奖获得者)等人在布赖顿举办的Algol 60培训班，感到与其自己没有把握地去设计一个新的语言，还不如将比较成熟的Algol 60在Elliott 503上加以实现。霍尔和他的同事们的这个想法获得公司同意以后，由霍尔主持设计与实现了Algol 60的一个子集的版本。霍尔在开发初首先制定了明确的目标，即系统要安全可靠，生成的目标码要简洁，工作区数据要紧凑，过程和函数的人口和出口要清晰、严密等，还明确了整个编译过程采用一次扫描等原则。这样，ElliottAl-gol的开发十分顺利与成功，它在1963年中推出以后大受欢迎，成为世界各国所开发的Algol 60的各种版本中在效率、可靠性和方便性等方面的性能指标都首屈一指的一个版本，霍尔本人也从此受到国际学术界的重视。国际信息处理联盟IFIP后来任命霍尔为2．1工作组(WorkingGroup 2．1)的负责人，这个工作组的任务是维护和发展Algol。霍尔果然不负众望，主持设计了Algol X以继承与发展Algol60。正是在AlgolX的设计中，霍尔发明了CASE语句。CASE语句具有如下形式的语法结构：

CASE E of

C1:S1；

C2:S2；

.

.

.

Cn-1:Sn-1;

Otherwise:Sn

End

其中E是一个表达式，称为“选择子”(Selector)，每个Ci的值为常数，称为“分情形标号”，Si则为可执行语句。CASE语句的含义是：若E的值等于某个Ci的值，则执行其后的Si(i=1，2，3，…，n—1)，否则执行Sn。某个Si或S。执行完之后，整个CASE语句也就执行完毕。由于CASE语句构成多路分支，程序结构清晰、直观，所以CASE语句后来几乎成为程序设计语言的标准，被各种语言广泛采用。在C语言中，没有独立的CASE语句，但它的SWITCH语句(开关语句)实际上是在CASE语句的基础上形成的：

switch E

{case C1:S1；

case C2:S2；

.

.

.

case Cn-1:Sn-1;

[default:Sn]

  不同之处有二：一是C；可以是表达式，但计算结果必须仍是常数；二是E的结果若不等于某个Ci(i=1，2，3，…，n—1)的值，则视有无default子句，若有，执行Sn；若无，则什么也不执行，控制转向SWITCH后的语句。显然，这些都是对CASE语句的进一步改进。

  霍尔于1968年离开Elliott，离开产业界，原因是作为学者他对程序设计浯言的形式化定义这类更偏重于学术性和理论性的课题更感兴趣。离开Elliott以后，他任职过一年英国国家计算中心主任，发现自己也不适于从事行政管理，因此又转入爱尔兰的昆土大学(Queen’s University)，从事教学和研究，1977年转入牛津大学。离开Elliott以后，霍尔在计算机科学理论的研究中发挥其特长，作出了许多创造性的重大贡献。首先是1969年10月，霍尔在Communications of ACM上发表了他那篇有里程碑意义的论文“计算机程序设计的公理基础”(An Axiomatic Basis for Computer Programming)。在这篇论文中，霍尔提出了程序设计语言的公理化定义方法，即公理语义学(axiomatic semantics)，也就是用一组公理和一组规则描写语言应有的性质，从而使语言与具体实现的机器无关，而且也易于证明程序的正确性。这是继麦卡锡(J．McCarthy，1985年计算机先驱奖获得者)在1963年提出用递归函数定义程序、弗洛伊德(R．W．Floyd，1991年计算机先驱奖获得者)在1967年提出基于程序流程图的归纳断言法以后，在程序逻辑研究中所取得的又一个重大技术进展。霍尔提出的方法在逻辑上与弗洛伊德提出的方法类似，但不是用流程图而是用代数法，即控制流用以下一些结构表示：

    begin al；a2；a3；…；an end

    if p then a1 else a2

    while p do a

    后面为了方便，我们用到第一个结构时省略首尾的begin和end。

    相应于弗洛伊德的验证条件，霍尔引入下列符号：

    p{a}q

    其意义是：如果在执行。之前P(叫做precondition)成立，则当α执行完了后q(叫做postcondition)成立。

    霍尔给出了以下一组证明规则(proof rule)或叫推导规则：

       p’ pp{a}qq→q’

    1.

          p’{a}q’

    这个规则中的p’→和q’→q是普通数理逻辑中的断言命题，表示若p’(或q’)成立，则p(或q)成立。这个规则表示，若横线以上的p’→p、p{a}q、q→q’成立，则横线以下的p’{a}q1成立。

2．

   P(e){x:=e}p(x)

这个规则表示，如果在将e赋给x之前p(e)成立，则其后p(x)成立。

3． P{a}qq{b}r

    p{a;b}r

    这个规则表示的是“传递律”(transitive law)，即如果执行α之前p成立，α执行完了以后q成立；而如果执行b之前q成立，b执行完了以后r成立，则若在动作序列。和^执行之前P成立，则a和b执行完了以后r成立。

   4.   p∧r{a}qp∧～r(b)q

       p{if r then a else b}q

    这个规则中的∧和～是一般数理逻辑中的合取(conjunction)和否定(negation)连接词。这个规则定义了if-then-else的执行取决于precondition r的值。

5.        p∧q{a}p

     p{while q do a}p∧～q

    这个规则定义了while循环：p是循环不变量（loop invariant），而q是终止循环的条件。

    下面我们举一个例子说明如何用霍尔建立的系统验证程序的正确性。设有计算n的阶乘n！的如下程序：

A: x:1;B

B: while y>0 do C

C: x:y×x;y:=y-1

    则通过下列霍尔断言可以证明上述程序是正确的，因为这些断言都是真的，而且在霍尔的系统中是可以被证明的，而最后一个断言正是我们所要寻求的结论，因此它们形成对上述阶乘程序正确性的说明。

i.  y>0∧x×y! =n! {x:=y×x}y>0∧x×(y-1)! =n!

[首先y>0∧x×y! =n!→y>0∧(y×x)×(y-1)! =n!]

然后用规则（2），用x代替y×x]

ii. y>0∧x×(y-1)! =n!{y:=y-1}y≥0∧x×y! =n!

    [类似（i），利用规则（2）]

iii．y>0∧x×y! =n! {C}y≤0∧x×y! =n!

[对(i)和(ii)用规则(3)]

iv．Y≥0∧y=n∧x=1{B}x=n!

[因为] y=n∧x=1→x×y! =n!

又因为0！ =1，所以Y≥0∧x×y! =n! ∧y≤0→y=0∧x=n! →x×y! =n!

根据（iii），利用规则（5），令（5）中p=y≤0∧x×y! =n!，q=y>0，孥可得(iv)]

v.  y≥0∧y=n{x:=1}y≥0∧y!=n∧x=1

[因为p{x:=1}p∧x=1]

vi. y≥0∧y=n{A}x=n!

[对（V）和(Vi)利用规则(3)]

    因为(vi)中的precondition正好是n的初始条件，而postcondition给出了所需结果，这样就证明了程序可算出n!。

    为了给出证明，应该从程序的最后一行开始逐步后推。在这个例子中，(iii)步是最关键的，其中y≥0∧x×y! =n!就是循环不变量或归纳假设(induction hypothesis)。

    利用霍尔提出的这种方法，已经成功地描述了PASCAL等语言，说明了这个方法的巨大威力。但应该指出的是，霍尔的这个方法是不完备的，因为霍尔在开发和建立这个系统时并没有追求系统的完备性，而更多地追求系统的实用性。

    在数据类型、数据结构和操作系统设计等方面，霍尔也做了许多开创性的工作。目前广泛流行与应用着的许多概念都源于霍尔的工作。例如，关于抽象数据类型的规格说明(Specification，也叫规约)与其实现是否一致，就是由霍尔于1972年公式化了的。霍尔通过前后断言方法用已经定义了的(抽象)数据类型给出所要定义的新类型的抽象模型，这成为抽象数据类型规格说明的两种主要方法之一，即模型方法(另一方法为基于异调代数理论的代数方法)。对于操作系统的设计与实现十分关键的monitor(监控程序)的概念也是霍尔首先提出，并界定了它的作用与功能，即作为操作系统的核心，在把操作系统看做虚拟机扩充时，monitor是硬件的第一次扩充，它完成中断处理、进程控制与进程通信、存储区动态分配，建立软时钟，驱动设备通道，进行处理机调度。monitor为外面各层的设计提供良好的环境，并提高系统的安全性。

    20世纪70年代后期，霍尔又深入研究了运行在不同的机器上的若干个程序之间如何互相通信、互相交换数据的问题，实现了面向分布式系统的程序设计语言CSP。在该语言中，一个并发系统由若干并行运行的顺序进程组成，每个进程不能对其他进程的变量赋值。进程之间只能通过一对通信原语实现协作：Q?x表示从进程Q输入一个值到变量x中；P!e表示把表达式e的值发送给进程户。当户进程执行Q?x，同时口进程执行户!‘时，发生通信，e的值从Q进程传送给户进程的变量x。CSP语言后来成为著名的并行处理语言OCCAM(由INMOS公司为Transputer开发)的基础。20世纪80年代中期，霍尔又和布鲁克斯(S．Brooks)等人合作，提出了“CSP理论”TCSP(Theory Of Communicating Sequential Processes)，它与上述CSP不同，但又有联系，这是一个代数演算系统，其基本成分是事件(或动作)。进程由事件和一组算子构造而成。TCSP采用“广播式通信”，而不像程序设计语言CSP中那样采用握手式通信，即只有当并行运行的各进程都执行同一动作时，才发生通信。此外，TCSP采用失败等价作为确定进程等价的准则，这就是著名的“失败语义”。利用失败可以构造TCSP的指称模型。霍尔为失败等价建立了一些公理系统，可以对语义上的等价关系进行形式推导。霍尔在这方面的工作开创了用代数方法研究通信并发系统的先河，形成了所谓“进程代数”(process algebra)这一新的研究领域，产生了很重要的影响。

    霍尔的论著极多，而且都很有份量，有很高的学术水平。有评论说，霍尔每发表一篇论文，几乎就要改变一次人们对程序设计的认识。这虽然是一种夸张的说法，但也说明霍尔的论著确实非常重要。ACM在1983年评选出最近四分之一个世纪中发表在Communications of ACM上的有里程碑式意义的25篇经典论文，只有两名学者各有2篇论文人选，霍尔就是其中之一(另一名是首届计算机先驱奖获得者狄克斯特拉)。霍尔人选的两篇论文分别是1969年10月的“计算机程序设计的公理基础”(An Axiomatic Basis for Computer Programming，这篇论文的要点我们前面已经介绍过了)，另一篇是1978年8月的“通信顺序进程”(Communicating Sequential Processes)，该论文奠定了前述CSP语言的基础。CSP现在已推广为“混合通信／顷序进程”(Hybrid Communicating Sequential Processes)。在这个语言中，有一种特殊的语句称为“连续构件”，可表示一个具体给定初值的微分方程；而原有的通信语句可用来表达事件的起源和发生；语言中的顺序算子、条件算子等则用来刻画连续构件和通信间的耦合关系。

    值得指出的是，霍尔还和我国软件学者、中国科学院软件所的周巢尘研究员等合作，在20世纪80年代末由于Esprit的ProCos项目的需要而对基于时态逻辑的逻辑型混合计算模型进行了研究，在这个模型中引入了时段和切变的概念，建立了时段演算，已引起该领域同行的广泛重视。时段用以刻画系统在一个时间区间上的连续变化，而切变则表示事件的发生(离散变量的变化)。在单个时段上，借助连续数学(微分方程理论)推导系统的行为；而在相邻时段间，则用时态逻辑中切变算子的规则，推导系统行为的转化。这种混合计算模型对于设计要求绝对安全的软件系统具有十分重大的意义。时段演算已在煤气燃烧器、铁路岔口控制、水位控制、自动导航、OCCAM语言的实时语义、描述调度程序的实时行为和电路设计等方面获得成功应用。

    此外，由法国学者阿勃利尔(J．R．Abrial)提出的以状态机为模型的著名的形式规约语言Z语言，也是由霍尔所领导的研究小组加以发展并实现的。

  霍尔出版的专著主要有以下几种：

  《操作系统技术》(Operating Systems Techniques，Academic Pr.,1972)

    《数理逻辑和程序设计语言》(Mathematical Logic and Programming language，Prentice—Hall，1985)

  《并发和通信的发展》(Development in  Concurrency and Communication，Addison-Wesley，1990)

  《机器推理和硬件设计》(Mechanized Reasoning and Hardware Design，Prentice·Hall，1992)

    除了获得计算机先驱奖和图灵奖以外，霍尔还在1981年获得AFIPS的Harry Goode奖；1985年获得英国IEE的法拉第奖章。霍尔曾应邀到过世界的许多国家讲学，中国科学院研究生院也曾于1983年邀请霍尔到北京讲学，并主办讨论班。1989年霍尔当选为欧洲科学院院士。1992年新加坡政府授予霍尔“李光耀优秀访问学者”称号。在2000年北京WCC大会上，霍尔应邀作了主题报告。

  顺便提一下，霍尔所开创的进程代数，我国学者给予了高度重视和深入研究，并有创新。国防科技大学李舟军博土已撰写出《进程代数导论——理论及应用》一书，被列入“中创软件丛书"2001年度计划即将出版。