人工智能时代：破解人机共存密码（套装共10册）

我们很容易证明 $\mathbb { A }$ 中的方程是无穷多的。比如，我们定义第一个方程，这个方程在x=1的时候， $f \mathrm { ~ ( ~ x ~ ) ~ }$ 等于1，输入其他数的时候等于0。即：

$$
f \left( 1 \right) = 1 ; f \left( \mathrm { x } \right) = 0 , \mathrm { x } \neq 1
$$

我们同样可以定义第二个方程，在 $\tt X ^ { = 2 }$ 的时候等于1，其他输入等于0，即：

$$
f \left( 2 \right) = 1 ; f \left( \mathrm { x } \right) = 0 , \mathrm { x } \neq 2
$$

因为自然数有无穷多个，这样定义的方程也会有无穷多个。

里存在不可计算方程，即可计算方程的集合 $\mathbb { A }$ 是方程集合 $\wp$ 的严格子集。即 $\mathbb { A } _ { \sf t E } \mathbb { Q }$ 要小，总有些方程是可以有确定结果，但不是一个可计算方程。

证明

在任何形式系统中，只要某种证明存在，就总有找到对应该证明的算法。由于我们必须假定该系统是以某种符号语言来表达的，而这种语言又是按照符号的某些有限“字母”来表达的。我们把符号串以字典的方式编序。这表示对于固定的串的长度按字母编序，先取所有串长为1的，然后取串长为2的，串长为3的等。这样我们就把所有正确建立起来的证明按照这个字典方案进行编序。我们有了证明的列表，就有了该形式系统里的所有定理的列表。

我们总可以对可计算方程，写出来它的计算步骤，再按照写这些步骤的文档的字母顺序把这些文档排列起来。这样我们就可以首先对集合 $\mathbb { A }$ 里所有的方程排一个顺序。具体来说，我们这样做：写计算

表5–2

机程序时，我们常用分割符来表示一行的结束。这并不妨碍我们把整个程序当成一个字符串。这样，比如用某一个程序语言编写的程序Pf是用来计算可计算方程f所对应的程序，这个程序Pf是有限长度的字符串。我们依据长度把所有的表示Pf的字符串排起来，当字符串长度相同的时候，我们依据它们的字母顺序来排序。这很像编一本字典，先按照单词的长度排序，单词长度相同的时候，我们依照它们的字母顺序来排。于是我们就有了一本所有可计算程序的字典L。每一个可计算程序都会在这个字典L中有一个确定的位置。当然也有可能某个可计算方程f可以对应几个不同的程序Pf1，Pf2 ……，我们只保留在这个序列中的第一个Pf，由于方程和程序之间实质上是对应的，我们会看到一个就足够了。一个方程可以有多个方程来表达，我们只选其中一个。f可以由多个Pf来表达，这在布置计算机课的作业的时可以看到。同一道编程题学生可以交来不同的程序，变量用的符号都可以不一样，但这些程序本身是等效的，我们只保留其中最短的字母排序最靠前的一个来作为列表的程序Pf 。

依据这本字典，我们就可以把输入值和程序列在一起，形成一个足够大的表，如表5–2所示。

我们现在可以定义一个方程 ${ \overline { { f } } } .$

$$
\overline { { f } } _ { \mathrm { ~ = ~ 1 ~ - ~ f ~ i ~ } \mathrm { ~ ( ~ } i \mathrm { ~ ) ~ } }
$$

$\overline { { f } }$ 也可以把确定的正整数输入输出为确定的0或1，所以它是 $\wp$ 中的一员。依据上表， $\overline { { { f } } } _ { \mathrm { ~ ( 1 ) ~ = ~ 0 , ~ } } \overline { { { f } } } _ { \mathrm { ~ ( 2 ) ~ = ~ 1 , ~ } } \overline { { { f } } } _ { \mathrm { ~ ( 3 ) ~ = ~ 1 ~ } }$ ${ \overline { { f } } } _ { \mathbf { \Phi } ( 4 ) \mathbf { \Phi } = \mathbf { \Phi } 0 \cdots }$

那么， $\overline { { f } }$ 是一个可计算方程吗？

答案是否定的， $\overline { { f } }$ 不是一个可计算方程。

如果f是一个可计算方程，那它应该已经在表5–2里了，因为我们把所有的可计算方程列在了表5–2里。假设 $\overline { { f } }$ 在第j行，这样 $\overline { { f } }$ $\left( \begin{array} { l } { \mathbf { \boldsymbol { x } } } \end{array} \right) \ = f \mathbf { \dot { j } } \ \left( \begin{array} { l } { \mathbf { \boldsymbol { x } } } \end{array} \right)$ ，比如是在第107行，则 $\scriptstyle { j = 1 0 7 }$ ，但是 $f _ { \mathrm { ~ \tiny ~ ( ~ 1 0 7 ) ~ } = 1 \mathrm { ~ - ~ } }$ $f 1 0 7 \ ( 1 0 7 ) \ \ne f 1 0 7 \ ( 1 0 7 )$ ，所以 $f$ 不是在第107行。同样的，对于$\overline { { { f } } } _ { \mathbf { \Phi } ( \ j ) \mathbf { \Phi } ( \ j ) \mathbf { \Phi } ( \ j ) \mathbf { \Phi } ( \ j ) \mathbf { \Phi } ( \ j ) } $ ，当输入相同的时候， $\bar { f }$ 和fj至少有一个输出是不一样的， $\overline { { f } }$ 也不在任意一行。因此，在表5–2里面，没有一行对应于 $\overline { { f } }$ 这个方程，所以 $\overline { { f } }$ 不是可计算方程 $\mathbb { A }$ 中的一员，但它确实是 $\wp$ 中的一员，因此， $A \mathbb { 1 } _ { \mathbb { A } } \mathbb { Q }$ 的子集。

