更改

跳到导航 跳到搜索

系统中的观察者(5)——自指 (查看源代码)

2016年9月17日 (六) 19:50的版本

添加2,244字节 、 2016年9月17日 (六) 19:50
无编辑摘要
第577行： 第577行：  
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
−
! 自然数\实数位 !!   1   !!   2   !!   ......   !!   N   !!   ......  
+
! 自然数\实数位 !! 1 !! 2 !! ...... !! N !! ......
 
|-
 
|-
 
| 1 || 1 || 3 || ...... || 8 || ......
 
| 1 || 1 || 3 || ...... || 8 || ......
第590行： 第590行：  
|}
 
|}
   −
假设我们可以将[0,1]之间的所有自然数放置到一张无穷行、无穷列的表格上。每一行就是一个实数，某一行的每一列就表示该实数小数点后面的第n位数字。例如第一个实数的第1、2、„„、n、„„列分别是1、3、„„、8、„„，那么这个小数就是0.13…8…。
+
假设我们可以将[0,1]之间的所有自然数放置到一张无穷行、无穷列的表格上。每一行就是一个实数，某一行的每一列就表示该实数小数点后面的第n位数字。例如第一个实数的第1、2、...、n、...列分别是1、3、...、8、...，那么这个小数就是0.13…8…。
   −
下面我们考察对角线上面的元素（黄色的方格）。它表示第1个实数小数点后第一位的数字1，第2个实数小数点后第二位的数字7，„„。假设第n个对角线上的数字为Q(n)，那么我们构造一个特殊的数字d：
+
下面我们考察对角线上面的元素（黄色的方格）。它表示第1个实数小数点后第一位的数字1，第2个实数小数点后第二位的数字7，...。假设第n个对角线上的数字为Q(n)，那么我们构造一个特殊的数字d：
    
0.28….6….
 
0.28….6….
第598行： 第598行：  
也就是该数字d的第n位d(n)为：
 
也就是该数字d的第n位d(n)为：
   −
d(n)=(Q(n)+1)mod10
+
d(n)=(Q(n)+1) mod 10
   −
那么，很显然d是一个[0,1]之间的实数，但是d并不在表格2中，因为d的第一个位与第一个实数的第一个数字不同，所以d不是第一个数字；d的第二个位与第二个实数的第二个数字不同，所以d不是第二个数字，„„。所以d肯定不在表2之中。
+
那么，很显然d是一个[0,1]之间的实数，但是d并不在表格2中，因为d的第一个位与第一个实数的第一个数字不同，所以d不是第一个数字；d的第二个位与第二个实数的第二个数字不同，所以d不是第二个数字，...。所以d肯定不在表2之中。
    
于是，我们便可以推知，表2并不是一张完整的从[0,1]到N的映射。存在着漏网之鱼：实数d。
 
于是，我们便可以推知，表2并不是一张完整的从[0,1]到N的映射。存在着漏网之鱼：实数d。
第610行： 第610行：  
====程序的黄金对角线与“自我”====
 
====程序的黄金对角线与“自我”====
   −
下面，我们将进入计算机程序的世界。首先，让我们把考虑的计算机程序设定到自然数范围内，也就是说程序F(x)中的输入x是自然数，F(x)的计算结果也是自然数。我们知道计算机程序都是有限的指令组成的字符串，于是我们可以为这些字符串编号。所以，任何程序F都对应了一个自然数编码f，而输入变量x也是自然数，我们还可以定义一个函数λ(f,x)来对程序“把数据x输入给函数F”这个事件编码，其中λ(f,t)也是一个自然数。
+
下面，我们将进入计算机程序的世界。首先，让我们把考虑的计算机程序设定到自然数范围内，也就是说程序F(x)中的输入x是自然数，F(x)的计算结果也是自然数。我们知道计算机程序都是有限的指令组成的字符串，于是我们可以为这些字符串编号。所以，任何程序F都对应了一个自然数编码f，而输入变量x也是自然数，我们还可以定义一个函数λ(f,x)来对程序“把数据x输入给函数F”这个事件编码，其中λ(f,t)也是一个自然数<sup>4</sup>。
    
既然所有程序和输入数据都编好号了，我们便可以把所有的程序针对所有的输入数据的运算情况画在下面的大表格上：
 
既然所有程序和输入数据都编好号了，我们便可以把所有的程序针对所有的输入数据的运算情况画在下面的大表格上：
第616行： 第616行：  
<div style="text-align: center;">表3：程序与数据的列表</div>
 
<div style="text-align: center;">表3：程序与数据的列表</div>
    +
{| class="wikitable"
 +
|-
 +
! 程序\数据 !! 1 !! 2 !! ...... !! q !! ......
 +
|-
 +
| 1 || λ(1,1) || λ(1,1) || ...... || λ(1,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) || ......
 +
|-
 +
| ...... || ...... || ...... || ...... || ...... || ......
 +
|}
   −
 
