第5期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） .629. 以上证明是“对角线构造方法”，根据定理， D(x,y)是二元原始递归函数，g(x)也是一元原始 h(k)是不动项函数，h(k)主U。 递归函数，设g(x)=D(x,n),n∈w是递归的，令 根据以上定理，以下推论成立。 x=n,g(n)=D(n,n) 推论17不动项函数h(k)定在U外，h()主U。 g(n)=D(n,n)=D(n,n)+1,矛盾，所以，D(x,y) 推论18不动项函数h(k)是未定义项。 不是二元原始递归函数[6。 推论19不动项函数h(k)是否递归函数，是 推论23ω上存在非递归函数的证明错误。 不可判定命题。 推论24不存在一元递归函数的能行可枚举， 推论20不动项函数h(k)是否递归函数的不 证明错误。 可判定与U内项是否可以判定无关。 6.2 Turing机“停机问题”证明错误 推论21不动项函数h(k)矛盾来源于U外。 Turing证明，Turing机“停机问题”是不可判定 推论22不动项函数h(k)不能作为任何“U 的，即：不存在算法对以下问题类提供答案， 内演算的推理依据”。 {Turing机Tn在输入n后是否会停机Im,n∈ 注记12ω上存在非递归函数，是“对角线证 No 明方法”，证明错误。 回顾一下图灵机“停机问题”的证明过程。 1)递归函数集合是可数的，考察一元递归函数 按照哥德尔编码，给Turing机指定一个编码， 的一个枚举5，…，定义一个函数g:w2→w, 按编码的大小，把所有的Turing机一个不漏的枚举 g(m,n)=fm(n),假设g(m,n)=fm(n)是递归的， 如下：T。,T,T2,…,Tm,…。 h(m)=g(m,m)+1,m∈w是递归的， 定义一个一元函数： h(k)=f(k)=g(k,k)+1=f(k)+1,矛盾，所 (0,Tn输入n后停机： 以，g(m,n)=f(n)不是递归函数)。 f八n)= 1,Tn输入n后不停机。 2)不存在一元递归函数的能行可枚举，是“对 Turing机Tn在输入n后是否会停机的各种情 角线证明方法”。 况排列如表7（表中的所有情况与二进制表示的实 假设存在一元递归函数的能行可枚举，设6， 数等价)。 ∫f,…,是所有一元递归函数的能行枚举，考察下 表7对角线方法“Turing停机问题”定义 列算法：给定n∈w,的枚举f。ff,…,直到找到 Table 7 The "Turing halting problem"define table of di- fn,计算f(n) agonal metho h(n)=f(n)+1,n∈w是递归的 T。 T T h(k)=f(k)=f(k)+1,矛盾，所以，不存在一 元递归函数的能行可枚举)。 f0) 0 1 0 0 1 3)以下定理是“对角线证明方法”，证明错误： f1) 0 0 1 设D(x,y)是一元原始递归函数的通用函数， f(2) 0 1 0 0 则D(x,y)不是二元原始递归函数。 f(3) 0 0 0 0 证明D(x,y)是一元原始递归函数的通用函 f(4) 1 0 0 0 数，所以，全体一元原始递归函数都包含在函数序列 … D(x,0),D(x,1),D(x,2),D(x,3),…中，可以 假设f(n)是Turing可计算函数，那么存在某个 做以下无穷列表： Turing机T来计算f(n)的值，即 表6跨正反集上的真值表 Table 6 The truth value table for crossing the positive and 对任意n∈w,f(n)=0台T输入n后输出0； f(n)=1曰T输入n后输出1。 inverse sets 把上表对角线上的元素挑出来。就可以得到一 个序列：0,1,0,1,0，…，而根据这个序列完全可以 0 2 3 构造这样一个反序列：1,0,1,0,1，…利用反序列， 0D(0.0) D(0.1)D(0.2)D(0.3) 1 D(1.0) D(1,1)D(1,2) D(1,3) 构造一个新的Turing机T,。 g 3 D(2.0) D(2.1)D(2.2)D(2.3) T输入n后输出1台T,输入n后会停机。 3 D(3.0) D(3,1) D(3,2)D(3,3) T是一个新的图灵机，T必然出现在T。,T, T2,…,Tm,…中，设Tg=T。 定义一个一元函数g(x)=D(x,x)+1,如果 T.输入k后会停机台T输入k后输出1台以上证明是 “ 对角线构造方法”， 根据定理， ｈ（ｋ） 是不动项函数， ｈ（ｋ） ∉ Ｕ 。 根据以上定理，以下推论成立。 推论 １７ 不动项函数ｈ（ｋ） 定在Ｕ 外， ｈ（ｋ） ∉Ｕ 。 推论 １８ 不动项函数 ｈ（ｋ） 是未定义项。 推论 １９ 不动项函数 ｈ（ｋ） 是否递归函数，是 不可判定命题。 推论 ２０ 不动项函数 ｈ（ｋ） 是否递归函数的不 可判定与 Ｕ 内项是否可以判定无关。 推论 ２１ 不动项函数 ｈ（ｋ） 矛盾来源于 Ｕ 外。 推论 ２２ 不动项函数 ｈ（ｋ） 不能作为任何“ Ｕ 内演算的推理依据”。 注记 １２ ω 上存在非递归函数，是“对角线证 明方法”，证明错误。 １）递归函数集合是可数的，考察一元递归函数 的一个枚举 ｆ ０ ，ｆ １ ，ｆ ２ ，… ，定义一个函数 ｇ：ω ２ → ω ， ｇ（ｍ，ｎ） ＝ ｆｍ（ｎ） ，假设 ｇ（ｍ，ｎ） ＝ ｆｍ（ｎ） 是递归的， ｈ（ｍ） ＝ ｇ（ｍ，ｍ） ＋ １， ｍ ∈ ω 是递归的， ｈ（ｋ） ＝ ｆ ｋ（ｋ） ＝ ｇ（ｋ，ｋ） ＋ １ ＝ ｆ ｋ（ｋ） ＋ １，矛盾，所 以， ｇ（ｍ，ｎ） ＝ ｆｍ（ｎ） 不是递归函数［３］ 。 ２）不存在一元递归函数的能行可枚举，是“对 角线证明方法”。 假设存在一元递归函数的能行可枚举，设 ｆ ０ ， ｆ １ ，ｆ ２ ，… ，是所有一元递归函数的能行枚举，考察下 列算法：给定 ｎ ∈ ω ，的枚举 ｆ ０ ，ｆ １ ，ｆ ２ ，… ，直到找到 ｆ ｎ ，计算 ｆ ｎ（ｎ） ｈ（ｎ） ＝ ｆ ｎ（ｎ） ＋ １， ｎ ∈ ω 是递归的， ｈ（ｋ） ＝ ｆ ｋ（ｋ） ＝ ｆ ｋ（ｋ） ＋ １，矛盾，所以，不存在一 元递归函数的能行可枚举［３］ 。 ３）以下定理是“对角线证明方法”，证明错误： 设 Ｄ（ｘ，ｙ） 是一元原始递归函数的通用函数， 则 Ｄ（ｘ，ｙ） 不是二元原始递归函数。 证明 Ｄ（ｘ，ｙ） 是一元原始递归函数的通用函 数，所以，全体一元原始递归函数都包含在函数序列 Ｄ（ｘ，０） ， Ｄ（ｘ，１） ， Ｄ（ｘ，２） ， Ｄ（ｘ，３） ，…中，可以 做以下无穷列表： 表 ６ 跨正反集上的真值表 Ｔａｂｌｅ ６ Ｔｈｅ ｔｒｕｔｈ ｖａｌｕｅ ｔａｂｌｅ ｆｏｒ ｃｒｏｓｓｉｎｇ ｔｈｅ ｐｏｓｉｔｉｖｅ ａｎｄ ｉｎｖｅｒｓｅ ｓｅｔｓ ｘ ｙ ０ １ ２ ３ … ０ Ｄ（０，０） Ｄ（０，１） Ｄ（０，２） Ｄ（０，３） … １ Ｄ（１，０） Ｄ（１，１） Ｄ（１，２） Ｄ（１，３） … ２ Ｄ（２，０） Ｄ（２，１） Ｄ（２，２） Ｄ（２，３） … ３ Ｄ（３，０） Ｄ（３，１） Ｄ（３，２） Ｄ（３，３） … … … … … … … 定义一个一元函数 ｇ（ｘ） ＝ Ｄ（ｘ，ｘ） ＋ １，如果 Ｄ（ｘ，ｙ） 是二元原始递归函数， ｇ（ｘ） 也是一元原始 递归函数，设 ｇ（ｘ） ＝ Ｄ（ｘ，ｎ） ， ｎ ∈ ω 是递归的，令 ｘ ＝ ｎ，ｇ（ｎ） ＝ Ｄ（ｎ，ｎ） ｇ（ｎ） ＝ Ｄ（ｎ，ｎ） ＝ Ｄ（ｎ，ｎ） ＋ １，矛盾，所以， Ｄ（ｘ，ｙ） 不是二元原始递归函数［６］ 。 推论 ２３ ω 上存在非递归函数的证明错误。 推论 ２４ 不存在一元递归函数的能行可枚举， 证明错误。 ６．２ Ｔｕｒｉｎｇ 机“停机问题”证明错误 Ｔｕｒｉｎｇ 证明， Ｔｕｒｉｎｇ 机“停机问题”是不可判定 的，即： 不 存 在 算 法 对 以 下 问 题 类 提 供 答 案， ｛ Ｔｕｒｉｎｇ 机 Ｔｍ 在输入 ｎ 后是否会停机 ｜ ｍ，ｎ ∈ Ｎ｝。 回顾一下图灵机“停机问题”的证明过程。 按照哥德尔编码，给 Ｔｕｒｉｎｇ 机指定一个编码， 按编码的大小，把所有的 Ｔｕｒｉｎｇ 机一个不漏的枚举 如下： Ｔ０ ，Ｔ１ ，Ｔ２ ，…，Ｔｍ ，… 。 定义一个一元函数： ｆ（ｎ） ＝ ０， Ｔｎ 输入 ｎ 后停机； {１， Ｔｎ 输入 ｎ 后不停机。 Ｔｕｒｉｎｇ 机 Ｔｍ 在输入 ｎ 后是否会停机的各种情 况排列如表 ７（表中的所有情况与二进制表示的实 数等价）。 表 ７ 对角线方法“Ｔｕｒｉｎｇ 停机问题”定义 Ｔａｂｌｅ ７ Ｔｈｅ “Ｔｕｒｉｎｇ ｈａｌｔｉｎｇ ｐｒｏｂｌｅｍ” ｄｅｆｉｎｅ ｔａｂｌｅ ｏｆ ｄｉ⁃ ａｇｏｎａｌ ｍｅｔｈｏ Ｔ０ Ｔ１ Ｔ２ Ｔ３ Ｔ４ … ｆ（０） ０ １ ０ ０ １ … ｆ（１） ０ １ ０ １ １ … ｆ（２） ０ １ ０ １ ０ … ｆ（３） ０ ０ ０ １ ０ … ｆ（４） １ ０ ０ １ ０ … … … … … … … … 假设 ｆ（ｎ） 是 Ｔｕｒｉｎｇ 可计算函数，那么存在某个 Ｔｕｒｉｎｇ 机 Ｔ 来计算 ｆ（ｎ） 的值，即 对任意 ｎ ∈ ω ， ｆ（ｎ） ＝ ０⇔ Ｔ 输入 ｎ 后输出 ０； ｆ（ｎ） ＝ １⇔ Ｔ 输入 ｎ 后输出 １。 把上表对角线上的元素挑出来。 就可以得到一 个序列： ０，１，０，１，０，… ，而根据这个序列完全可以 构造这样一个反序列： １，０，１，０，１，… 利用反序列， 构造一个新的 Ｔｕｒｉｎｇ 机 Ｔｇ 。 Ｔ 输入 ｎ 后输出 １⇔ Ｔｇ 输入 ｎ 后会停机。 Ｔｇ 是一个新的图灵机， Ｔｇ 必然出现在 Ｔ０ ，Ｔ１ ， Ｔ２ ，…，Ｔｍ ，… 中，设 Ｔｇ ＝ Ｔｋ 。 Ｔｋ 输入 ｋ 后会停机 ⇔ Ｔ 输入 ｋ 后输出 １⇔ 第 ５ 期 张金成，等：逻辑及数学演算中的不动项与不可判定命题（Ⅱ） ·６２９·