图灵的论著和工作为计算机理论的诞生奠定了基础，为了理解这一壮举的背景，需要回顾20世纪初那场著名的数学基础危机。
对于数学基础的关注和研究，可追溯至古代，但在较长的历史阶段中，基本上只限于对单科数学基础的讨论，至于作为整个数学基础的探索，乃是20世纪初的事，缘起于非欧几里得几何的诞生。
欧几里得（Euclid）的《几何原本》一直被认为是最早用严格的逻辑结构建立学科体系的典范，但其不足之处也一直为历代学者所关心，其中一个具有争议的议题是第五公设，长达两千年之久所有企图推导出此公设的努力都失败，却促成了非欧几何的建立，引起了数学基础的重大危机，其核心问题涉及到：在什么终极基础上命题可以称为“真”?在人们寻找解决方案时，不得不将“真实性”和“可证性”脱钩：欧几里得几何公理系统的所有定理是“可证的”，而且符合我们对空间的传统直觉，但仍然不是“真实的”，换句话说，欧几里得几何学的合法性突然变得有问题。当然，证明仍然是检验新定理有效性的标准，但人们不能再依赖公理系统的论证。
康托尔（1845-1916）正是为了给这些令人不安的发展提供一个明确的解决方案，发展了著名的集合论。由于他的开创性工作，使整个数学大厦有了新的基础，天空似乎又开始晴朗了。不幸的是，在康托里理论本身中很快就发现了悖论。
于是，出现了三个相互竞争的数学流派，旨在应对这场危机。
一，逻辑主义，形式主义与直觉主义【1】1，逻辑主义逻辑主义试图将数学归结为逻辑，使其受益于逻辑的严谨性，认为数的性质是推导出来的。这是英国哲学家和数学家罗素（1872-1970）与他以前的老师怀特海（1861-1947）合作进行的巨大计划。
2，形式主义形式主义认为数学是一种智力游戏，在所开发的一系列操作中，数学家不必担心他所操作的符号的性质：对他来说唯一重要的是命题的非矛盾性和证明的一致性。数学家不必起始公理是真还是假，而只需问公理是否一致和完整。这一立场是由德国数学家希尔伯特（1862-1943）提出的，表达为著名的“希尔伯特计划”。
3，直觉主义直觉主义倡导将数学建立在算术的基础上，认为算术是人类头脑创造性自由和对时间的原始直觉基础上的产物，拒绝某些经典的推理类型，因为它们在应用于无限集时导致矛盾。直觉主义的代表人物荷兰数学家Brouwer（1881-1966），为各种构造主义铺平了道路。
二，图灵与“论可计算数及其在判定性问题上的应用”论文【2】这时图灵（1912-1954）出场了，投身于备受争议的数学基础问题中。图灵受过数学训练并精通逻辑，对于逻辑主义，按照他的说法，数是一个原始的数据，不能被还原为集合的特征。在这一点上，他同意直觉主义，只是他不能接受这个学派对数学世界的截断。在1935年春天，22岁的他报名参加了形式主义的信徒麦克斯-纽曼(Maxwell Newman，1897-1984)
在剑桥大学开设的课程。
麦克斯-纽曼名声在外的是他在组合拓扑方面的工作，不过他也可能是剑桥大学在数理逻辑方面最有见识的人。纽曼整个课程的高潮是对哥德尔不完备性定理的证明。
此外，纽曼的课程也涵盖了尚未解决的判定性问题。
“是否有一种确定的方法，或者纽曼所说的’机械过程’，它可以应用于一个数学命题，并得出该命题能否被证明的结论？
”当然，对于“机械过程”，纽曼指的不是一台机器。机器也许能够进行简单的算术，但几乎不能解决实际意义的数学问题。纽曼暗指的是后人称为“算法”的一类过程- 用于解决某个问题的一组明确（但无意识，非智能的）指令集。图灵开始研究判定性问题，很可能是在1935年初夏。那时，他已经获得了剑桥大学奖学金，每年300英镑。图灵后来说，想到判定性问题的解决思路时，他正躺在格兰切斯特草坪上，这是剑桥学生很喜欢的一个休闲场所，距国王学院大约两英里。
到1936年4月，图灵把论文“论可计算数及其在判定性问题上的应用”的草稿交给了纽曼，开启了理论计算机的先河，。。。
评论 (0)