更改

{| class="wikitable"

{| class="wikitable"

|-

|-

! 比较条目 !! 图灵停机问题 !! 哥德尔定理

! 编号 !! 比较条目 !! 图灵停机问题 !! 哥德尔定理

|-

|-

| 基本符号 || 程序设计语言的基本符号，诸如“if then, for, loop...” || 谓词逻辑符号:“~,∧,∨,∃,∀”,算 数运算符:“+,×,=”,数字,变量等等

| 1 !! 基本符号 || 程序设计语言的基本符号，诸如“if then, for, loop...” || 谓词逻辑符号:“~,∧,∨,∃,∀”,算 数运算符:“+,×,=”,数字,变量等等

|-

|-

| 基本单元 || 基本符号拼接出的完整的计算机程序，例如“Print("hello world");” || 基本符号拼接出的合法的命题语句,诸 如:“∀a: ~(a+1)=0”

| 2 !! 基本单元 || 基本符号拼接出的完整的计算机程序，例如“Print("hello world");” || 基本符号拼接出的合法的命题语句,诸 如:“∀a: ~(a+1)=0”

|-

|-

| 计算 || 计算机程序对字符串操作产生新的字符串 || 命题语句根据公理和规则推导产生新的命题语句

| 3 !! 计算 || 计算机程序对字符串操作产生新的字符串 || 命题语句根据公理和规则推导产生新的命题语句

|-

|-

| 单元编码 || 程序的源代码（字符串） || 命题的哥德尔编号

| 4 !! 单元编码 || 程序的源代码（字符串） || 命题的哥德尔编号

|-

|-

| 层次混淆 || 程序P去读另一个程序S的源代码s，并进行运算P(s) || 将一个命题的哥德尔编号n输入给包含自由变元的命题,并完成运算f(n)

| 5 !! 层次混淆 || 程序P去读另一个程序S的源代码s，并进行运算P(s) || 将一个命题的哥德尔编号n输入给包含自由变元的命题,并完成运算f(n)

|-

|-

| 单元意义 || 程序是否停机(停或不停) || 命题是否正确(真或假)

| 6 !! 单元意义 || 程序是否停机(停或不停) || 命题是否正确(真或假)

|-

|-

| 有意义的单元集合 || 所有的停机的计算机程序，数据对：(x,y)。即当x作用到y上面的时候X(y)停机 || 所有的定理,即根据公理和推理规则推 单元集合 导出的命题语句。我们希望所有的定理 都是真的(一致性),并且所有的真命题

| 7 !! 有意义的单元集合 || 所有的停机的计算机程序，数据对：(x,y)。即当x作用到y上面的时候X(y)停机 || 所有的定理,即根据公理和推理规则推 单元集合 导出的命题语句。我们希望所有的定理 都是真的(一致性),并且所有的真命题

都是定理(完备性)

都是定理(完备性)

|-

|-

| 系统自身给出的意义判断 || H(x,y)函数：判断源代码为x的计算机程序作用到数据y上面是否停机 || 语句“∃m:T(m,n)”,即“存在一个自然数m,使得m和n构成证明对”,也就是“n所代表的命题是一个定理”

| 8 !! 系统自身给出的意义判断 || H(x,y)函数：判断源代码为x的计算机程序作用到数据y上面是否停机 || 语句“∃m:T(m,n)”,即“存在一个自然数m,使得m和n构成证明对”,也就是“n所代表的命题是一个定理”

|-

|-

| 蒯恩函数 || 计算机程序Q(x)，定义为：让程序X读入自己的源代码，即Q(x)="X(x)" || 函数Q(n),定义为:将一个包含自由变元的语句N的编号n代入其自身的自由变元中,即 Q(n)=N(n)

| 9 !! 蒯恩函数 || 计算机程序Q(x)，定义为：让程序X读入自己的源代码，即Q(x)="X(x)" || 函数Q(n),定义为:将一个包含自由变元的语句N的编号n代入其自身的自由变元中,即 Q(n)=N(n)

|-

|-

| “我” || Q(q)，就是将蒯恩函数Q的源代码q（字符串）喂给函数Q它自己的代码。Q(q)为一个字符串，Q(q)="Q(q)" || Q(q)，将函数Q自己的哥德尔编号q喂给函数Q。Q(q)得到的数就是它自己的哥德尔配数。Q(q)=c(Q(q))。

| 10 !! “我” || Q(q)，就是将蒯恩函数Q的源代码q（字符串）喂给函数Q它自己的代码。Q(q)为一个字符串，Q(q)="Q(q)" || Q(q)，将函数Q自己的哥德尔编号q喂给函数Q。Q(q)得到的数就是它自己的哥德尔配数。Q(q)=c(Q(q))。

|-

|-

| 悖论函数 || 程序D(z)，他是蒯恩程序与判断程序H(x,y)的结合，即D(z)=H(z,z)=H(Q(z))，其中z为输入的参数 || 函数Q<u>о</u>T,也就是蒯恩函数Q(x)与意义判断语句的结合: Q<u>о</u>T(n)=“~∃m: T(m,Q(n))”,其中 n 为一个自由变元

| 11 !! 悖论函数 || 程序D(z)，他是蒯恩程序与判断程序H(x,y)的结合，即D(z)=H(z,z)=H(Q(z))，其中z为输入的参数 || 函数Q<u>о</u>T,也就是蒯恩函数Q(x)与意义判断语句的结合: Q<u>о</u>T(n)=“~∃m: T(m,Q(n))”,其中 n 为一个自由变元

|-

|-

| 悖论单元 || 当程序D作用到它自己的源代码上，即D(d)，表示“我不停机”。 || G,当函数Q<u>о</u>T作用到它自己的哥德尔编码q<u>о</u>t上所产生的哥德尔语句即G=“~∃m:T(m,Q(q<u>о</u>t))”,表示“我不是定理”。注意,Q(q<u>о</u>t)得到的就是G的编码

| 12 !! 悖论单元 || 当程序D作用到它自己的源代码上，即D(d)，表示“我不停机”。 || G,当函数Q<u>о</u>T作用到它自己的哥德尔编码q<u>о</u>t上所产生的哥德尔语句即G=“~∃m:T(m,Q(q<u>о</u>t))”,表示“我不是定理”。注意,Q(q<u>о</u>t)得到的就是G的编码

|-

|-

| 二律背反 || 当H(d,d)判断D(d)停机的时候，D(d)自己的表现为不停机；而当H(d,d)判断不停机的时候，D(d)又会停机 || 当G是一个定理的时候，根据G自己的意思，G不是一个定理(破坏了一致性)；当G不是一个定理的时候，我们知道G是一个真句子(破坏了完备性)

| 13 !! 二律背反 || 当H(d,d)判断D(d)停机的时候，D(d)自己的表现为不停机；而当H(d,d)判断不停机的时候，D(d)又会停机 || 当G是一个定理的时候，根据G自己的意思，G不是一个定理(破坏了一致性)；当G不是一个定理的时候，我们知道G是一个真句子(破坏了完备性)

|-

|-

| 结论 || 判断一切函数X作用到数据y上是否停机的计算机程序H(x,y)不存在 || 公理系统的一致性和完备性不能同时被满足

| 14 !! 结论 || 判断一切函数X作用到数据y上是否停机的计算机程序H(x,y)不存在 || 公理系统的一致性和完备性不能同时被满足

|}

|}

