更改

跳到导航 跳到搜索

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

2016年9月19日 (一) 10:03的版本

删除18字节 、 2016年9月19日 (一) 10:03
无编辑摘要
第716行： 第716行：  
! 程序\数据 !! 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> 就是一个在任意输入上都没有定义的函数。因此，表中所列的不再是数，而是计算机程序本身，我们稍后将会看到这个区别的重要性。
+
与表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> ,...
+
Φ<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> 的计算结果上。于是我们便得到了一个复合程序FQ(x)F(x(x))。下面考察这样一个由不同的程序构成的行：
+
接下来，我们考察任意一个计算机程序F，它可以作用到自然数：Φ<sub>Φ<sub>x</sub>(x)</sub> 的计算结果上。于是我们便得到了一个复合程序FQ(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有：
取自“https://wiki.swarma.org/index.php/特殊:移动版差异/4944”

导航菜单