7,129
个编辑
更改
跳到导航
跳到搜索
第688行：
第688行： + + + + 第715行：
第719行： + + + + + + + + + + + + 第762行：
第778行： + + + + + + + 第884行：
第907行： + + 第904行：
第929行： + + + + 第931行：
第960行： + + + + + + 第964行：
第999行： + + + + + 第993行：
第1,033行： + + + +
→黄金对角线3
我们这里所说的黄金对角线是一种证明方法，它起源于数学家康托尔证明实数的个数比自然数多的过程中所用的一个特殊的技巧。
我们这里所说的黄金对角线是一种证明方法，它起源于数学家康托尔证明实数的个数比自然数多的过程中所用的一个特殊的技巧。
首先，康托尔定义对于两个超限集合（元素个数是无穷个）A和B来说，如果能找到一个单射f:A→B（即任给一个A中的元素，都存在唯一的B中元素与其对应），那么就称A集合的元素个数c(A)<=c(B)，即B集合的元素个数。反过来，如果存在单射g:B→A，那么就有c(B)<=c(A)。而如果c(A)<=c(B)和c(B)<=c(A)同时成立，就说c(B)=c(A)。
首先，康托尔定义对于两个超限集合（元素个数是无穷个）A和B来说，如果能找到一个单射f:A→B（即任给一个A中的元素，都存在唯一的B中元素与其对应），那么就称A集合的元素个数c(A)<=c(B)，即B集合的元素个数。反过来，如果存在单射g:B→A，那么就有c(B)<=c(A)。而如果c(A)<=c(B)和c(B)<=c(A)同时成立，就说c(B)=c(A)。
有了比较两个无穷集合元素个数的方法，我们就可以证明自然数集合N与偶数集合E的个数一样多。因为存在着单射f:N→E，f(x)=2x，同时存在单射g:E→N，g(x)=x/2。所以c(E)=c(N)。
有了比较两个无穷集合元素个数的方法，我们就可以证明自然数集合N与偶数集合E的个数一样多。因为存在着单射f:N→E，f(x)=2x，同时存在单射g:E→N，g(x)=x/2。所以c(E)=c(N)。
下面，我们来比较实数集合R和自然数集合N的元素个数的多少。首先，我们很容易构造一个从N到R的单射f:N→R,f(x)=x。所以c(N)<=c(R)。
下面，我们来比较实数集合R和自然数集合N的元素个数的多少。首先，我们很容易构造一个从N到R的单射f:N→R,f(x)=x。所以c(N)<=c(R)。
接下来，是否存在从R到N的单射呢？答案是不存在，我们可以用反证法来证明。我们可以先把问题简化，仅仅看从[0,1]这个闭区间到自然数集合N存在一个单射g。这也就意味着，对于任意的[0,1]之间的实数x，都唯一存在着一个确定的自然数n与它对应。我们称n为x的编号。我们不妨按照x的编号大小写下这些实数而形成一个表格：
接下来，是否存在从R到N的单射呢？答案是不存在，我们可以用反证法来证明。我们可以先把问题简化，仅仅看从[0,1]这个闭区间到自然数集合N存在一个单射g。这也就意味着，对于任意的[0,1]之间的实数x，都唯一存在着一个确定的自然数n与它对应。我们称n为x的编号。我们不妨按照x的编号大小写下这些实数而形成一个表格：
假设我们可以将[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….
也就是该数字d的第n位d(n)为：
也就是该数字d的第n位d(n)为：
d(n)=(Q(n)+1) mod 10
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。
不难发现，对于任意的单射g，我们总可以构造出一个对角线元素d不在表中，所以，我们只能否认一开始的假设：R与N之间存在单射。于是不可能有c(R)<=c(N)，也就是实数的个数比自然数多。
不难发现，对于任意的单射g，我们总可以构造出一个对角线元素d不在表中，所以，我们只能否认一开始的假设：R与N之间存在单射。于是不可能有c(R)<=c(N)，也就是实数的个数比自然数多。
康托尔的这种巧妙的对角线证明方法正是我们前面讨论的自指方法，对角线Q(n)也正是蒯恩函数，我们马上就会对此明朗了。
康托尔的这种巧妙的对角线证明方法正是我们前面讨论的自指方法，对角线Q(n)也正是蒯恩函数，我们马上就会对此明朗了。
====康托尔的黄金对角线====
====康托尔的黄金对角线====
我们这里所说的黄金对角线是一种证明方法，它起源于数学家康托尔证明实数的个数比自然数多的过程中所用的一个特殊的技巧。
我们这里所说的黄金对角线是一种证明方法，它起源于数学家康托尔证明实数的个数比自然数多的过程中所用的一个特殊的技巧。
首先，康托尔定义对于两个超限集合（元素个数是无穷个）A和B来说，如果能找到一个单射f:A→B（即任给一个A中的元素，都存在唯一的B中元素与其对应），那么就称A集合的元素个数c(A)<=c(B)，即B集合的元素个数。反过来，如果存在单射g:B→A，那么就有c(B)<=c(A)。而如果c(A)<=c(B)和c(B)<=c(A)同时成立，就说c(B)=c(A)。
首先，康托尔定义对于两个超限集合（元素个数是无穷个）A和B来说，如果能找到一个单射f:A→B（即任给一个A中的元素，都存在唯一的B中元素与其对应），那么就称A集合的元素个数c(A)<=c(B)，即B集合的元素个数。反过来，如果存在单射g:B→A，那么就有c(B)<=c(A)。而如果c(A)<=c(B)和c(B)<=c(A)同时成立，就说c(B)=c(A)。
有了比较两个无穷集合元素个数的方法，我们就可以证明自然数集合N与偶数集合E的个数一样多。因为存在着单射f:N→E，f(x)=2x，同时存在单射g:E→N，g(x)=x/2。所以c(E)=c(N)。
有了比较两个无穷集合元素个数的方法，我们就可以证明自然数集合N与偶数集合E的个数一样多。因为存在着单射f:N→E，f(x)=2x，同时存在单射g:E→N，g(x)=x/2。所以c(E)=c(N)。
下面，我们来比较实数集合R和自然数集合N的元素个数的多少。首先，我们很容易构造一个从N到R的单射f:N→R,f(x)=x。所以c(N)<=c(R)。
下面，我们来比较实数集合R和自然数集合N的元素个数的多少。首先，我们很容易构造一个从N到R的单射f:N→R,f(x)=x。所以c(N)<=c(R)。
接下来，是否存在从R到N的单射呢？答案是不存在，我们可以用反证法来证明。我们可以先把问题简化，仅仅看从[0,1]这个闭区间到自然数集合N存在一个单射g。这也就意味着，对于任意的[0,1]之间的实数x，都唯一存在着一个确定的自然数n与它对应。我们称n为x的编号。我们不妨按照x的编号大小写下这些实数而形成一个表格：
接下来，是否存在从R到N的单射呢？答案是不存在，我们可以用反证法来证明。我们可以先把问题简化，仅仅看从[0,1]这个闭区间到自然数集合N存在一个单射g。这也就意味着，对于任意的[0,1]之间的实数x，都唯一存在着一个确定的自然数n与它对应。我们称n为x的编号。我们不妨按照x的编号大小写下这些实数而形成一个表格：
假设我们可以将[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….
也就是该数字d的第n位d(n)为：
也就是该数字d的第n位d(n)为：
d(n)=(Q(n)+1) mod 10
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。
不难发现，对于任意的单射g，我们总可以构造出一个对角线元素d不在表中，所以，我们只能否认一开始的假设：R与N之间存在单射。于是不可能有c(R)<=c(N)，也就是实数的个数比自然数多。
不难发现，对于任意的单射g，我们总可以构造出一个对角线元素d不在表中，所以，我们只能否认一开始的假设：R与N之间存在单射。于是不可能有c(R)<=c(N)，也就是实数的个数比自然数多。
康托尔的这种巧妙的对角线证明方法正是我们前面讨论的自指方法，对角线Q(n)也正是蒯恩函数，我们马上就会对此明朗了。
康托尔的这种巧妙的对角线证明方法正是我们前面讨论的自指方法，对角线Q(n)也正是蒯恩函数，我们马上就会对此明朗了。
====程序的黄金对角线与“自我”====
====程序的黄金对角线与“自我”====
这样，我们只要取cv(v)就得到了递归定理：
这样，我们只要取cv(v)就得到了递归定理：
cF(c)（3）
cF(c)（3）
下面我们来说明为什么表4上的每一个元素是m(n)而不是n(m)。首先，我们知道n(m)是一个数即第n个程序计算第m个输入数据时候的计算结果，而m(n)是一个程序。这样，当我们说n(m)k(m)的时候仅仅意味着两个数相等，即第n个程序作用到m上的输出结果与第k个程序作用到m上的输出结果是一样的。但是这并不意味着对于任意的输入数据m都有此等式成立。
下面我们来说明为什么表4上的每一个元素是m(n)而不是n(m)。首先，我们知道n(m)是一个数即第n个程序计算第m个输入数据时候的计算结果，而m(n)是一个程序。这样，当我们说n(m)k(m)的时候仅仅意味着两个数相等，即第n个程序作用到m上的输出结果与第k个程序作用到m上的输出结果是一样的。但是这并不意味着对于任意的输入数据m都有此等式成立。
而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)和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)。
也许你会好奇，如果在证明递归定理的过程中，表格的所有的项目是n(m)而不是m(n)会怎样？为了满足你的好奇心，我们不妨把此表格列出：
也许你会好奇，如果在证明递归定理的过程中，表格的所有的项目是n(m)而不是m(n)会怎样？为了满足你的好奇心，我们不妨把此表格列出：
(3)式与(1)式略有不同。(1)式为F(c)这个事件的编码，而(3)为数F(c)。但实际上，只要我们适当地选择程序F’为计算得到FQ作用到x上这个事件的编码，那么根据(3)式便能得到(1)式。所以二者实际上是等价的。
(3)式与(1)式略有不同。(1)式为F(c)这个事件的编码，而(3)为数F(c)。但实际上，只要我们适当地选择程序F’为计算得到FQ作用到x上这个事件的编码，那么根据(3)式便能得到(1)式。所以二者实际上是等价的。
<div style="text-align: center;">表5 所有的程序-数据计算结果表</div>
<div style="text-align: center;">表5 所有的程序-数据计算结果表</div>
1(1),2(2),...,x(x),...
1(1),2(2),...,x(x),...
然后再考虑一个任意的计算机程序F。我让它作用到这条对角线上，也就是计算F(x(x))。这可以被看作一个程序：V(x)，它的编码记为v。那么它也必然在表中的某一行（蓝色的行），并且它应与黄金对角线有一个交点，我们把它染成了绿色。在这一点上，我们得到了F这个函数的一个不动点（fixedpoint），即F(c)=c，其中这个cv(v)。但是，等等，你不觉得此结论有问题吗？
然后再考虑一个任意的计算机程序F。我让它作用到这条对角线上，也就是计算F(x(x))。这可以被看作一个程序：V(x)，它的编码记为v。那么它也必然在表中的某一行（蓝色的行），并且它应与黄金对角线有一个交点，我们把它染成了绿色。在这一点上，我们得到了F这个函数的一个不动点（fixedpoint），即F(c)=c，其中这个cv(v)。但是，等等，你不觉得此结论有问题吗？
我们知道F是一个任意的计算机程序，简单起见我们不妨设F(x)=x+1。那么根据刚才的推理，存在着一个数c使得F(c)=c，也就是c=c+1。注意，这里面的c是一个数，但是一个数怎么可能满足c=c+1呢？
我们知道F是一个任意的计算机程序，简单起见我们不妨设F(x)=x+1。那么根据刚才的推理，存在着一个数c使得F(c)=c，也就是c=c+1。注意，这里面的c是一个数，但是一个数怎么可能满足c=c+1呢？
我们得到了矛盾，哪一步出了问题？
我们得到了矛盾，哪一步出了问题？
我认为矛盾发生在空值Null上。不要忘记，表5中存在着很多空值，它表示对应的程序计算对应的数据上的时候不停机。这样，尽管程序F可以是处处定义的可计算程序，但是当它作用到不停机的程序上时，它自己也停不下来，于是也只能取空值。这样，对于某些程序F，如果找不到自然数c让F(c)=c成立的时候，就必然意味着v(v)这个计算是不停机的。
我认为矛盾发生在空值Null上。不要忘记，表5中存在着很多空值，它表示对应的程序计算对应的数据上的时候不停机。这样，尽管程序F可以是处处定义的可计算程序，但是当它作用到不停机的程序上时，它自己也停不下来，于是也只能取空值。这样，对于某些程序F，如果找不到自然数c让F(c)=c成立的时候，就必然意味着v(v)这个计算是不停机的。
有趣的是，康托尔的证明以及下面所讲的破坏性自指的黄金对角线等方法恰恰是利用了与此类似的技巧。只不过，在那里的对角线中，我们能够事先保证v(v)是非空的数值。于是我们只能得到诸如c=c+1的矛盾，从而返回去否定前提的成立。
有趣的是，康托尔的证明以及下面所讲的破坏性自指的黄金对角线等方法恰恰是利用了与此类似的技巧。只不过，在那里的对角线中，我们能够事先保证v(v)是非空的数值。于是我们只能得到诸如c=c+1的矛盾，从而返回去否定前提的成立。
====破坏性自指的黄金对角线====
====破坏性自指的黄金对角线====
其中，每一项H(m,n)就要么是0要么是1。这样，上面的黄金对角线上的数值就应该相应地取为一个01的序列，我们不妨设这个序列为：
其中，每一项H(m,n)就要么是0要么是1。这样，上面的黄金对角线上的数值就应该相应地取为一个01的序列，我们不妨设这个序列为：
仿照小节（1）中康托尔构造的实数d，我们可以构造这样一个“对角线删除”程序如下：
仿照小节（1）中康托尔构造的实数d，我们可以构造这样一个“对角线删除”程序如下：
那么，这个程序D(x)所得到的计算结果就应该与对角线序列完全相反，也就是：
那么，这个程序D(x)所得到的计算结果就应该与对角线序列完全相反，也就是：
我们知道D(1)运算的结果与该列表中的第一行不同，D(2)与第2行不同，...，所以D(x)这个序列与列表中的每一行都不同，也就意味着D(n)这个序列不在列表中。但是，我们知道此表已经列出了所有的程序。这就得到了矛盾，于是我们得出结论，H这个函数本身的存在性应该受到质疑。
我们知道D(1)运算的结果与该列表中的第一行不同，D(2)与第2行不同，...，所以D(x)这个序列与列表中的每一行都不同，也就意味着D(n)这个序列不在列表中。但是，我们知道此表已经列出了所有的程序。这就得到了矛盾，于是我们得出结论，H这个函数本身的存在性应该受到质疑。
下面我们再给出另外一个图灵停机问题不可解性的证明，在这个证明中，你将能更清楚地看到对角线方法、破坏性自指、悖论之间的联系。
下面我们再给出另外一个图灵停机问题不可解性的证明，在这个证明中，你将能更清楚地看到对角线方法、破坏性自指、悖论之间的联系。
与以上的证明不同，我们并不直接否定掉D函数不在表6中的事实，而是假设它在该表中，并且它的编号是d，这样我们就得到了如下表格：
与以上的证明不同，我们并不直接否定掉D函数不在表6中的事实，而是假设它在该表中，并且它的编号是d，这样我们就得到了如下表格：
让我们把目光锁定到蓝色的第d行。如果说D这个程序在列表中，并且d就是D的编码，那么这第d行必然会跟黄金对角线在表中有一个交点（绿色格子），按照对角线的定义法则，这个交点对应的元素必然会是H(d,d)。
让我们把目光锁定到蓝色的第d行。如果说D这个程序在列表中，并且d就是D的编码，那么这第d行必然会跟黄金对角线在表中有一个交点（绿色格子），按照对角线的定义法则，这个交点对应的元素必然会是H(d,d)。
但是，请不要忘记，按照D(n)这个函数的定义，D(n)=1-H(n,n)，所以当n=d的时候，D(d)就应该等于1-H(d,d)。
但是，请不要忘记，按照D(n)这个函数的定义，D(n)=1-H(n,n)，所以当n=d的时候，D(d)就应该等于1-H(d,d)。
H(d,d)与1-H(d,d)无论如何都不可能相等（注意，这里H(d,d)要么是0要么是1，绝无可能是空值）。也就是说H(d,d)说停机的时候，1-H(d,d)就说不停机，而H(d,d)说不停机的时候，1-H(d,d)就说停机。因此，我们只能得到矛盾。在整个推理的链条中，只有第一个环节，即H函数是存在的出现了问题。
H(d,d)与1-H(d,d)无论如何都不可能相等（注意，这里H(d,d)要么是0要么是1，绝无可能是空值）。也就是说H(d,d)说停机的时候，1-H(d,d)就说不停机，而H(d,d)说不停机的时候，1-H(d,d)就说停机。因此，我们只能得到矛盾。在整个推理的链条中，只有第一个环节，即H函数是存在的出现了问题。
实际上，这种对角线证明图灵停机问题的方法与第5节中构造自指程序的方法是相通的，尽管它们在表面上看似乎很不相同。首先，第5节中的程序D(z)实际上就是这里的程序D(n)。只不过D(z)通过判断语句和实际的死循环实现了与H(z,z)判断相反的结果，而这里的D(n)通过1-H(n,n)这样一步数学运算就实现了相同的效果。其次，在第5节中的第二步，将z=d代入D函数自己其实就相当于本节第二个方法中的对角线与蓝色的第d行的交点元素H(d,d)。最后，本节的方法1的独到之处就是在于，它直接分析D(d)这个函数计算的结果与H(1,1)不同，与H(2,2)不同，...，从而导致了D(n)不可能在列表中。以至于该方法不用分析到H(d,d)这个元素上就能完成H不存在的证明。
实际上，这种对角线证明图灵停机问题的方法与第5节中构造自指程序的方法是相通的，尽管它们在表面上看似乎很不相同。首先，第5节中的程序D(z)实际上就是这里的程序D(n)。只不过D(z)通过判断语句和实际的死循环实现了与H(z,z)判断相反的结果，而这里的D(n)通过1-H(n,n)这样一步数学运算就实现了相同的效果。其次，在第5节中的第二步，将z=d代入D函数自己其实就相当于本节第二个方法中的对角线与蓝色的第d行的交点元素H(d,d)。最后，本节的方法1的独到之处就是在于，它直接分析D(d)这个函数计算的结果与H(1,1)不同，与H(2,2)不同，...，从而导致了D(n)不可能在列表中。以至于该方法不用分析到H(d,d)这个元素上就能完成H不存在的证明。
利用黄金对角线方法也同样可以分析哥德尔定理的证明等其它的破坏性自指现象（读者不妨分析一下如何用对角线方法来构造哥德尔定理的证明）。也就是说，黄金对角线方法与自指方法是一脉相承的；因此多书上，蒯恩函数也被称为对角线函数（例如：《[http://ebooklink.net/g/detail/0198534507/Diagonalization%20and%20Self-Reference%20%28Oxford%20Logic%20Guides%29/ Diagonalization and Self-Reference]》）。
利用黄金对角线方法也同样可以分析哥德尔定理的证明等其它的破坏性自指现象（读者不妨分析一下如何用对角线方法来构造哥德尔定理的证明）。也就是说，黄金对角线方法与自指方法是一脉相承的；因此多书上，蒯恩函数也被称为对角线函数（例如：《[http://ebooklink.net/g/detail/0198534507/Diagonalization%20and%20Self-Reference%20%28Oxford%20Logic%20Guides%29/ Diagonalization and Self-Reference]》）。