不确定性的困惑与NP理论分享 http://blog.sciencenet.cn/u/liuyu2205 平常心是道

博文

数学基础的危机与计算机理论的诞生 - 图灵的壮举 精选

已有 7121 次阅读 2021-6-14 03:18 |个人分类:不确定性问题和算法讨论|系统分类:观点评述

图灵的论著和工作为计算机理论的诞生奠定了基础,为了理解这一壮举的背景,需要回顾20世纪初那场著名的数学基础危机。


一,数学基础危机1


对于数学基础的关注和研究,可追溯至古代,但在较长的历史阶段中,基本上只限于对单科数学基础的讨论,至于作为整个数学基础的探索,乃是20世纪初的事,缘起于非欧几何的诞生。


欧几里得(325年-前265)的《几何原本》一直被认为是最早用严格的逻辑结构建立学科体系的典范,但其不足之处也一直为历代学者所关心,其中一个具有争议的议题是第五公设,长达两千年之久所有企图推导出此公设的努力都失败,却促成了非欧几何的建立,引起了数学基础的重大危机,其核心问题涉及到:在什么终极基础上命题可以称为”?


在人们寻找解决方案时,不得不将真实性可证性脱钩:欧几里得几何公理系统的所有定理是可证的,而且符合我们对空间的传统直觉,但仍然不是真实的,换句话说,欧几里得几何学的合法性突然变得有问题。当然,证明仍然是检验新定理有效性的标准,但人们不能再仅依赖公理系统的论证了。


康托尔(1845-1916)正是为了给这些令人不安的发展提供一个明确的解决方案,发展了著名的集合论。由于他的开创性工作,使整个数学大厦有了新的基础,天空似乎又开始晴朗了。不幸的是,在康托里理论本身中很快就发现了悖论。


于是,出现了三个相互竞争的数学流派,旨在应对这场危机。


二,逻辑主义,形式主义与直觉主义【2


1,逻辑主义


逻辑主义试图将数学归结为逻辑,使其受益于逻辑的严谨性,认为数的性质是推导出来的。这是英国哲学家和数学家罗素(1872-1970)与他以前的老师怀特海(1861-1947)合作进行的雄心勃勃的计划,整理在三卷本的《数学原理》(Principia Mathematica)中


2,形式主义


形式主义认为数学是一种智力游戏,在所开发的一系列操作中,数学家不必担心他所操作的符号的性质,对他来说唯一重要的是公理系统的一致性,完备性和可判定性。这一立场是由德国数学家希尔伯特(1862-1943)提出的,表达在著名的希尔伯特计划”和“希尔伯特的23个问题”中


3,直觉主义


直觉主义倡导将数学建立在算术的基础上,认为算术是人类思维的自由创造和对时间的原始直觉的产物,拒绝某些经典的推理类型,因为它们在应用于无限集时导致矛盾。直觉主义的代表人物荷兰数学家布劳威尔Brouwer1881-1966),为各种构造主义铺平了道路。


三,图灵的贡献


这时年轻的图灵(1912-1954)出场了,投身于这场备受争议的数学基础问题中。图灵受过严格的数学训练并精通逻辑,对于逻辑主义,按照他的说法,数是一个原始的数据,不能被还原为集合的特征。在这一点上,他同意直觉主义,只是他不能接受这个学派对数学世界的截断。在1935年的春天,22岁的他报名参加了形式主义的信徒麦克斯-纽曼(Maxwell Newman1897-1984)在剑桥大学开设的课程:


- 麦克斯-纽曼名声在外的是他在组合拓扑方面的工作,不过他也可能是剑桥大学在数理逻辑方面最有见识的人。纽曼整个课程的高潮是对哥德尔不完备性定理的证明。3


- 此外,纽曼的课程也涵盖了尚未解决的“判定问题”(Entscheidungsproblem):是否有一种确定的方法,或者纽曼所说的机械过程,它可以应用于一个数学命题,并得出该命题能否被证明的结论?当然,对于机械过程,纽曼指的不是一台机器。机器也许能够进行简单的算术,但几乎不能解决实际意义的数学问题。纽曼暗指的是后人称为算法的一类过程 - 用于解决某个问题的一组明确(但无意识,非智能的)指令集。图灵开始研究判定问题,很可能是在1935年初夏。那时,他已经获得了剑桥大学奖学金,每年300英镑。图灵后来说,想到判定问题的解决思路时,他正躺在格兰切斯特草坪上,这是剑桥学生很喜欢的一个休闲场所,距国王学院大约两英里。3


19364月,图灵把论文论可计算数及其在判定性问题上的应用的草稿交给了纽曼,开启了理论计算机的先河,。。。


参考文献:

1https://baike.baidu.com/item/数学基础

2Jean-Claude SimardPuis Turing vint… https://www.acfas.ca/publications/magazine/2015/02/puis-turing-vint

3Charles Petzold, “图灵的秘密” - 他的生平,思想及论文解读。




https://blog.sciencenet.cn/blog-2322490-1291056.html

上一篇:真数学命题从何而来?- Paul Jorion的书第四章“毕达哥拉斯的复仇:当代数学”译文
下一篇:数学中的三个危机 :逻辑主义、直觉主义和形式主义 - 译文(1):逻辑主义
收藏 IP: 91.165.191.*| 热度|

8 张学文 彭真明 杨正瓴 黄永义 吴国林 闵应骅 武爱 段玉聪

该博文允许注册用户评论 请点击登录 评论 (0 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-10-4 07:21

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部