这样我们就会看到，确实我们可以定义一个方程，它有确定的含义和输入输出，但是是不可计算的。

现在我们证明哥德尔的第一不完备定理：在系统Π中，存在真实的命题，但不能被证明。

我们再来补充定义我们说“真”和“假”时的含义。

我们把一个陈述称为f 陈述，对于任何一个正整数输入值x，如果它可以表达为“f 是1”或“ f 是0”，每一个f 陈述都是一个关于某一整数的判定。比如 f（107）=1就是一个f 陈述，x的值是107。这样对于任何正整数输入值，f 陈述只有两个值，0或1。因为两个陈述都指的是同一个输入值，我们说第一个是f 陈述Sf，第二个是反f 陈述， $S _ { \textit { f } }$

现在我们可以定义“真”了。

我们说如果f 等于1，那么这个关于f 的陈述Sf 是真的，它的反对面 $S _ { f }$ 就是假的。同样，如果f等于0，那么 $S$ f是真的，而Sf就是假的。这样，对于任何一个输入值x，陈述Sf和 $\widetilde { S }$ f总有一个是真的，另外一个是假的。在这个有效证明体系中，不可能证明一个假命题是对的。

形式系统足够丰富：任何f的命题可以被确定陈述。我们这里用到确定陈述，不一定指的是被证明或者被证伪，只是说它应该有个确定的值，即这个形式系统是足够丰富的。我们将来会看到这一点非常重要。

假设系统Π是一个足够丰富的形式证明系统，并且：

A.任何假的命题不能被证明；

B.任何真的Sf命题，都存在一个属于系统Π的证明序列，来证明Sf是真的。

因为系统Π足够丰富，任何整数x，都会有Sf和 $\widetilde { S }$ f的陈述，而且只有一个是对的，A和B意味着总有一个有限的证明序列，证明Sf或 $S$ f是真的。即这个证明序列本身就可以作为一个确定的程序，在有限的时间内结束，给出一个确定的结果，因此它是可计算的。但这与我们之前证明的f是不可计算的矛盾。具体来说，如果两个假设A和B都是真的，我们可以设计这样一个程序来决定 $f \mathrm { ~ ( ~ } \mathrm { x ~ ) ~ }$ 的值。

具体来说，我们就可以设计一个计算机程序P在这个程序里，在有限时间内可以被计算出来。即，对于输入值x，程序P可以在有限时间里输出0或1。我们可以有一个P'，来检测输出值是否符合1–$f \mathrm { ~ ( ~ x ~ ) ~ }$ ，如果符合，就是一个被证明正确的命题；如果不是，我们同样可以设计一个 $\cdot P ^ { \mathrm { ~ , ~ } }$ ，来检测否定，这样我们就设计了一个程序，它在有限时间内能够计算f，而且它是一个有限长的程序，但我们刚刚证明$_ { \intercal } f$ 是不可计算的，与前面的证明相悖，因此刚才的假设A或B不同时成立。

因此我们说，对于任何一个足够丰富的形式系统Π，如果它自洽的话，总存在正确的陈述在这个体系内不能被证明。类似的说法，在一个自洽的系统里，一定存在对于自然数来说，命题的正与反都不可证。

我们也证明了图灵的不停机问题，即不存在一个超级程序能判定其他程序是否可以在有限时间内结束。

和前一节的讨论有类似的推论，我们一样有了哥德尔第二不完备定理：

如果一个系统是足够丰富和自洽的，它的自洽性不能在系统内部被证明。如果要证明系统Π是自洽的，需要引入另外的一个形式证明$\varPi ^ { \prime }$ ，但 $\varPi ^ { \prime }$ 的自洽性也不能在它内部证明。

第六章哥德尔问题的延伸

真理存在，真理存续。哥德尔不完备定理解释了为什么我们总需要感性部分的存在，总有些直觉的认知无法被理性取代。这些感性的认知成就了我们人之所以为人的重要性。

《数学原理》是这一打击的第一个牺牲品，但绝不是最后一个。哥德尔那篇论文的标题中的“及有关系统”这几个字，蕴含着丰富的潜在内容。简而言之，哥德尔展示了：无论涉及什么公理系统，可证性总是比真理性弱。

——侯世达（Douglas R. Hofstadter）

哥德尔的不完备定理有几种等价的数学说法：

1.任何自洽的数学形式系统都包含不可判定命题。

2.没有数学形式系统既是自洽的又是完备的。

3.没有定理证明机器（或机器程序）能够证明数学中所有的真命题。

4.数学是算法上（机械上）不可穷尽的。

希尔伯特和罗素和他们之前的几代人希望把数学搞成一个形式化系统，希望所有的猜想都能从逻辑出发加以判定，希望所有事情迟早在“意料之中”等等，这些希望最终由哥德尔判定为数学家的痴心妄想。数学的神奇之处在于它扎根于人类的观察、直觉和灵感，但数学不等于逻辑，数学成果也并不总是能从公设开始通过逻辑推演出来。哥德尔不完备定理同时表明，数学存在无穷多个有确切答案的问题，不能利用任何公设化程序找到它们的解；它们并不，也不能对应于任何形式系统中的定理。这些问题的答案是不可计算的，而且也不能归结为其他数学事实。这里推广爱因斯坦关于上帝掷骰子的名言：上帝恐怕不仅仅是在量子力学中玩骰子，他甚至在数学中也玩了骰子。这对数学家而言是个可悲的结论，他们努力了一生的某个数学猜想的证明可能根本不存在，但也可能是无穷美好的结论，它把实验物理学家对数学家的“纯想象的”鄙视消除了，数学也是发现自然潜在规律的工具，它联结了人脑的直觉和自然规律。