7,129
个编辑
更改
跳到导航
跳到搜索
第914行：
第914行： − <ref> − </ref> − <ref> − </ref>ref> 第975行：
第971行： −
→对角线版本的递归定理
而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的计算效果都等效。例如我们考察下面两个计算机程序：
f(x){
f(x){
return(x+1);
return(x+1);
}
}
和：
和：
g(x){
g(x){
return(x+2-1);
return(x+2-1);
}
}
很显然f(x)和g(x)是两个不同的程序，因为它们的源代码不同，这样它们的编码也必然不同。但是，我们看到这两个函数实际上是等效的，因为它们都进行x+1的计算，所以f=g是成立的。
很显然f(x)和g(x)是两个不同的程序，因为它们的源代码不同，这样它们的编码也必然不同。但是，我们看到这两个函数实际上是等效的，因为它们都进行x+1的计算，所以f=g是成立的。
有趣的是，康托尔的证明以及下面所讲的破坏性自指的黄金对角线等方法恰恰是利用了与此类似的技巧。只不过，在那里的对角线中，我们能够事先保证v(v)是非空的数值。于是我们只能得到诸如c=c+1的矛盾，从而返回去否定前提的成立。
有趣的是，康托尔的证明以及下面所讲的破坏性自指的黄金对角线等方法恰恰是利用了与此类似的技巧。只不过，在那里的对角线中，我们能够事先保证v(v)是非空的数值。于是我们只能得到诸如c=c+1的矛盾，从而返回去否定前提的成立。
====破坏性自指的黄金对角线====
====破坏性自指的黄金对角线====