更改
跳到导航
跳到搜索
第577行：
第577行： − + − + − + − + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + 第610行：
第657行： − 下面，我们将进入计算机程序的世界。首先，让我们把考虑的计算机程序设定到自然数范围内，也就是说程序''F(x)''中的输入''x''是自然数，''F(x)''的计算结果也是自然数。我们知道计算机程序都是有限的指令组成的字符串，于是我们可以为这些字符串编号。所以，任何程序''F''都对应了一个自然数编码''f''，而输入变量''x''也是自然数，我们还可以定义一个函数''λ(f,x)''来对程序“把数据''x''输入给函数''F''”这个事件编码，其中''λ(f,t)''也是一个自然数<sup>4</sup>。+ 第618行：
第665行： − + − + − + − + − 其中，''λ(n,m)''就表示第''n''个程序计算输入数据''m''这个事件的编码。下面我们来考察那条黄金色的+ − ''λ(1,1),λ(2,2),λ(3,3),...,λ(n,n),...''+ − + − ''Q(1),Q(2),Q(3),...,Q(n),...''+ − 我们只要定义程序''Q''为：+ − ''Q(x):=λ(x,x)''+ − 实际上''Q(x)''就是蒯恩函数，它作用到''x''上就计算出将编码为''x''的程序作用到''x''自身上这个事件的编码。这样，只要我们清晰定义了函数''λ''，那么''Q''程序就一定存在。+ − 既然''Q''是可计算的，那么它必然也会占据表格中的某一行（表3中的粉色的行，设这行编码为''q''）。注意在这行中，我们列出了两个数值，上面的数值为程序''Q''作用到数据''x''的编码，即''λ(q,x)''，下面的数值为函数值''Q(x)=λ(x,x)''。对于一般的''x''来说，这两个数值没什么关系。但是，粉红行与黄金对角线的交点（桔色的格子）是个意外，它的上下两个数值发生了重合。+ − '''这个蒯恩程序所对应的行与对角线的交点是一个非常特殊的点，它就是我们前面提到的蒯恩句子，也是计算程序中的“自我”'''。为什么可以这么说呢？因为程序''Q''作用到它自己的源代码q上的就得到了''λ(q,q)''，即这个事件自身的编码。所以''Q(q)''这个计算就得到了“我”。+ − 从这个角度看，''Q(q)''其实也就是那个自打印程序。只不过在自打印程序中，我们把数据''q''同样定义到了函数''S(x)''之中的''q''变量上。所以自打印程序''S(x)''其实已经包含了这个''Q(q)''。+ − 同样地，''Q(q)''就相当于那个蒯恩句子：+ − 所以''Q(q)''神奇的地方恰恰就在于它让同样一个东西在不同的两个层次上重复了。+ 第667行：
第714行： − + − + − + − + − 与表3不同的地方是，此表格中的每一项不再是''λ(m,n)''了，而是''Φ<sub> Φ<sub>m</sub>(n)</sub>'' ，也就是第''k''个计算机程序''Φ<sub>k</sub>'' ，其中''k''为第''m''个程序作用到第''n''个数据上所计算出来的结果。如果第''m''个程序计算第''n''个数据不停机，则''Φ<sub> Φ<sub>m</sub>(n)</sub>'' 就是一个在任意输入上都没有定义的函数。因此，表中所列的不再是数，而是计算机程序本身，我们稍后将会看到这个区别的重要性。+ − ''Φ<sub> Φ<sub>1</sub>(1)</sub>'' ,''Φ<sub> Φ<sub>2</sub>(2)</sub>'' ,''Φ<sub> Φ<sub>3</sub>(3)</sub>'' ,...,''Φ<sub> Φ<sub>n</sub>(n)</sub>'' ,...+ − 接下来，我们考察任意一个计算机程序''F''，它可以作用到自然数：''Φ<sub> Φ<sub>x</sub>(x)</sub>'' 的计算结果上。于是我们便得到了一个复合程序FQ(x)F(x(x))。下面考察这样一个由不同的程序构成的行：+
无编辑摘要
{| class="wikitable"
{| class="wikitable"
|-
|-
! 自然数\实数位 !! ''1'' !! ''2'' !! ...... !! ''N'' !! ......
! 自然数\实数位 !! 1 !! 2 !! ...... !! N !! ......
|-
|-
| ''1'' || ''1'' || ''3'' || ...... || ''8'' || ......
| 1 || 1 || 3 || ...... || 8 || ......
|-
|-
| ''2'' || ''2'' || ''7'' || ...... || ''6'' || ......
| 2 || 2 || 7 || ...... || 6 || ......
|-
|-
| ...... || ...... || ...... || ...... || ...... || ......
| ...... || ...... || ...... || ...... || ...... || ......
|-
|-
| ''n'' || ''5'' || ''8'' || ...... || ''5'' || ......
| n || 5 || 8 || ...... || 5 || ......
|-
| ...... || ...... || ...... || ...... || ...... || ......
|}
假设我们可以将[0,1]之间的所有自然数放置到一张无穷行、无穷列的表格上。每一行就是一个实数，某一行的每一列就表示该实数小数点后面的第n位数字。例如第一个实数的第1、2、...、n、...列分别是1、3、...、8、...，那么这个小数就是0.13…8…。
下面我们考察对角线上面的元素（黄色的方格）。它表示第1个实数小数点后第一位的数字1，第2个实数小数点后第二位的数字7，...。假设第n个对角线上的数字为Q(n)，那么我们构造一个特殊的数字d：
0.28….6….
也就是该数字d的第n位d(n)为：
d(n)=(Q(n)+1) mod 10
那么，很显然d是一个[0,1]之间的实数，但是d并不在表格2中，因为d的第一个位与第一个实数的第一个数字不同，所以d不是第一个数字；d的第二个位与第二个实数的第二个数字不同，所以d不是第二个数字，...。所以d肯定不在表2之中。
于是，我们便可以推知，表2并不是一张完整的从[0,1]到N的映射。存在着漏网之鱼：实数d。
不难发现，对于任意的单射g，我们总可以构造出一个对角线元素d不在表中，所以，我们只能否认一开始的假设：R与N之间存在单射。于是不可能有c(R)<=c(N)，也就是实数的个数比自然数多。
康托尔的这种巧妙的对角线证明方法正是我们前面讨论的自指方法，对角线Q(n)也正是蒯恩函数，我们马上就会对此明朗了。
====康托尔的黄金对角线====
我们这里所说的黄金对角线是一种证明方法，它起源于数学家康托尔证明实数的个数比自然数多的过程中所用的一个特殊的技巧。
首先，康托尔定义对于两个超限集合（元素个数是无穷个）A和B来说，如果能找到一个单射f:A→B（即任给一个A中的元素，都存在唯一的B中元素与其对应），那么就称A集合的元素个数c(A)<=c(B)，即B集合的元素个数。反过来，如果存在单射g:B→A，那么就有c(B)<=c(A)。而如果c(A)<=c(B)和c(B)<=c(A)同时成立，就说c(B)=c(A)。
有了比较两个无穷集合元素个数的方法，我们就可以证明自然数集合N与偶数集合E的个数一样多。因为存在着单射f:N→E，f(x)=2x，同时存在单射g:E→N，g(x)=x/2。所以c(E)=c(N)。
下面，我们来比较实数集合R和自然数集合N的元素个数的多少。首先，我们很容易构造一个从N到R的单射f:N→R,f(x)=x。所以c(N)<=c(R)。
接下来，是否存在从R到N的单射呢？答案是不存在，我们可以用反证法来证明。我们可以先把问题简化，仅仅看从[0,1]这个闭区间到自然数集合N存在一个单射g。这也就意味着，对于任意的[0,1]之间的实数x，都唯一存在着一个确定的自然数n与它对应。我们称n为x的编号。我们不妨按照x的编号大小写下这些实数而形成一个表格：
<div style="text-align: center;">表2：对所有[0,1]区间内的实数编号</div>
{| class="wikitable"
|-
! 自然数\实数位 !! 1 !! 2 !! ...... !! N !! ......
|-
| 1 || 1 || 3 || ...... || 8 || ......
|-
| 2 || 2 || 7 || ...... || 6 || ......
|-
| ...... || ...... || ...... || ...... || ...... || ......
|-
| n || 5 || 8 || ...... || 5 || ......
|-
|-
| ...... || ...... || ...... || ...... || ...... || ......
| ...... || ...... || ...... || ...... || ...... || ......
====程序的黄金对角线与“自我”====
====程序的黄金对角线与“自我”====
下面，我们将进入计算机程序的世界。首先，让我们把考虑的计算机程序设定到自然数范围内，也就是说程序F(x)中的输入x是自然数，F(x)的计算结果也是自然数。我们知道计算机程序都是有限的指令组成的字符串，于是我们可以为这些字符串编号。所以，任何程序F都对应了一个自然数编码f，而输入变量x也是自然数，我们还可以定义一个函数λ(f,x)来对程序“把数据x输入给函数F”这个事件编码，其中λ(f,t)也是一个自然数<sup>4</sup>。
既然所有程序和输入数据都编好号了，我们便可以把所有的程序针对所有的输入数据的运算情况画在下面的大表格上：
既然所有程序和输入数据都编好号了，我们便可以把所有的程序针对所有的输入数据的运算情况画在下面的大表格上：
{| class="wikitable"
{| class="wikitable"
|-
|-
! 程序\数据 !! ''1'' !! ''2'' !! ...... !! ''q'' !! ......
! 程序\数据 !! 1 !! 2 !! ...... !! q !! ......
|-
|-
| ''1'' || ''λ(1,1)'' || ''λ(1,1)'' || ...... || ''λ(1,q)'' || ......
| 1 || λ(1,1) || λ(1,1) || ...... || λ(1,q) || ......
|-
|-
| ''2'' || ''λ(2,1)'' || ''λ(2,2)'' || ...... || ''λ(2,q)'' || ......
| 2 || λ(2,1) || λ(2,2) || ...... || λ(2,q) || ......
|-
|-
| ...... || ...... || ...... || ...... || ...... || ......
| ...... || ...... || ...... || ...... || ...... || ......
|-
|-
| ''q'' || ''λ(q,1) Q(1)=λ(1,1)'' || ''λ(q,2) Q(2)=λ(2,2)'' || ...... || ''λ(q,q) Q(q)=λ(q,q)'' || ......
| q || λ(q,1) Q(1)=λ(1,1) || λ(q,2) Q(2)=λ(2,2) || ...... || λ(q,q) Q(q)=λ(q,q) || ......
|-
|-
| ...... || ...... || ...... || ...... || ...... || ......
| ...... || ...... || ...... || ...... || ...... || ......
|}
|}
其中，λ(n,m)就表示第n个程序计算输入数据m这个事件的编码。下面我们来考察那条黄金色的
对角线，它是第n个程序作用到它自己的编码。如果我们把这一条线上的元素都拿出来就形成了一行：
对角线，它是第n个程序作用到它自己的编码。如果我们把这一条线上的元素都拿出来就形成了一行：
λ(1,1),λ(2,2),λ(3,3),...,λ(n,n),...
有趣的是，它的第一个元素与第一个程序作用到第一个数据上编码相同，第二个元素与第二个程序作用到第二个数据上相同，...。这一行的编码可看作一种运算''Q(x)''：
有趣的是，它的第一个元素与第一个程序作用到第一个数据上编码相同，第二个元素与第二个程序作用到第二个数据上相同，...。这一行的编码可看作一种运算Q(x)：
Q(1),Q(2),Q(3),...,Q(n),...
我们只要定义程序Q为：
Q(x):=λ(x,x)
实际上Q(x)就是蒯恩函数，它作用到x上就计算出将编码为x的程序作用到x自身上这个事件的编码。这样，只要我们清晰定义了函数λ，那么Q程序就一定存在。
既然Q是可计算的，那么它必然也会占据表格中的某一行（表3中的粉色的行，设这行编码为q）。注意在这行中，我们列出了两个数值，上面的数值为程序Q作用到数据x的编码，即λ(q,x)，下面的数值为函数值Q(x)=λ(x,x)。对于一般的x来说，这两个数值没什么关系。但是，粉红行与黄金对角线的交点（桔色的格子）是个意外，它的上下两个数值发生了重合。
'这个蒯恩程序所对应的行与对角线的交点是一个非常特殊的点，它就是我们前面提到的蒯恩句子，也是计算程序中的“自我”'。为什么可以这么说呢？因为程序Q作用到它自己的源代码q上的就得到了λ(q,q)，即这个事件自身的编码。所以Q(q)这个计算就得到了“我”。
从这个角度看，Q(q)其实也就是那个自打印程序。只不过在自打印程序中，我们把数据q同样定义到了函数S(x)之中的q变量上。所以自打印程序S(x)其实已经包含了这个Q(q)。
同样地，Q(q)就相当于那个蒯恩句子：
<u>把“把中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变”中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变</u>
<u>把“把中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变”中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变</u>
所以Q(q)神奇的地方恰恰就在于它让同样一个东西在不同的两个层次上重复了。
====对角线版本的递归定理====
====对角线版本的递归定理====
{| class="wikitable"
{| class="wikitable"
|-
|-
! 程序\数据 !! ''1'' !! ''2'' !! ...... !! ''v'' !! ......
! 程序\数据 !! 1 !! 2 !! ...... !! v !! ......
|-
|-
| ''1'' || ''Φ<sub> Φ<sub>1</sub>(1)</sub>'' || ''Φ<sub> Φ<sub>1</sub>(2)</sub>'' || ...... || ''Φ<sub> Φ<sub>1</sub>(v)</sub>'' || ......
| 1 || Φ<sub> Φ<sub>1</sub>(1)</sub> || Φ<sub> Φ<sub>1</sub>(2)</sub> || ...... || Φ<sub> Φ<sub>1</sub>(v)</sub> || ......
|-
|-
| ''2'' ||''Φ<sub> Φ<sub>2</sub>(1)</sub>'' || ''Φ<sub> Φ<sub>2</sub>(2)</sub>'' || ...... || ''Φ<sub> Φ<sub>2</sub>(v)</sub>'' || ......
| 2 ||Φ<sub> Φ<sub>2</sub>(1)</sub> || Φ<sub> Φ<sub>2</sub>(2)</sub> || ...... || Φ<sub> Φ<sub>2</sub>(v)</sub> || ......
|-
|-
| ...... || ...... || ...... || ...... || ...... || ......
| ...... || ...... || ...... || ...... || ...... || ......
|-
|-
| ''v'' ||''Φ<sub> Φ<sub>v</sub>(1)</sub> = Φ<sub>F (Φ<sub>1</sub>(1)</sub>)'' || ''Φ<sub> Φ<sub>v</sub>(2)</sub> = Φ<sub>F (Φ<sub>2</sub>(2)</sub>)'' || ...... || ''Φ<sub> Φ<sub>v</sub>(v)</sub> = Φ<sub>F (Φ<sub>v</sub>(v)</sub>)'' || ......
| v ||Φ<sub> Φ<sub>v</sub>(1)</sub> = Φ<sub>F (Φ<sub>1</sub>(1)</sub>) || Φ<sub> Φ<sub>v</sub>(2)</sub> = Φ<sub>F (Φ<sub>2</sub>(2)</sub>) || ...... || Φ<sub> Φ<sub>v</sub>(v)</sub> = Φ<sub>F (Φ<sub>v</sub>(v)</sub>) || ......
|-
|-
| ...... || ...... || ...... || ...... || ...... || ......
| ...... || ...... || ...... || ...... || ...... || ......
|}
|}
与表3不同的地方是，此表格中的每一项不再是λ(m,n)了，而是Φ<sub> Φ<sub>m</sub>(n)</sub> ，也就是第k个计算机程序Φ<sub>k</sub> ，其中k为第m个程序作用到第n个数据上所计算出来的结果。如果第m个程序计算第n个数据不停机，则Φ<sub> Φ<sub>m</sub>(n)</sub> 就是一个在任意输入上都没有定义的函数。因此，表中所列的不再是数，而是计算机程序本身，我们稍后将会看到这个区别的重要性。
下面，我们仍然考察那条黄金对角线，它构成了一行：
下面，我们仍然考察那条黄金对角线，它构成了一行：
Φ<sub> Φ<sub>1</sub>(1)</sub> ,Φ<sub> Φ<sub>2</sub>(2)</sub> ,Φ<sub> Φ<sub>3</sub>(3)</sub> ,...,Φ<sub> Φ<sub>n</sub>(n)</sub> ,...
接下来，我们考察任意一个计算机程序F，它可以作用到自然数：Φ<sub> Φ<sub>x</sub>(x)</sub> 的计算结果上。于是我们便得到了一个复合程序FQ(x)F(x(x))。下面考察这样一个由不同的程序构成的行：
注意，这一行的每一个下标都是F作用于黄金对角线的下标的结果。这里面的每一个元素都是一个程序F(x(x))(y)，其中y为该程序的输入参数，它相当于一个具有两个输入变量的程序，这样由递归函数论中的s-m-n定理（参见：《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》中的s-m-n定理），必然存在某一个单一输入变量的程序V(x)，使得对任意的y有：
注意，这一行的每一个下标都是F作用于黄金对角线的下标的结果。这里面的每一个元素都是一个程序F(x(x))(y)，其中y为该程序的输入参数，它相当于一个具有两个输入变量的程序，这样由递归函数论中的s-m-n定理（参见：《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》中的s-m-n定理），必然存在某一个单一输入变量的程序V(x)，使得对任意的y有：