+
其中，λ(n,m)就表示第n个程序计算输入数据m这个事件的编码。下面我们来考察那条黄金色的
−
其中，(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(x)：
   −
Q(1),Q(2),Q(3),…,Q(n),….
+
Q(1),Q(2),Q(3),...,Q(n),...
    
我们只要定义程序Q为：
 
我们只要定义程序Q为：
第636行： 第649行：  
既然Q是可计算的，那么它必然也会占据表格中的某一行（表3中的粉色的行，设这行编码为q）。注意在这行中，我们列出了两个数值，上面的数值为程序Q作用到数据x的编码，即λ(q,x)，下面的数值为函数值Q(x)=λ(x,x)。对于一般的x来说，这两个数值没什么关系。但是，粉红行与黄金对角线的交点（桔色的格子）是个意外，它的上下两个数值发生了重合。
 
既然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)其实也就是那个自打印程序。只不过在自打印程序中，我们把数据q同样定义到了函数S(x)之中的q变量上。所以自打印程序S(x)其实已经包含了这个Q(q)。
第642行： 第655行：  
同样地，Q(q)就相当于那个蒯恩句子：
 
同样地，Q(q)就相当于那个蒯恩句子：
   −
把‚把中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变‛中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变
+
<u>把“把中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变”中的第一个字放到左引号前面，其余的字放到右引号后面，并保持引号及其中的字不变</u>
    
所以Q(q)神奇的地方恰恰就在于它让同样一个东西在不同的两个层次上重复了。
 
所以Q(q)神奇的地方恰恰就在于它让同样一个东西在不同的两个层次上重复了。
第650行： 第663行：  
====对角线版本的递归定理====
 
====对角线版本的递归定理====
   −