表1给出了图灵停机问题与哥德尔定理，以及证明这两个结论时所用的自指悖论技巧的全部细节对照表。

表1给出了图灵停机问题与哥德尔定理，以及证明这两个结论时所用的自指悖论技巧的全部细节对照表。

接下来的蓝色单元格表示的是系统所具备的另外一种基本属性，即'''意义判断'''。在计算机程序的世界中，我们知道程序可以分为停机的程序和不停机的程序两种；而对于命题语句来说，它们又可以分成真命题和假命题两种。这种意义判断是一个非常微妙的东西，因为，任意拿来一个程序或者是命题，我们观察者确信它们会存在着一种意义，或者是程序停机或者是命题正确。尽管在很多情况下，我们并不能马上给出这样的判断。例如，对于很复杂的程序来说，尽管我们已经等了100天，它没有停机，但是我们并不知道它会不会在第101天内停下来。但是，我们会倾向于认为任何的单元都具备某种意义或者价值，而且我们迫切地希望这种意义判断能够让系统自身告诉我们答案，也就是希望存在一个计算机程序H能够自动给出任意程序X作用到y上是否停机；或者是希望公理体系中的定理能够自动帮我们判断所有的命题是否为真，这就是语句“m:T(m,n)”的作用。尽管这个梦想最终必将破灭。我们看到，'''这种意义判断是破坏性自指系统特有的，而构建性自指系统不具备的重要属性之一'''。

