更改
跳到导航
跳到搜索
第658行：
第658行： − − 这样的编码函数λ是存在的，例如取λ(f,x)=23。则对任意的自然数组合(f,x)，都有唯一的自然数λ(f,x)作为这对自然树的编码。 第708行：
第706行： + 第713行：
第712行： + + 第719行：
第720行： + +
无编辑摘要
所以Q(q)神奇的地方恰恰就在于它让同样一个东西在不同的两个层次上重复了。
所以Q(q)神奇的地方恰恰就在于它让同样一个东西在不同的两个层次上重复了。
====对角线版本的递归定理====
====对角线版本的递归定理====
而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>
<ref>
f(x){
f(x){
}
}
</ref>
</ref>
和：
和：
<ref>
<ref>
g(x){
g(x){
}
}
</ref>ref>
</ref>ref>
很显然f(x)和g(x)是两个不同的程序，因为它们的源代码不同，这样它们的编码也必然不同。但是，我们看到这两个函数实际上是等效的，因为它们都进行x+1的计算，所以f=g是成立的。
很显然f(x)和g(x)是两个不同的程序，因为它们的源代码不同，这样它们的编码也必然不同。但是，我们看到这两个函数实际上是等效的，因为它们都进行x+1的计算，所以f=g是成立的。
因此，递归定理中所说的cF(c)，指的就是编码为c的函数和编码为F(c)的函数等效，但这并不意味着c等于F(c)。
因此，递归定理中所说的cF(c)，指的就是编码为c的函数和编码为F(c)的函数等效，但这并不意味着c等于F(c)。