利用对角线这种几何方法，我们同样可以说明递归定理必然成立（参看《Computability:anintroduction torecursivefunctiontheory》）。首先，我们仿照表3构造另外一个表：
+
利用对角线这种几何方法，我们同样可以说明递归定理必然成立（参看《[https://book.douban.com/subject/1437118/ Computability: an introductionto recursive function theory]》）。首先，我们仿照表3构造另外一个表：
    
<div style="text-align: center;">表4递归定理所用的程序-数据表</div>
 
<div style="text-align: center;">表4递归定理所用的程序-数据表</div>
   −
 
+
{| class="wikitable"
 +
|-
 +
! 程序\数据 !! 1 !! 2 !! ...... !! q !! ......
 +
|-
 +
| 1 || λ(1,1) || λ(1,1) || ...... || λ(1,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) || ......
 +
|-
 +
| ...... || ...... || ...... || ...... || ...... || ......
 +
|}
    
与表3不同的地方是，此表格中的每一项不再是λ(m,n)了，而是m(n)，也就是第k个计算机程序k，其中k为第m个程序作用到第n个数据上所计算出来的结果。如果第m个程序计算第n个数据不停机，则
 
与表3不同的地方是，此表格中的每一项不再是λ(m,n)了，而是m(n)，也就是第k个计算机程序k，其中k为第m个程序作用到第n个数据上所计算出来的结果。如果第m个程序计算第n个数据不停机，则
第663行： 第689行：  
接下来，我们考察任意一个计算机程序F，它可以作用到自然数：x(x)的计算结果上。于是我们便得到了一个复合程序FQ(x)F(x(x))。下面考察这样一个由不同的程序构成的行：
 
接下来，我们考察任意一个计算机程序F，它可以作用到自然数：x(x)的计算结果上。于是我们便得到了一个复合程序FQ(x)F(x(x))。下面考察这样一个由不同的程序构成的行：
   −
注意，这一行的每一个下标都是F作用于黄金对角线的下标的结果。这里面的每一个元素都是一个程序F(x(x))(y)，其中y为该程序的输入参数，它相当于一个具有两个输入变量的程序，这样由递归函数论中的s-m-n定理（参见：《Computability:anintroductiontorecursivefunctiontheory》中的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有：
    
F(x(x))(y)V(x)(y)
 
F(x(x))(y)V(x)(y)
第682行： 第708行：     
而n(m)k(m)恰恰表示计算机程序的等效。也就意味着对于任意的输入数据x来说，都有：n(m)(x)k(m)(x)。我们知道严格来说等式左边的程序编号是n(m)而右侧是k(m)，这两个数字不一定相等。但是，这并不妨碍这两个程序对于所有的输入数据x的计算效果都等效。例如我们考察下面两个计算机程序：
 
而n(m)k(m)恰恰表示计算机程序的等效。也就意味着对于任意的输入数据x来说，都有：n(m)(x)k(m)(x)。我们知道严格来说等式左边的程序编号是n(m)而右侧是k(m)，这两个数字不一定相等。但是，这并不妨碍这两个程序对于所有的输入数据x的计算效果都等效。例如我们考察下面两个计算机程序：
 +
<ref>
 
f(x){
 
f(x){
−
return(x+1);
+
    return(x+1);
 
}
 
}
−
 
+
</ref>
 
和：
 
和：
−
 
+
<ref>
 
g(x){
 
g(x){
−
return(x+2-1);
+
    return(x+2-1);
 
}
 
}
−
 
+
</ref>ref>
 
很显然f(x)和g(x)是两个不同的程序，因为它们的源代码不同，这样它们的编码也必然不同。但是，我们看到这两个函数实际上是等效的，因为它们都进行x+1的计算，所以f=g是成立的。
 
很显然f(x)和g(x)是两个不同的程序，因为它们的源代码不同，这样它们的编码也必然不同。但是，我们看到这两个函数实际上是等效的，因为它们都进行x+1的计算，所以f=g是成立的。
 
因此，递归定理中所说的cF(c)，指的就是编码为c的函数和编码为F(c)的函数等效，但这并不意味着c等于F(c)。
 
因此，递归定理中所说的cF(c)，指的就是编码为c的函数和编码为F(c)的函数等效，但这并不意味着c等于F(c)。
第699行： 第726行：  
(3)式与(1)式略有不同。(1)式为F(c)这个事件的编码，而(3)为数F(c)。但实际上，只要我们适当地选择程序F’为计算得到FQ作用到x上这个事件的编码，那么根据(3)式便能得到(1)式。所以二者实际上是等价的。
 
(3)式与(1)式略有不同。(1)式为F(c)这个事件的编码，而(3)为数F(c)。但实际上，只要我们适当地选择程序F’为计算得到FQ作用到x上这个事件的编码，那么根据(3)式便能得到(1)式。所以二者实际上是等价的。
   −
表5所有的程序-数据计算结果表
+
<div style="text-align: center;">表5 所有的程序-数据计算结果表</div>
    +
{| class="wikitable"
 +
|-
 +
! 程序\数据 !! 1 !! 2 !! ...... !! q !! ......
 +
|-
 +
| 1 || λ(1,1) || λ(1,1) || ...... || λ(1,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) || ......
 +
|-
 +
| ...... || ...... || ...... || ...... || ...... || ......
 +
|}
    
此表与表4的不同所在是每个表项m(n)表示的是第m个程序作用到数字n上面的运算结果，而不是对此事件的编码。如果这个计算不停机，则我们可以把相应的值赋为Null。仿照表4中的推理逻辑。同样地，我们可以将黄金对角线单独列出：
 
此表与表4的不同所在是每个表项m(n)表示的是第m个程序作用到数字n上面的运算结果，而不是对此事件的编码。如果这个计算不停机，则我们可以把相应的值赋为Null。仿照表4中的推理逻辑。同样地，我们可以将黄金对角线单独列出：
第722行： 第763行：  
<div style="text-align: center;">表6图灵停机判别表</div>
 
<div style="text-align: center;">表6图灵停机判别表</div>
   −
 
+
{| class="wikitable"
 +
|-
 +
! 程序\数据 !! 1 !! 2 !! ...... !! q !! ......
 +
|-
 +
| 1 || λ(1,1) || λ(1,1) || ...... || λ(1,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) || ......
 +
|-
 +
| ...... || ...... || ...... || ...... || ...... || ......
 +
|}
    
其中，每一项H(m,n)就要么是0要么是1。这样，上面的黄金对角线上的数值就应该相应地取为一个01的序列，我们不妨设这个序列为：
 
其中，每一项H(m,n)就要么是0要么是1。这样，上面的黄金对角线上的数值就应该相应地取为一个01的序列，我们不妨设这个序列为：
第738行： 第792行：  
<div style="text-align: center;">表7自指悖论与黄金对角线</div>
 
<div style="text-align: center;">表7自指悖论与黄金对角线</div>
   −
 
+
{| class="wikitable"
 +
|-
 +
! 程序\数据 !! 1 !! 2 !! ...... !! q !! ......
 +
|-
 +
| 1 || λ(1,1) || λ(1,1) || ...... || λ(1,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) || ......
 +
|-
 +
| ...... || ...... || ...... || ...... || ...... || ......
 +
|}
    
让我们把目光锁定到蓝色的第d行。如果说D这个程序在列表中，并且d就是D的编码，那么这第d行必然会跟黄金对角线在表中有一个交点（绿色格子），按照对角线的定义法则，这个交点对应的元素必然会是H(d,d)。
 
让我们把目光锁定到蓝色的第d行。如果说D这个程序在列表中，并且d就是D的编码，那么这第d行必然会跟黄金对角线在表中有一个交点（绿色格子），按照对角线的定义法则，这个交点对应的元素必然会是H(d,d)。
取自“https://wiki.swarma.org/index.php/特殊:移动版差异/4935”

导航菜单