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

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

ID:29996214

大小:70.54 KB

页数:5页

时间:2018-12-25

计算的极限(零):逻辑与图灵机_第1页
计算的极限(零):逻辑与图灵机_第2页
计算的极限(零):逻辑与图灵机_第3页
计算的极限(零):逻辑与图灵机_第4页
计算的极限(零):逻辑与图灵机_第5页
资源描述:

《计算的极限(零):逻辑与图灵机》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库

1、计算的极限(零):逻辑与图灵机Comments>>方弦发表于2012-07-1706:45

2、Tags标签:原创,哥德尔不完备定理,图灵机【提出问题和解决问题的人】2012,图灵诞辰100周年,献给这位伟大的开拓者。计算无处不在。走进一个机房,在服务器排成的一道道墙之间,听着风扇的鼓噪,似乎能嗅出0和1在CPU和内存之间不间断的流动。从算筹算盘,到今天的计算机,我们用作计算的工具终于开始量到质的飞跃。计算机能做的事情越来越多,甚至超越了它们的制造者。上个世纪末,深蓝凭借前所未有的搜索和判断棋局的能力,成为第一台战胜人类国际象棋世界冠军的计算机,但它的胜利仍然仰仗于人类大师赋

3、予的丰富国际象棋知识;而仅仅十余年后,Watson却已经能凭借自己的算法,先“理解”问题,然后有的放矢地在海量的数据库中寻找关联的答案。长此以往,工具将必在更多的方面超越它的制造者。而这一切,都来源于越来越精巧的计算。计算似乎无所不能,宛如新的上帝。但即使是这位“上帝”,也逃不脱逻辑设定的界限。第一位发现这一点的,便是图灵。一切从逻辑开始1900年的巴黎,在世纪交替之际,希尔伯特提出了他著名的23个问题。其中第二个问题——算术系统的相容性——正是他那雄心勃勃的“希尔伯特计划”的最后一步。这位数学界的巨人,打算让整个数学体系矗立在一个坚实的地基上,一劳永逸地解决所有关于对数

4、学可靠性的种种疑问。一切都为了回答三个问题:数学是完备的吗?也就是说,面对那些正确的数学陈述,我们是否总能找出一个证明?数学真理是否总能被证明?数学是一致的吗?也就是说,数学是否前后一致,不会得出某个数学陈述又对又不对的结论?数学是否没有内部矛盾?数学是可判定的吗?也就是说,能够找到一种方法,仅仅通过机械化的计算,就能判定某个数学陈述是对是错?数学证明能否机械化?希尔伯特明确提出这三个问题时,已是28年后的1928年。在这28年间,数学界在算术系统的相容性上没有多少进展。但希尔伯特没有等太久,仅仅三年后,哥德尔就得到了前两个问题的答案,尽管这个答案不是希尔伯特所希望看到的

5、。哥德尔的答案分两部分。第一,任何包含了算术的数学系统都不可能同时拥有完备性和一致性,也就是说,如果一个数学系统包含了算术的话,要么它是自相矛盾的,要么存在一些命题,它们是真的,但我们却无法证明。这说明,希尔伯特的前两个问题不可能同时为真。在这里,“算术”有着精确的含义,就是皮亚诺公理,一组描述了自然数的公理。第二,任何包含了算术的数学系统,如果它是一致的,那么我们不能在它的内部证明它本身的一致性。这说明,我们没有希望解决第二个问题。这就是著名的哥德尔不完备性定理,与其说它回答了希尔伯特的前两个问题,不如说它阐述了为什么我们根本不可能解决这两个问题。哥德尔的证明非常精巧。

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

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

8、形式地证明这个命题,这就是一阶谓词演算的完备性。在一阶谓词演算中,真理总能被证明。在这个弱得多的逻辑系统中,我们有了完备性,真的命题必定可以被证明。那么,它是不是可判定的?我们能不能找到一种机械计算的方法,判定其中数学陈述的对错?数学称述的真假,是否可判定的?这个问题,就是希尔伯特的可判定性问题。注:希望更深入了解哥德尔不完备性定理的读者,可以重温旧文《希尔伯特之梦,以及梦的破灭》复杂的简单机器在纽曼教授的数理逻辑课上,图灵第一次听到希尔伯特的可判定性问题以及哥德尔不完备性定理。那是1935年的春天,他刚刚完成在剑桥国王学院的

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。