动机
关于程序的许多问题问的是它接受哪些输入,而不是它的代码如何书写。它是否接受某个字符串?它的语言是否有限?它的语言是否正则?这些问题看上去各不相同,但同一个归约即可证明:所识别语言的每一个非平凡性质都是不可判定的。
关键在于构造这样一台机器:根据某个特定计算是否停机,它要么识别一个选定的参考语言,要么什么也不识别。新机器不需要知道究竟属于哪种情形,它只需在收到输入时模拟该计算。一个假设存在的性质判定器可以区分这两种情形,从而判定停机问题。
定义
定义 5.3.1
(可识别语言)
固定一个至少含两个符号的有限字母表 ,指定其中两个不同的符号分别记作 和 ,并固定一种对确定型图灵机(Turing machine)的有效编码,机器的输入为 上的字。对机器 ,令 为 最终接受的字的集合。对其他字,机器可以拒绝,也可以永不停机。若一个语言等于某台这类机器的 ,则称该语言是可识别的。
定义 5.3.2
(语言的性质与非平凡性)
性质 是 上若干可识别语言构成的一个集合。若存在某个可识别语言属于它,同时又存在某个可识别语言不属于它,则称该性质是非平凡的。相应的判定问题是:给定编码后的机器 ,问 是否成立。我们假设采用标准编码,其句法合法性检查是可判定的,格式错误的编码可以直接拒绝。通常的有效机器编码的具体选择不会改变归约论证。
定理
定理 5.3.3
(莱斯定理)
可识别语言的每一个非平凡性质都是不可判定的:不存在这样的判定器,能对每一台机器 正确地判定 是否具有该性质。
定理 5.3.4
(归约中使用的停机问题)
不存在这样的判定器:给定编码后的确定型图灵机 和输入 ,判定 在 上是否停机。
第二个定理是可计算性配套章节中已经确立的标准停机不可判定性结果。“停机”既包括接受,也包括拒绝。莱斯(Rice)定理中的性质只涉及所接受的语言:即使两台机器的运行时间和拒绝行为不同,只要它们接受同一个集合,就必须得到相同的答案。
证明
空语言不属于该性质时的归约
证明
(停机问题归约到非平凡性质)
先假设 。由非平凡性,存在可识别语言 ,并固定一台识别 的机器 。给定一个停机问题的实例 ,有效地构造一台机器 ,它在任意输入 上按如下方式运行:
- 在固定的字 上模拟 。
- 若该模拟停机,则在 上运行 ,并且恰在 接受时接受。
若 在 上永不停机,则对每个 ,第一步都会永远运行下去,因此 。若 确实停机,则有限步的第一步之后是对 的模拟,因此 。无论 接受还是拒绝 ,这一点都成立;决定分支的只是是否停机。
映射 是可计算的:机器的描述可以包含 和 的有限编码,以及两次模拟的指令。该构造并不试图判定第一次模拟是否会停机。假设存在 的判定器,那么它对 回答“是”,当且仅当 在 上停机,这与停机问题的不可判定性矛盾。
证明透视
莱斯定理的假设在何处被用到
非平凡性被用到两次:它提供了固定的可识别语言 ,其机器 被嵌入 ;在其余情形中,它又保证互补性质仍是非平凡的。假设 使二分成立:构造只可能产生 或 ,其中恰有一个属于 ,因此判定器对 的回答就报告了 是否停机。语义不变性在把判定器应用于 时被用到:回答只依赖于 ,而与代码如何书写无关。不显然的一步是: 只是等待 ,而不是检验 是否停机,所以映射 是可计算的,尽管要辨认它所产生的语言是不可能的。论证以反证法收尾: 的判定器与这个可计算映射复合,就会判定停机问题。
其余情形
证明
(取互补性质处理其余情形)
若 ,考虑可识别语言类内的互补性质 :它恰好包含那些不属于 的可识别语言。它仍然是非平凡的,并且不含 。由前面的论证,它的判定问题是不可判定的。如果 是可判定的,把“是”与“否”的回答互换,就能判定 ,矛盾。证明完毕。
常见错误
(性质的补集不是语言的补集)
这里的补集是语言性质的补集,而不是每个语言自身的补集。我们并不是断言每个可识别语言的补集都是可识别的。一个假设的判定器对每个机器编码返回一个布尔值,因此互换该答案就判定了互补性质,即使语言补运算本身可能很困难。
例题详解
例题 5.3.5
(“包含 0”这一性质的构造)
设 为含有字 的可识别语言所成的性质。于是 ,语言 属于 ,而 可以取为恰好接受输入 的机器。对实例 ,机器 先在 上模拟 ,然后在自己的输入上运行 。若 在 上停机(即使是以拒绝方式停机),模拟就会结束,所以 。若 在 上永远运行,则 永远到不了 ,。因此“包含 ”的判定器将能判定停机问题。拒绝的情形是边界情形:决定分支的是停机,而不是接受。
例题 5.3.6
(有限性:其余情形的例子)
设 为有限的可识别语言所成的性质,所以 ,上面的构造不能直接套用。互补性质 由无限的可识别语言组成:,而 。取 ,并令 接受每个字。于是若 在 上停机,;否则 。所以 无限,当且仅当 在 上停机。有限性的判定器把答案互换之后,就能判定停机问题。
例题 5.3.7
(空性)
性质 是非平凡的:空语言是可识别的,而 是另一个不同的可识别语言。莱斯定理表明,判定 是否成立是不可能的。它的互补性质,即非空性,同样是不可判定的,尽管非空性是可识别的:可以对所有输入交错模拟,并在某次运行接受时接受。
例题 5.3.8
(有限性)
“ 是有限的”是一个非平凡的语义性质。空语言是有限且可识别的,而 是无限的,并且由于字母表非空而可识别。因此,没有判定器能够仅从任意识别器的代码判定其语言是否有限。一台描述中只含有限多个状态的机器仍可能接受无限语言;代码的大小与语言的大小是不同的概念。
例题 5.3.9
(所识别语言的正则性)
空语言是正则且可识别的。语言 是可识别的,但由正则语言一章中的泵引理论证可知它不是正则的。因此,正则性是可识别语言的一个非平凡性质,对任意图灵机描述而言是不可判定的。这与对已承诺输入为 DFA 的情形所存在的与正则性相关的高效算法并不矛盾。
例题 5.3.10
(句法问题则不同)
“编码的机器是否恰好有三个状态?”可以通过解析一个合法的有限描述并数出状态个数来回答。它不是语言的语义性质:接受同一语言的两台机器,其不可达或冗余状态的数目可以不同。莱斯定理不适用于这个句法问题。
常见错误
定理说了什么,没说什么
输入类很重要。莱斯定理针对的是任意编码的识别器,包括可能永远运行的机器。如果输入限制在带有更强承诺的表示上,某个具体性质可能是可判定的。例如,DFA 的空性可以通过图的可达性来判定,尽管任意图灵可识别语言的空性是不可判定的。
性质必须只依赖于 。某台机器在固定输入上是否于固定步数内停机,可以通过有界模拟来判定,但接受同一语言的两台机器在这一点上可以不同。它不是莱斯定理的反例,因为它并不是只关于所接受语言的性质。
常见错误
(不可判定不等于不可识别)
该定理证明的是不可判定性,并不自动意味着两种回答都不可识别。语言非空的机器编码集合是可识别的:枚举输入字,交错执行机器计算的有限前缀,并在某次计算接受时立即接受。然而它仍是不可判定的。要确定另一个性质的“是”一侧或“否”一侧是否可识别,需要单独的论证。
反例模式
并非关于机器的每个非平凡问题都不可判定
对莱斯定理一个诱人的过度解读是:关于编码机器的每个非平凡是非问题都不可判定。考虑“机器是否恰好有三个状态?”它是非平凡的,因为有些机器恰有三个状态而有些不是;但它是可判定的:解析有限描述并数出状态即可。具体地,设 恰有三个状态,且没有任何转移进入接受状态,所以 ;设 是在 上多加一个不可达状态所得的机器,所以 也成立。对 的答案是“是”,对 是“否”,尽管它们接受同一个语言。因此这个问题并不只是所接受语言的性质,而这恰好是莱斯定理所需的假设。
注意归约的方向
常见错误
(把归约方向弄反)
归约从已知不可判定的停机问题的任意实例出发,把它转化为性质问题的一个实例。若性质判定器存在,把构造出的实例交给它,就能解决原来的停机问题。这个方向至关重要:若把性质问题归约到停机问题,只能说明假设的停机预言机如何帮助解决性质问题,并不能说明性质判定器能解决停机问题。
该构造还使用了固定的参考识别器,而不是固定的参考输入。当被模拟的停机实例停止后,新机器必须对其所得到的任意输入 重现 的行为。对每个这样的 ,最初的模拟所需步数是有限的,并且与 在 上最终是接受、拒绝还是永不停机无关。因此,被接受的输入集合恰好是 ,而不仅仅是 的子集。
当停机模拟不停止时,新机器在每个输入上都永远运行。对识别器而言,这种行为是允许的。若证明要求构造出的机器在每个输入上都停机,则需要额外的论证,不能简单地沿用这种等待式构造。本定理所涉及的是不受限制的图灵机识别器,这一区别说明了为何输入类的假设是实质性的。
对于非空性,交错模拟可以明确写出。把所有有限输入字枚举为 。在第 阶段,对 各自运行该机器 步,格局可以重新开始,也可以保留,视方便而定。若任何一次运行接受,就接受该机器编码。对任何固定的输入及其模拟的任何固定有限步数,最终都会被到达。若没有任何输入被接受,该过程就永远运行,这对识别而言是允许的,但对判定过程则不允许。
理解非平凡性
非平凡性是相对于固定字母表上的可识别语言而言的。对每个可识别语言都成立的性质,总回答“是”即可判定;对任何可识别语言都不成立的性质,总回答“否”即可判定。莱斯定理排除了这两种平凡情形。证明中使用的见证语言不必难以识别;、 和 这类简单语言往往就足够。
对于正则性这类性质,其中一个见证必须是可识别但非正则的语言。仅仅举出任意一个非正则集合而不说明它可识别,是不够的。语言 是可判定的:检查块的顺序并比较两个计数即可,所以它是合格的见证。它的非正则性则是另一个事实,由泵引理证明。
在归约中,一旦性质确定,参考机器 也就固定了。构造允许包含这台有限的机器描述。构造并不把性质的任意描述作为输入,也不需要从这样的描述计算出见证。这一区别使得从 到 的有效变换保持精确。
总结
语义性质只依赖于所接受的语言。若它是非平凡的,则可以构造一个识别器,根据某个停机计算的结果,在空语言与一个固定见证语言之间切换。因此,该性质的判定器将能够判定停机问题。平凡性质、机器的句法特征以及受限的表示类,都不在本定理的假设范围之内。
练习
快速检查
(解释为什么“包含字 ”这一性质对任意图灵机识别器是非平凡且不可判定的。)
找出两个可识别语言,一个含有该字,一个不含。
解答 · 答案
空语言不含 ,而 含有 ;两者都是可识别的。 是否属于语言只依赖于所接受的语言,所以由莱斯定理,该性质是不可判定的。
快速检查
(性质“所接受的语言等于 ”是否属于莱斯定理的适用范围?请给出非平凡性的见证。)
检查两项假设:非平凡性,以及只依赖于语言。
解答 · 答案
是。 是可识别的且满足该性质,而 是可识别的且不满足该性质。是否等于 只依赖于语言,所以该性质是非平凡的语义性质。
快速检查
(解释为什么“机器在 100 步内接受 ”不是所识别语言的语义性质。)
找两台语言相同但运行时间不同的机器。
解答 · 答案
一台机器可以立即接受 ,而另一台机器在接受它之前先执行 101 步空操作;除此之外它们可以识别同一个语言。尽管所接受的语言相同,有限时间内的答案却不同。有界模拟本身是可判定的。
快速检查
(对于非空性这一性质,描述其“是”实例的一个识别器,并解释为什么莱斯定理仍然适用。)
哪种程序可以同时搜索所有输入?
解答 · 答案
枚举所有输入字,并交错模拟该编码机器在这些字上的运行,每次运行的步数递增且有限。若任一模拟接受,则接受。若语言非空,最终会找到某次接受运行;若语言为空,该过程可能永远运行。该性质是非平凡的语义性质,所以尽管其“是”实例是可识别的,它仍是不可判定的。