接下来的蓝色单元格（'''编号6-8'''）表示的是系统所具备的另外一种基本属性，即'''意义判断'''。在计算机程序的世界中，我们知道程序可以分为停机的程序和不停机的程序两种；而对于命题语句来说，它们又可以分成真命题和假命题两种。这种意义判断是一个非常微妙的东西，因为，任意拿来一个程序或者是命题，我们观察者确信它们会存在着一种意义，或者是程序停机或者是命题正确。尽管在很多情况下，我们并不能马上给出这样的判断。例如，对于很复杂的程序来说，尽管我们已经等了100天，它没有停机，但是我们并不知道它会不会在第101天内停下来。但是，我们会倾向于认为任何的单元都具备某种意义或者价值，而且我们迫切地希望这种意义判断能够让系统自身告诉我们答案，也就是希望存在一个计算机程序H能够自动给出任意程序X作用到y上是否停机；或者是希望公理体系中的定理能够自动帮我们判断所有的命题是否为真，这就是语句“m:T(m,n)”的作用。尽管这个梦想最终必将破灭。我们看到，'''这种意义判断是破坏性自指系统特有的，而构建性自指系统不具备的重要属性之一'''。

然后是粉色单元格部分，它是破坏性自指系统的核心之处。无论是图灵停机问题还是哥德尔定理的证明，它们都用蒯恩函数加上一个否定的意义判断程序而构造了一个自指悖论出来。在图灵停机问题里面，程序D作用到自己的源代码d上面就会产生“我不会停机”的效果；而在哥德尔定理的证明中，哥德尔句子就在说“我不是一个定理”。所以D(d)和G才是整个证明中的核心。

然后是粉色单元格部分（'''编号11-13'''），它是破坏性自指系统的核心之处。无论是图灵停机问题还是哥德尔定理的证明，它们都用蒯恩函数加上一个否定的意义判断程序而构造了一个自指悖论出来。在图灵停机问题里面，程序D作用到自己的源代码d上面就会产生“我不会停机”的效果；而在哥德尔定理的证明中，哥德尔句子就在说“我不是一个定理”。所以D(d)和G才是整个证明中的核心。

最后，让我们来看浅蓝色的结论部分。虽然都采用了自指悖论的技术，但是图灵停机问题的结论是否定自动意义判断程序H的存在性，而哥德尔定理则并不反对系统自身给出的意义判断语句“∃m:T(m,n)”的存在性，因为我们已经人为构造出了这样的语句，它必然是存在的，但是自指悖论引来的是这个判断语句的判断能力是受到局限的，要么它是不一致的，要么它是不完备的。看起来似乎哥德尔定理的证明与图灵停机问题的证明在这一点上很不一样，但其实如果我们仔细分析，它们仍然是相通的。假如在图灵停机问题的证明中，我们像哥德尔定理证明中一样强硬地写出来一个判断程序停机的函数H，那么同样的逻辑就会在最后一步导致这个函数H判断的局限性。也就是说对于程序D(d)来说，H是否应该判断它停机呢？如果H判断D(d)停机，那么通过分析D(d)我们知道它不会停机，也就是说H的判断会导致矛盾的结果，即不一致性。如果H判断D(d)不停机，而我们通过分析D(d)又知道它会停机，于是我们便知道H这个函数并不能将所有事实上停机的程序判断为停机，也就是说H的判断是不完备的。于是，我们便能得出与哥德尔定理类似的结论：任何判断停机问题的程序都不能同时具备一致性和完备性。

最后，让我们来看浅蓝色的结论部分（'''编号14'''）。虽然都采用了自指悖论的技术，但是图灵停机问题的结论是否定自动意义判断程序H的存在性，而哥德尔定理则并不反对系统自身给出的意义判断语句“∃m:T(m,n)”的存在性，因为我们已经人为构造出了这样的语句，它必然是存在的，但是自指悖论引来的是这个判断语句的判断能力是受到局限的，要么它是不一致的，要么它是不完备的。看起来似乎哥德尔定理的证明与图灵停机问题的证明在这一点上很不一样，但其实如果我们仔细分析，它们仍然是相通的。假如在图灵停机问题的证明中，我们像哥德尔定理证明中一样强硬地写出来一个判断程序停机的函数H，那么同样的逻辑就会在最后一步导致这个函数H判断的局限性。也就是说对于程序D(d)来说，H是否应该判断它停机呢？如果H判断D(d)停机，那么通过分析D(d)我们知道它不会停机，也就是说H的判断会导致矛盾的结果，即不一致性。如果H判断D(d)不停机，而我们通过分析D(d)又知道它会停机，于是我们便知道H这个函数并不能将所有事实上停机的程序判断为停机，也就是说H的判断是不完备的。于是，我们便能得出与哥德尔定理类似的结论：任何判断停机问题的程序都不能同时具备一致性和完备性。

可以说，表1涵盖了所有破坏性自指中的精华。例如，我们可以用同样的方法来分析说谎者悖论：“这句话是假的”，或者等价的：

可以说，表1涵盖了所有破坏性自指中的精华。例如，我们可以用同样的方法来分析说谎者悖论：“这句话是假的”，或者等价的：