GÖDEL, ESCHER, BACH
2025-05-27
哥德尔不完备定理
数论的所有一致的公理化形式系统都包含有不可判定的命题。
- 数论 - 能够表达基本运算的系统
- 一致的 - 这个系统不能有互相矛盾的命题
- 公理化形式系统 - 由有限或可枚举的公理集合构成，基于符号、规则、逻辑，是形式化的
- 不可判定的命题 - 系统无法证明这个命题为真还是假
有一个命题G
“这个命题 G 在系统 F 中是不可证的。”
G ≡ G不可证
情况一：如果在系统中证明了G，则矛盾，因为这证明了一个不可证明的命题
情况二：如果不能证明，则 G = 真
所以，G是真的，但是系统无法证明，系统是不完备的
这即是一个古老的哲学悖论数论形式——“我在说谎。”
WU谜题
给定 WJ ，推导出 WU
规则
I. J 结尾 → 加 U
II. Wx → Wxx
III. JJJ → U
IV. UU → 删除
推理
- 从 WJ 推理，通过 规则I 得到 WJU ，通过 规则II 得到 WJJ。
- 从 WJU 推理，通过 规则II 得到 WJUJU
从 WJJ 推理，通过 规则I 得到 WJJU ；通过 规则II 得到 WJJJJ - 从 WJUJU 推理，… 从 WJJU 推理，… 从 WJJJJ 推理，…
以上包含了所有考虑的情况。同时从 WU 倒推可知，需要构造出 WUUU 或是 WJJJ ，尝试继续列举，希望不大，开始寻找不变量以证明无解——如果在所有规则中，有一个始终不变的性质，而这个性质与目标矛盾，遂证目标不可达。
思路1 规则III 是一个 JJJ → U 的转换，所以可以构造一个三倍关系。
令 f(s) = count(J) + 3 * count(U)；规则I 会增加 count(U) ，所以再对 f(s) 取模3
f(WJ) = 1 → f ≡ 1 (mod 3)
f(WU) = 3 → f ≡ 0 (mod 3)
无论应用哪一条规则，f(s') mod 3 无法从 1 变成 0.
| rule | f(s’) mod 3 |
|---|---|
| I | Remains unchanged |
| II | 0 → 0, 1 → 2, 2 → 1 |
| III | Remains unchanged |
| IV | Remains unchanged |
思路2 WJ 有 1 个 J，≡ 1 (mod 3)；目标 WU 有 0 个 J。规则 I、IV 不会改变 J 的个数，mod 3 不变；规则 IV 中 J 个数减 3，mod 3 不变；规则 II 中，J 个数翻倍，mod 3 会从 1 变成 2 或是 2 变成 1， 无法抵达 0.
综上，对 WJ 中 J 的个数 mod 3 为 1，任意操作后这个值要么不变，要么变成2，要么变成1，无法抵达0
Euclid’s Theorem
n! + 1 从模1到模n，始终余1。-> 质数是无穷的
非递归的递归可枚举集
- Recursive (递归的)/Decidable（可判定的）：存在一个算法，能对任意输入在有限时间内判断其是否属于该集合
- Semi-Decidable（半可判定的）：只有在元素存在于集合中时，才能确定
- Recursively enumerable (递归可枚举的)：一个图灵机，它可以枚举集合中的所有元素（如果拥有足够长的时间），比如输出包含所有元素的一个无限列表
一个不是递归的递归可枚举集合，是说无法构造一个总会停机的算法来判断某元素是否不属于该集合。也即是如果某个输入不在集合中，程序可能永远不会停下来给出否定答案
第五公设与非欧几何
如果两条直线与第三条直线相交时，在第三条直线的某一侧三条线所夹的内角之和小于两个直角的和，则那两条直线沿着这一侧延伸足够长之后必然相交。
- What does the statement— “There are recursively enumerable sets that are not recursive” ?
- Mathematical Logic at Fudan
- 康托尔、哥德尔、图灵——永恒的金色对角线(rev#2)
- 对角线方法之后的故事
- Poincaré圆盘模型：一个神奇的双曲世界
三个层次上的语言
沙文主义
把这种“固有意义”的论点与那种与此平行的“固有重量”的论点相比较将是很有趣的。假设某人把一个物体的重量定义为“当此物体处于行星地球的表面时产生的向下方的力的量度”。在这个定义下，当一个物体处于火星表面时，它产生的向下方的力就不能被称为“重量”，而要另找个词。按这个定义，重量成了一种固有属性，但其代价是地球中心观——“地球沙文主义”。这有点像“格林威治沙文主义”——即拒绝承认地球上除格林威治平时之外的其它地区时间。这样看待时间未免太古怪了。
也许我们在智能问题上已经不自觉地背上了类似的沙文主义包袱，导致在意义问题上也是这样。在我们的沙文主义观点下，我们可能把那些具有和我们充分相似的大脑的生物称为“智能生物”，同时拒绝承认其它类型的东西是具有智能的。举一个极端的例子：设想有一块陨石，它没有去释读那张游荡在太空的巴赫唱片，而是在相遇时对唱片完全置之不理，只管走自己的路。在我们看来，它和唱片的相互作用方式不涉及唱片的意义。因此，我们会倾向于认为它是“愚钝的”。但我们这样做很可能是错怪了这块陨石。也许它正是具有一种“更高级的智能”，是我们这些带着地球沙文主义眼光的人所无法感知到的。而它与唱片的相互作用恰恰是这种高级智能的表现。那么，也许唱片也具有一种“更高级的意义”——完全不同于我们所赋予它的那种意义。也许它的意义取决于接收它的智能的类型。也许。
框架消息、外在消息、内在消息
另一方面，如果构成一条DNA的碱基序列是以抽象符号的形式（如图41）被送出，而不是作为长长的螺旋形分子被送出，那么，用这种外在消息来触发那种能把表现型从遗传型中抽取出来的解码机制，其成功的可能性实质上是零。在这种情况下用来包裹内在消息的外在消息实在是太抽象了，它已经失去了恢复环境的能力，因此在实用的意义上来说，这组符号是不具有固有意义的。为了不使你觉得上述讨论过分抽象化和哲学化，请想一下下面这个当今在某些国家高度敏感的问题：到底在哪个时刻才能说遗传型已经“达到”或“隐含”了表现型？这也就是堕胎的合法性问题。
TBC