自我指涉与数理逻辑

寂收录于 Theory

2020-11-16 约 2127 字预计阅读 5 分钟次阅读

“我是谁？”，这种对指代自身的疑问每个人都会有。在自然语言和形式语言中，如果一个句子直接或间接提及自身，就称为自指 (Self-reference)，自指的语句常常会造成悖论。

不可判定怪圈

“这句话在说谎”，那么引号中的话是真话吗？你会发现，你若判定真，就会推出假。而你若判定假，又会推出真。不停的判定下去，就会陷入怪圈：

在程序中，这就是无穷递归。与意识的自指相似的是别洛索夫发现的 B-Z 反应。意识中的悖论竟在自然界中有对应，这不禁让人疑惑：我们真的有自由意志吗？

崩塌的数学大厦

在 1900 年巴黎数学家大会上，希尔伯特提出了他的 23 个著名数学问题。以希尔伯特为首的很多数学家，打算让数学矗立在一个坚实的地基(公理体系)上，一劳永逸地解决所有对数学可靠性的疑问，这可是一项宏图大志。

第二个问题

这 23 个问题中的第 2 个问题是完成数学家们理想计划的关键一步，它包含如下三个问题：

数学是完备的吗？(正确的数学陈述，是否总能被证明？)
数学是一致的吗？(数学是否前后一致，没有内部矛盾？)
数学是可判定的吗？(能否仅通过计算判定数学陈述的真假？)

在数学中，不证自明的事实被归纳为公理。公理是数学推演(计算)的起点，对公理的陈述就是命题，已被证明成立的重要命题被称为定理。那么一个可靠的数学系统至少应该满足以下性质：

有效性：在系统中如果前提为真，那么结论也为真
可靠性：系统中的所有定理都为真
一致性：系统中所有公理，定理之间没有矛盾
完备性：系统中不存在无法证明或无法证伪的命题

哥德尔不完备定理

这个想法非常美好，然而不久后，哥德尔用两条不完备定理将数学家们拍醒了：

第一定理：任何包含了算术的数学系统不可能同时拥有一致性和完备性(这里算术指皮亚诺算术(PA)的公理，这说明任何一个允许自然数加法和乘法的体系必定是不完备的，通过数学推演无法得到体系中所有真命题)。
第二定理：任何包含了算术的数学系统，如果它是一致的，那么它就不能证明自身的一致性。

哥德尔不完备定理说的是算术系统中“正确”与“可证”是两码事。他的证明是在算术系统 T 中构造出了命题 P：“P 不可在算术系统 T 内证明”(我不可被证明)。这让我们意识到只要一个系统的表达力强到可以自指，那么就是不完备的。

图灵机的由来

哥德尔得到了第二个问题中前两个问题的答案。不久之后，图灵给出了其中最后一个问题的答案：数学是不可判定的。

图灵对计算的思考

什么是计算？计算就是由输入(前提)到输出(结论)的过程。什么是可计算的？可计算就是一定能在有限步骤内完成的计算。为了给可计算一个精确定义，图灵提出了一种叫图灵机的数学模型，并提出了可计算函数 (算法)的概念。(为什么可计算就是图灵机可判定，请看邱奇－图灵论题 )

图灵对计算的思考让他解决了希尔伯特的问题，他的证明过程分两步:

1.停机问题不可判定
2.停机问题到判定问题的归约

停机问题不可判定

停机问题：是否存在一个程序 P，对于有任意输入参数的程序 w，能够判断 w 会在有限时间内结束或者死循环。图灵用对角论证法证明了，不存在解决停机问题的通用算法。本文用自指做一个反证法证明(程序中的自指就是递归)：

假设存在可以判定任意程序是否停机的程序，我们姑且称它为上帝程序
那么一定存在一个撒旦程序，首先让上帝程序判定自己，然后根据上帝判定结果，相反地运行程序

伪代码描述如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def P(w, input):
    if w halts on input:
        return true
    else:
        return false

def oppose_P():
    if P(oppose_P):
        while (1):
            pass
    else:
        pass

在撒旦程序中，上帝程序的判断都是错的，所以不存在这样的上帝程序。停机问题是不可判定问题，这响应了哥德尔不完备定理。

到判定问题的规约

现在一定存在某个数学陈述能够做为程序 w 的输入参数，而前面的停机问题证明了，不存在能够判定任意程序 w 能否在有限时间内结束的上帝程序，因此数学是不可判定的。

自指与自复制

美国哲学家蒯因(Quine)创造了一种不使用代词就能构造自指语句的方法，称为蒯因技巧。如下句子便采用了蒯因技巧：

把“把中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变”中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变

当你按照该句子的指示操作后，便得到了它自身。该句子仅用动作(数学推演)便完成了一次自复制，数学家克林(Kleene)将蒯因这种语言的操作技巧进行数学化得到了一种更加普适的递归定理。有了这个递归定理以后，数学家就可以在严格的数学公理体系中构造各种自指游戏。哥德尔和图灵也是用递归定理来完成他们的伟大证明。

思考总结

回到皮亚诺公理的第五条：对于无穷无尽具有相同性质的多米诺骨牌序列，已知第一块会倒下，并且每一块多米诺骨牌的倒下都会导致后一块倒下，是否每一块多米诺骨牌都会倒下？数学给出的假设是会，你觉得呢？数学是建立在有限假设之上的学科，当已知假设无法推导某些与无穷相关的性质时，就会在判定结果中显现出这种无穷无尽。一阶逻辑的逻辑归结是半可判定的，无法用有限归纳描述无穷过程。

对自指的深入研究涉及到复杂性科学，想了解相关知识的读者，可阅读下面的参阅资料。

推荐阅读

目录