更改
跳到导航
跳到搜索
第610行：
第610行： − 下面，我们将进入计算机程序的世界。首先，让我们把考虑的计算机程序设定到自然数范围内，也就是说程序F(x)中的输入x是自然数，F(x)的计算结果也是自然数。我们知道计算机程序都是有限的指令组成的字符串，于是我们可以为这些字符串编号。所以，任何程序F都对应了一个自然数编码f，而输入变量x也是自然数，我们还可以定义一个函数λ(f,x)来对程序“把数据x输入给函数F”这个事件编码，其中λ(f,t)也是一个自然数<sup>4</sup>。+ 第618行：
第618行： − + − + − + − + − 其中，λ(n,m)就表示第n个程序计算输入数据m这个事件的编码。下面我们来考察那条黄金色的+ − + − 有趣的是，它的第一个元素与第一个程序作用到第一个数据上编码相同，第二个元素与第二个程序作用到第二个数据上相同，„„。这一行的编码可看作一种运算Q(x)：+ − + − 我们只要定义程序Q为：+ − + − 实际上Q(x)就是蒯恩函数，它作用到x上就计算出将编码为x的程序作用到x自身上这个事件的编码。这样，只要我们清晰定义了函数λ，那么Q程序就一定存在。+ − 既然Q是可计算的，那么它必然也会占据表格中的某一行（表3中的粉色的行，设这行编码为q）。注意在这行中，我们列出了两个数值，上面的数值为程序Q作用到数据x的编码，即λ(q,x)，下面的数值为函数值Q(x)=λ(x,x)。对于一般的x来说，这两个数值没什么关系。但是，粉红行与黄金对角线的交点（桔色的格子）是个意外，它的上下两个数值发生了重合。+ − + − 从这个角度看，Q(q)其实也就是那个自打印程序。只不过在自打印程序中，我们把数据q同样定义到了函数S(x)之中的q变量上。所以自打印程序S(x)其实已经包含了这个Q(q)。+ − 同样地，Q(q)就相当于那个蒯恩句子：+ − 所以Q(q)神奇的地方恰恰就在于它让同样一个东西在不同的两个层次上重复了。+
→程序的黄金对角线与“自我”
====程序的黄金对角线与“自我”====
====程序的黄金对角线与“自我”====
下面，我们将进入计算机程序的世界。首先，让我们把考虑的计算机程序设定到自然数范围内，也就是说程序''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),...
''λ(1,1),λ(2,2),λ(3,3),...,λ(n,n),...''
有趣的是，它的第一个元素与第一个程序作用到第一个数据上编码相同，第二个元素与第二个程序作用到第二个数据上相同，...。这一行的编码可看作一种运算''Q(x)''：
Q(1),Q(2),Q(3),...,Q(n),...
''Q(1),Q(2),Q(3),...,Q(n),...''
我们只要定义程序''Q''为：
Q(x):=λ(x,x)
''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,q)''，即这个事件自身的编码。所以''Q(q)''这个计算就得到了“我”。
从这个角度看，''Q(q)''其实也就是那个自打印程序。只不过在自打印程序中，我们把数据''q''同样定义到了函数''S(x)''之中的''q''变量上。所以自打印程序''S(x)''其实已经包含了这个''Q(q)''。
同样地，''Q(q)''就相当于那个蒯恩句子：
<u>把“把中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变”中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变</u>
<u>把“把中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变”中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变</u>
所以''Q(q)''神奇的地方恰恰就在于它让同样一个东西在不同的两个层次上重复了。
====对角线版本的递归定理====
====对角线版本的递归定理====