柳渝，Laboratoire MIS, Université de Picardie Jules Verne，France

一，引言

哥德尔不完备性定理的证明主要在他1931年论文的第一章和第二章 [1]：在第一章中，哥德尔介绍其证明的主要思路，即直接运用传统的康托尔对角线法构造一个说自己是不可证明的悖论命题; 在第二章中，哥德尔直接在他所定义的形式系统中将此悖论命题翻译成一个“事实的” 递归函数，并声称此悖论命题是其形式系统中的 “不可判定的命题”，从而得出形式系统不完备性的结论。

哥德尔的说自己是不可证明的悖论命题是“说谎者悖论”的翻版，所以解读“说谎者悖论”成为解读哥德尔不完备性定理证明的一个关键点！

二，“说谎者悖论”，自指与通用过程

以说谎者悖论为代表的一类悖论与“自指”密切相关，可以说自指是这类悖论的“因”。值得注意的是，自指只是悖论的必要条件，因为自指并不必然产生悖论，比如递归函数的自指就不是悖论。

那么，自指的“因”又是什么？可以说是通用过程f(x) 。通用过程f(x)指，f的变量x是任意的过程，包括f，故令x=f，则产生自指：f(f)（图1）。 

以“说谎者悖论”为例，埃皮门尼得斯（Epimenides）说所有的克里特人（Cretan）说谎，记作Epimenides(cretan)，cretan是变量。既然埃皮门尼得斯也是克里特人，令cretan=Epimenides，产生自指：Epimenides(Epimenides)，即问：埃皮门尼得斯自己说谎吗？

所以，追本溯源，如说谎者悖论的根源在“通用过程”！这正是图灵1936年论文的主题 [2]。

三，图灵1936年论文的主要工作

图灵1936年论文围绕着通用过程展开：图灵从可计算数出发，首先设计图灵机，定义可计算性，编码图灵机，然后构造通用过程（通用图灵机）U(M)，即U(M)模拟任意图灵机M的计算。

接着图灵持批判继承的态度，首先揭示传统的康托尔对角线存在着“不恰当预设”，然后加以修正，最后提出正确运用对角线法，证明不存在判定任意图灵机M的可计算性的通用过程D(M) [3]。由此图灵区分“计算通用过程”U(M)和用于“判定通用过程”D(M)：U(M)是图灵机，但D(M)却不是图灵机（图2）。图灵在1938年的博士论文中提出“神谕机（Oracle）”来指称D(M) [4]。

图灵在1936年的论文中进一步推论不存在判定任意图灵机 M 是否打印预期符号（比如说 0）的通用过程 E(M)。

最后，图灵将任意图灵机 M 打印预期符号表达为谓词公式Un(M)，推论不存在通用过程判定任意谓词公式是否可证明，于是希尔伯特的Entscheidungsproblem无解（图3）。

与学术界对图灵1936年论文的看法完全相反，图灵在其证明中并没有运用悖论！

四，图灵和哥德尔看待说谎者悖论的不同视角

让我们这样来表达说谎者悖论：

如果埃皮门尼得斯说“所有克里特人说谎”（因），那么埃皮门尼得斯自己是否说谎（果）？

哥德尔“预设”说所有克里特人说谎的埃皮门尼得斯存在，问埃皮门尼得斯自己是否说谎？而图灵“探寻”说所有克里特人说谎的埃皮门尼得斯是否存在，也就是说，哥德尔重“果”，而图灵重“因”。

这里需要提到图灵在世留下的最后一篇论文，“可解和不可解的问题”（1954）[5]，这是篇图灵以科普形式撰写的论文。图灵举拼图例子，运用反证法，“假设”而不是“预设”判定拼图不可解的通用过程存在，得出自相矛盾的悖论，然后得出不存在通用过程判定拼图是否可解，故判定拼图是否可解是一个“不可判定命题”。

无论是1936年的论文还是1954年的论文，图灵的观点都是一致的，悖论源于“不恰当预设”， 即悖论是因预设原本不存在的判定通用过程而产生的。

五，结语

我们继续用说谎者悖论来进行类比。

图灵在1936年的论文中通过证明不存在判定的通用过程来证明Hilbert的Entscheidungsproblem无解，其象征意义可以看作是，指出说所有克里特人说谎的埃皮门尼得斯不在克里特岛上，而是在克里特岛之外 (Escher's style Figure 4 [6])。由此图灵才得以于1950年提出“模仿游戏”，超越“计算机器”，迈入“思维机器”，开启了机器学习的人工智能的篇章 [7]！ 

但是哥德尔却没有这样的系统观，无意识中“预设”了埃皮门尼得斯在克里特岛上，从而混淆了克里特岛之内与克里特岛之外二个不同的维度，形成说谎者悖论 (Escher's style Figure 5 [6])。 

表面上看，哥德尔不完备性定理给出了形式系统不完备性的看似深刻的结论，但实际上却因在证明中将自相矛盾的悖论命题当作“事实命题”，无意识中又否定了其形式系统不完备性的结论，因此造成了近一个世纪人们思想上难以言表的困惑。

在逻辑上，说谎者悖论是预设不存在的判定的通用过程存在而导致的自相矛盾，是隐藏很深的“不恰当预设”谬误；在认知上，说谎者悖论形成自我否定的思想陷阱。所以探寻产生说谎者悖论的根源，解放思想，这或许就是无意义的悖论的真正意义！

参考文献：

[1] Kurt Gödel, On Formally Undecidable Propositions of Principia Mathematica and Related Systems I (1931). https://monoskop.org/images/9/93/Kurt_G%C3%B6del_On_Formally_Undecidable_Propositions_of_Principia_Mathematica_and_Related_Systems_1992.pdf

[2] Alan Turing, On Computable Numbers, with an Application to the ENTSCHEIDUNGSPROBLEM, 1936. https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

[3] Yu LI, How did Turing apply the diagonal method? - Revisiting Turing's 1936 paper. https://revisiter-godel-article.blogspot.com/2023/11/revisiting-turings-1936-paper-how-did.html

[4] Turing, A.M. Systems of Logic Based on Ordinals, 1938.

[5] Alan Turing, Solvable and Unsolvable Problems. http://www.ivanociardelli.altervista.org/wp-content/uploads/2018/04/Solvable-and-unsolvable-problems.pdf

[6] https://mcescher.com/gallery/

[7] Alan Turing, Computing Machinery and Intelligence, 1950. https://academic.oup.com/mind/article/LIX/236/433/986238