·630· 智能系统学报 第9卷 f八k)=1台T输入k后不停机。 推论29 Turing机T.矛盾来源于U外。 得出矛盾，新以f(n)是Turing不可计算函数。 推论30 Turing机T,不能作为任何“U内演 即：不存在算法对问题类{Turing机T在输入 算的推理依据”。 n后是否会停机1m,n∈N}提供答案o]。 根据以上推论，Turing机T,的不可判定与U内 以上证明，与“自然数幂集合不可数”，“实数不 项是否可以判定无关，T不能作为任何“U内演算 可数”的证明是一样的。通过分析，可以知道，构造 的推理依据”，即：T矛盾使用“反证法”不成立。 的矛盾是不动项矛盾。 故Turing机“停机问题”不可判定证明是错误的。 定理24设U={T,T1,T2,…,Tm,…},Turing 6.3一批错误结论及其根源 机T.是不动项。 我们知道经典逻辑定理只能在一个封闭的域上 证明P是定义在U上的一个性质，命题P是 使用，由于U外不动项矛盾的存在，“反证法”不能 关于正集+α、反集-α的一个二项划分， 无限制使用。 P(Tn)台T。在输人n后会停机： 如果命题P,P(x)是系统L“或K的一个推 P(T.)台T.在输人n后不会停机。 论，即L上P,上P(x),这个推理只有在一个 即+a={TnIP(Tn),Ta∈U), 已经定义的集合U={x1,x2,x3,…,x,…}上成立， -a={TnIP(Tn),Tn∈U}; 我们不能忘记它成立的前提x:∈U。 建立映射关系： 任何一个推理都存在一个已经定义集合： X∈+C←→y∈-C U={x1,x2,x3,…,xn,…} y=f(x) 在这个集合中使用自指代运算产生悖论是必然的， P(x)P(y) 即M上P(T)P(T)。 当xp满足x=f(x),P(xp)P(xp),xp是 这个悖论不足以否定这个集合内的任何前提， 不动项。 即不能得到上M。 以上构造的T满足P(T)∽P(T),即：T 这个悖论只能得到“U上的演算不是封闭的”， 是不动项，证毕。 即上TU。 还可以从“广义U外不动项定理”考虑： 之所以会产生如此“反证法”错误，因为“项T” 构造项T满足以下关系，x∈+αP(T.), 原来在U中并没有出现，是在自指代运算中不知不 x∈-aP(T.); 觉就跑出了U的范围，特别是一些高度抽象的项 根据“广义U外不动项定理”，Turing机T.是不 (命题项、函数项)，从表面上不能鉴别它是否在U 动项。 中，只能通过逻辑推理来判断，当“项T”在演算中 也可以从以下构造的二元项考虑： 跑出了U的范围，经典逻辑的定理“反证法”就不成 U={(To,1),(T,1),(T2,1),…,(Tm,1),… 立了，“悖论证明方法、对角线证明方法”就是这种 (T0,2),(T1,2),(T2,2),…,(Tm,2), 错误。 从经典逻辑封闭性要求看，如果写成： (To,n),(T,n),(T2,n),…,(Tm,n),… “T∈U,M上P(T)nP(T)”; …} 从而得到：“M上(T∈U)”,“反证法”依然 U是所有Turing机对所有输入后的状态，这些 正确。 状态可分为正反两个集合。 但是，由于“项T”事先并不存在，很难开始就 P(Tn,n)台T.在输人n后会停机 在前提中加入这个条件。 P(Tn,n)台Tn在输入n后不会停机。 由于经典逻辑的缺陷，Russell、Cantor、Godel, P(T,k)P(T,k),（T,k)是不动项。 Turing实际上发现了U外不一致性，发现了U外矛 根据U外不动项的一般性质，以下推论成立： 盾不动项，即构造了一个悖论，但是他们没有认识 推论25 Turing机不动颅T一定在U外，T,年U。 到，他们误以为悖论可以用于“反证法”，证明了“实 推论26 Turing机T,是未定义项。 数不可数”，“不完全定理”，“停机问题不可判定”。 推论27 Turing机T,是不可判定命题。 “不动项定理”表明，形形色色排除悖论的努力 推论28 Turing机T.的不可判定与U内项是 都是徒劳的，只要有“自指代”，就可能产生悖论。 否可以判定无关。 命题逻辑系统L,谓词演算系统K,只要使用“自指ｆ（ｋ） ＝１⇔ Ｔｋ 输入 ｋ 后不停机。 得出矛盾，所以 ｆ（ｎ） 是 Ｔｕｒｉｎｇ 不可计算函数。 即：不存在算法对问题类｛ Ｔｕｒｉｎｇ 机 Ｔｍ 在输入 ｎ 后是否会停机｜ ｍ，ｎ ∈ Ｎ ｝提供答案［１０］ 。 以上证明，与“自然数幂集合不可数”，“实数不 可数”的证明是一样的。 通过分析，可以知道，构造 的矛盾是不动项矛盾。 定理 ２４ 设 Ｕ ＝ ｛Ｔ０ ，Ｔ１ ，Ｔ２ ，…，Ｔｍ ，…｝ ，Ｔｕｒｉｎｇ 机 Ｔｇ 是不动项。 证明 Ｐ 是定义在 Ｕ 上的一个性质，命题 Ｐ 是 关于正集 ＋ α 、反集 － α 的一个二项划分， Ｐ（Ｔｎ ） ⇔ Ｔｎ 在 输 入 ｎ 后 会 停 机； ¬ Ｐ（Ｔｎ ） ⇔ Ｔｎ 在输入 ｎ 后不会停机。 即 ＋ α ＝ Ｔｎ { ｜ Ｐ（Ｔｎ ），Ｔｎ ∈ Ｕ} ， － α ＝ Ｔｎ { ｜ ¬ Ｐ（Ｔｎ ），Ｔｎ ∈ Ｕ} ； 建立映射关系： ｘ ∈＋ α↔ｙ ∈－ α ｙ ＝ ｆ（ｘ） Ｐ（ｘ）↔¬ Ｐ（ｙ） 当 ｘＰ 满足 ｘ ＝ ｆ（ｘ） ， Ｐ（ｘＰ ）↔¬ Ｐ（ｘＰ ） ， ｘＰ 是 不动项。 以上构造的 Ｔｇ 满足 Ｐ（Ｔｇ ）↔¬ Ｐ（Ｔｇ ） ，即： Ｔｇ 是不动项，证毕。 还可以从“广义 Ｕ 外不动项定理”考虑： 构造项 Ｔｇ 满足以下关系， ｘ ∈＋ α↔¬ Ｐ（Ｔｇ ） ， ｘ ∈－ α↔Ｐ（Ｔｇ ） ； 根据“广义 Ｕ 外不动项定理”，Ｔｕｒｉｎｇ 机 Ｔｇ 是不 动项。 也可以从以下构造的二元项考虑： Ｕ ＝ ｛（Ｔ０ ，１），（Ｔ１ ，１），（Ｔ２ ，１），…，（Ｔｍ ，１），… （Ｔ０ ，２），（Ｔ１ ，２），（Ｔ２ ，２），…，（Ｔｍ ，２），… … （Ｔ０ ，ｎ），（Ｔ１ ，ｎ），（Ｔ２ ，ｎ），…，（Ｔｍ ，ｎ），… …｝ Ｕ 是所有 Ｔｕｒｉｎｇ 机对所有输入后的状态，这些 状态可分为正反两个集合。 Ｐ（Ｔｎ ，ｎ） ⇔ Ｔｎ 在输入 ｎ 后会停机， ¬ Ｐ（Ｔｎ ，ｎ） ⇔ Ｔｎ 在输入 ｎ 后不会停机。 Ｐ（Ｔｇ ，ｋ）↔¬ Ｐ（Ｔｇ ，ｋ） ， （Ｔｇ ，ｋ） 是不动项。 根据 Ｕ 外不动项的一般性质，以下推论成立： 推论 ２５ Ｔｕｒｉｎｇ 机不动项Ｔｇ 一定在Ｕ外，Ｔｇ ∉Ｕ。 推论 ２６ Ｔｕｒｉｎｇ 机 Ｔｇ 是未定义项。 推论 ２７ Ｔｕｒｉｎｇ 机 Ｔｇ 是不可判定命题。 推论 ２８ Ｔｕｒｉｎｇ 机 Ｔｇ 的不可判定与 Ｕ 内项是 否可以判定无关。 推论 ２９ Ｔｕｒｉｎｇ 机 Ｔｇ 矛盾来源于 Ｕ 外。 推论 ３０ Ｔｕｒｉｎｇ 机 Ｔｇ 不能作为任何“ Ｕ 内演 算的推理依据”。 根据以上推论， Ｔｕｒｉｎｇ 机 Ｔｇ 的不可判定与 Ｕ 内 项是否可以判定无关， Ｔｇ 不能作为任何“ Ｕ 内演算 的推理依据”，即： Ｔｇ 矛盾使用“反证法” 不成立。 故 Ｔｕｒｉｎｇ 机“停机问题”不可判定证明是错误的。 ６．３ 一批错误结论及其根源 我们知道经典逻辑定理只能在一个封闭的域上 使用，由于 Ｕ 外不动项矛盾的存在，“反证法”不能 无限制使用。 如果命题 Ｐ ， Ｐ（ｘｉ） 是系统 Ｌ α 或 Ｋ α 的一个推 论，即 Ｌ α ├ Ｐ ， Ｋ α ├ Ｐ（ｘｉ） ，这个推理只有在一个 已经定义的集合 Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 上成立， 我们不能忘记它成立的前提 ｘｉ ∈ Ｕ 。 任何一个推理都存在一个已经定义集合： Ｕ ＝ ｘ１ ，ｘ２ ，ｘ３ ，…，ｘ { ｎ ，…} 在这个集合中使用自指代运算产生悖论是必然的， 即 Ｍ ├ Ｐ（Ｔ）↔¬ Ｐ（Ｔ） 。 这个悖论不足以否定这个集合内的任何前提， 即不能得到├ ¬ Ｍ 。 这个悖论只能得到“ Ｕ 上的演算不是封闭的”， 即├ Ｔ ∉ Ｕ 。 之所以会产生如此“反证法”错误，因为“项 Ｔ ” 原来在 Ｕ 中并没有出现，是在自指代运算中不知不 觉就跑出了 Ｕ 的范围，特别是一些高度抽象的项 （命题项、函数项），从表面上不能鉴别它是否在 Ｕ 中，只能通过逻辑推理来判断，当“项 Ｔ ” 在演算中 跑出了 Ｕ 的范围，经典逻辑的定理“反证法”就不成 立了，“悖论证明方法、对角线证明方法” 就是这种 错误。 从经典逻辑封闭性要求看，如果写成： “ Ｔ ∈ Ｕ ， Ｍ ├ Ｐ（Ｔ）↔¬ Ｐ（Ｔ） ”； 从而得到：“ Ｍ ├ ¬ （Ｔ ∈ Ｕ） ”，“反证法”依然 正确。 但是，由于“项 Ｔ ” 事先并不存在，很难开始就 在前提中加入这个条件。 由于经典逻辑的缺陷，Ｒｕｓｓｅｌｌ、Ｃａｎｔｏｒ、Ｇöｄｅｌ， Ｔｕｒｉｎｇ 实际上发现了 Ｕ 外不一致性，发现了 Ｕ 外矛 盾不动项，即构造了一个悖论，但是他们没有认识 到，他们误以为悖论可以用于“反证法”，证明了“实 数不可数”，“不完全定理”，“停机问题不可判定”。 “不动项定理”表明，形形色色排除悖论的努力 都是徒劳的，只要有“自指代”，就可能产生悖论。 命题逻辑系统 Ｌ，谓词演算系统 Ｋ，只要使用“自指 ·６３０· 智 能 系 统 学 报 第 ９ 卷