书名：皇帝新脑（第一推动丛书·综合系列）
作者：罗杰·彭罗斯
译者：许明贤,吴忠超
出版社：湖南科学技术出版社
出版时间：2018-01-01
ISBN：9787535794444
第4章 真理、证明和洞察
- 数学的希尔伯特计划
- 形式数学系统
- 哥德尔定理
- 数学洞察
- 柏拉图主义或直觉主义
- 从图灵结果到类哥德尔定理
- 递归可列集
- 芒德布罗集是递归的吗
- 一些非递归数学的例子
- 芒德布罗集像非递归数学吗
- 复杂性理论
- 物理事物中的复杂性和可计算性
一、数学的希尔伯特计划
1、三个问题
什么是真理？
我们如何对世界的真假形成判断呢？
我们是否简单地遵循着某些算法？
这种算法由于自然选择的强有力的过程无疑地比其他效率更低的可能算法更加优越。
或许还有其他探索真理的非算法的途径——直觉、禀性或洞察。这似乎是一个困难的问题。
我们的判断是基于感觉数据、推理和猜测的盘根错节的结合。
而且，在世间的许多情势中也许并没有何为真何为假的共识。
2、简化问题
- 为了使问题简化，让我们只考虑数学真理。
我们如何形成自己关于数学问题的判断或许“某些”知识呢？
在这儿事情至少应该是更明了些。
关于究竟什么为真什么为假在这里不应成为问题——难道会有问题吗？
究竟什么是数学的真理呢？
3、数学的真理
- 数学的真理是一个非常古老的问题，这可回溯到早期的希腊哲学家和数学家的时代——并毫无疑问地比这还要更早。
- 但是，只有在100多年前人们才刚刚获得了一些伟大的彻悟以及令人眼花缭乱的新的洞察。
- 我们想要理解的正是这些非常基本的问题。
- 它正好触及了我们的思维过程在本质上是不是完全算法的问题。
- 议定这些问题是非常重要的。
4、数学的进展（无穷集合系统）
- 数学在19世纪下半叶有了伟大的进展，其部分原因在于人们发展了数学证明的越来越有力的方法。
- 数学家大卫·希尔伯特和乔治·康托尔、亨利·庞加莱
- 数学家在利用如此有力的方法时相应地获得自信心。
- 其中许多方法涉及去考虑具有无穷多元素的集合。
正是由于可能将这样的集合当成实在的“东西”—完全存在的整体，而不仅仅为潜在的存在，使证明经常得到成功。
这许多强有力的观念是从康托尔的高度创造性的无穷数的概念中孕育而来的。
他利用无穷集合系统地发展了这一切。
5、罗素悖论
- 然而，1902年英国逻辑学家兼哲学家贝特朗·罗素提出其著名的悖论，完全粉碎了这种自信心。
- 罗素悖论又是怎么回事呢？它是关于以如下方式定义的集合R：
R为一切不是自身元素的集合的集合。
这样，R是集合的某一整体；
集X属于该整体的判据是集X自身不是它自身的成员。 - 罗素的概念又如何导致悖论呢？
我们问：罗素集合是它自身的一个成员或者不是它的成员？- 如果它不是它自身的成员，则它必须属于R，因为R刚好包括那些不是自身成员的集合。这样，R毕竟属于R—这是矛盾。
- 另一方面，如果R是它的一个成员，那么由于“自身”实际上就是R，它就属于由自身并非其成员所表征的集合中，也就是它根本不是自身的成员——又导致矛盾!
6、希尔伯特宏伟计划的破灭
伟大的数学家大卫·希尔伯特致力于一个更可行更广泛的计划。
它囊括了所有特殊领域的一切正确的数学推理类型。
而且，希尔伯特倾向于认为，有可能证明该计划免于矛盾冲突。
那么数学就一劳永逸地处于无可争辩的安全基础之上。1931年25岁的奥地利天才、数理逻辑学家库尔特· 哥德尔提出了一个实质上摧毁了希尔伯特计划的令人震惊的定理，使得希尔伯特及其追随者的希望落空。
哥德尔指出的是，任何精确（“形式的”）数学的公理和步骤法则系统，只要它大到足以包含简单算术命题的描述（诸如“费马大定理”），并且其中没有矛盾，则必然包含某些用该系统内所允许的方法既不能证实也不能证伪的陈述。
这种陈述的真理性以可允许的步骤是“不能判定的”。哥德尔能够向我们证明，公理系统本身的协调性的陈述被编码成适当的算术命题后，必定成为一个这种“不能判定的”命题。
哥德尔的论证使我们能用直觉去超越所考虑的任何个别的形式化的数学系统的局限。
