更改
跳到导航
跳到搜索
第667行：
第667行： − + − + − + − + − 与表3不同的地方是，此表格中的每一项不再是λ(m,n)了，而是m(n)，也就是第k个计算机程序k，其中k为第m个程序作用到第n个数据上所计算出来的结果。如果第m个程序计算第n个数据不停机，则+ − m(n)就是一个在任意输入上都没有定义的函数。因此，表中所列的不再是数，而是计算机程序本身，我们稍后将会看到这个区别的重要性。 − 接下来，我们考察任意一个计算机程序F，它可以作用到自然数：x(x)的计算结果上。于是我们便得到了一个复合程序FQ(x)F(x(x))。下面考察这样一个由不同的程序构成的行：+ + +
→对角线版本的递归定理
{| 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有：