书名:皇帝新脑(第一推动丛书·综合系列)
作者:罗杰·彭罗斯
译者:许明贤,吴忠超
出版社:湖南科学技术出版社
出版时间:2018-01-01
ISBN:9787535794444
第4章 真理、证明和洞察
- 数学的希尔伯特计划
- 形式数学系统
- 哥德尔定理
- 数学洞察
- 柏拉图主义或直觉主义
- 从图灵结果到类哥德尔定理
- 递归可列集
- 芒德布罗集是递归的吗
- 一些非递归数学的例子
- 芒德布罗集像非递归数学吗
- 复杂性理论
- 物理事物中的复杂性和可计算性
八、芒德布罗集是递归的吗
非递归集必须具有这样的性质,即它们在非常本质的方式上是复杂的。
在某种意义上看,它们的复杂性应当公然抵抗任何系统化的企图,否则该系统化就会导致某种适当的算法步骤。对于一个非递归的集合,不存在一般的算法的方式去决定一个元素(或一“点”)是否属于这个集合。
我们见证到一个非同寻常地复杂的集合,也就是芒德布罗集。
虽然提供其定义的规则是令人吃惊地简单,但集合本身却呈现出高度繁复的结构和无穷的变化。在一定的意义上讲,芒德布罗集的补集(也就是白的区域)是递归可数的。
九、一些非递归数学的例子
- 在许多数学分支中产生了非递归的问题。
也就是说,我们会遇到一系列的问题,它们答案或者为“是”或者为“非”,但是不存在决定究竟是什么答案的一般算法。
在这类问题中有一些显得非常简单。
1、丢番图方程
- 求整系数代数方程组的整数解的问题。这种方程称为丢番图方程。
问题在于决定它们是否有x, y, z的整数值的解。
在给定的特殊情况下,事实上存在x=13, y=7, z=2的解。
2、用多边形来覆盖欧几里得平面的问题。
允许用有限种不同形状的花砖,看看是否能将整个平面既没有裂缝又没有重叠地覆盖住。这种用多边形来铺满平面的方法称为平面的镶嵌。
可以只用正方形或正三角形或正六边形来镶嵌,但是不能只用正五边形。
1961年美籍华人逻辑学家王浩提出了对于镶嵌问题是否存在一个判定过程的问题,也就是说,是否存在一种算法,它可以判定给定的不同多边形的有限集合能否将整个平面镶嵌。