动机
有限自动机、下推自动机和有界带机器各自对记忆施加了限制,每种限制都排除了一些语言。图灵(Turing)机取消了这个限制:它有一条无界的带,可以在上面读写。问题也随之改变。我们不再问哪些语言适合某个记忆界,而是问哪些语言可以由任何机械过程判定,并发现存在明确的、可证明的极限,这些极限并非来自资源不足。
我们精确陈述机器模型,证明关于识别与判定的核心定理,并把前面各章的语言类放进同一条链中。完整的转移表只对一台小的示例机器给出;通用机器只在算法层面描述,其中常规的子程序假定可以实现。我们不作超出经典可计算性的任何断言。
定义
定义 5.1.1
(图灵机与格局)
确定型图灵机是 ,其中 为有限状态集, 为输入字母表,带字母表 ,空白符 ,转移函数为 。带向右无界,起初是输入字后接空白;读写头从第一个单元出发。从第一个单元左移时读写头留在原处。格局是串 ,其中 ,,意为带上是 后接空白,状态为 ,读写头扫描 的第一个符号( 为空时扫描空白)。关系 表示 由一步移动得到。
若从 出发到达处于 的格局,则机器接受 ;若到达处于 的格局,则拒绝 ;否则循环,即永远运行。以 记被接受的字的集合。
定义 5.1.2
(识别器、判定器、可判定、可识别)
若 对某台机器 成立,则称语言 图灵可识别;这时 只需接受 中的字,对其他字可以循环。若 对某台在每个输入上都停机(接受或拒绝)的机器 成立,则称 可判定;这样的 称为判定器。
定义 5.1.3
(编码与映射归约)
固定一种可计算的单射方式,把机器 与字 写成 上的串 与 ,并使得判断一个串是否为合法编码是可判定的。从 到 的映射归约记作 ,是一个全可计算函数 ,使对所有 有 。定义 ,,(自接受),以及 。
定理
定理 5.1.4
(通用模拟)
存在图灵机 ,在输入 上,当且仅当 接受 时接受,当且仅当 拒绝 时拒绝,当且仅当 在 上循环时循环。因此 与 是图灵可识别的。
定理 5.1.5
(可判定即可识别且补集可识别)
语言 可判定,当且仅当 与 都是图灵可识别的。
定理 5.1.6
(自接受与停机问题不可判定)
不可判定。因此 、 与 不可判定,且 的补集不是图灵可识别的。
定理 5.1.7
(归约的方向)
设 给出 。若 可判定则 可判定;若 可识别则 可识别。等价地,若 不可判定,则 不可判定。关系 是传递的。
定理 5.1.8
(莱斯(Rice)定理)
设 是 上图灵可识别语言的集合,使得某个可识别语言属于 ,且某个可识别语言不属于 。则 不可判定。
定理 5.1.9
(语言类的一条链)
在至少含三个符号的固定字母表上,,其中 CSL 是由非收缩文法生成的类,DEC 是可判定语言类,REC 是图灵可识别语言类。每个包含都是真包含。包含 使用配套范式一章所证明的乔姆斯基(Chomsky)范式定理。
证明思路
证明
(逐步模拟构成通用机器)
机器 在带上保存 当前格局的编码,旁边是编码后的转移表 。一个模拟步骤在格局中找到状态与被扫描的符号,在 中查找匹配的 项,并改写格局。这些子程序(搜索、串比较、复制、平移)都是常规的,我们不给出其状态。对 归纳可知,模拟 步后带上的格局编码了 在 上的 。若 处于 ,则 接受;若处于 ,则拒绝;若 永不停机,则 永远运行。对 ,先复制 得到 ,再运行 。
证明
(交错执行判定补集可识别的语言)
若 可判定,则 的判定器就是识别器,交换其接受与拒绝状态得到补集的判定器,因而也是识别器。反之,设 识别 , 识别其补集。对输入 ,在不同的带道上交替运行 与 :先走 一步,再走 一步,如此继续。这种交替运行的技巧称为交错执行(dovetailing)。 与 恰有一个为真,所以恰有一台机器接受 ,并且在有限步之后接受;另一台永不接受。若 接受,则接受;若 接受,则拒绝。这在每个输入上停机并判定 。若改为先后运行两台机器,则会失败,因为第一台可能循环。
证明
(对自接受问题的判定器作对角化)
假设判定器 判定 。构造 :对输入 ,若 不是机器的合法编码就拒绝;否则在 上运行 ,当且仅当 拒绝时接受。 在每个输入上停机。令 。则 接受 当且仅当 拒绝 ,当且仅当 ,当且仅当 不接受 ,矛盾。所以不存在判定器。这同样是一个对角线论证:只要 正确, 的语言在输入 处就与每台机器 的语言不同。
证明透视
对角线论证究竟用到了什么
需要三个要素,每个都能在正文中找到。第一,有效的编码:每台机器 都是一个串,所以可以把 自己的描述作为 的输入。第二,假设的判定器 必须是一台机器,这样由它构造的 才是一台在 上行为有定义的机器。第三, 翻转 的回答并在每个输入上停机。矛盾只出现在唯一的输入 上。这个论证并不说明没有机器能识别 ——通用机器就识别它。
证明
(不可判定性沿归约传递)
下列每个归约还把非法源编码送到目标集合外的一个固定对象,因此预处理在全部字符串上都有定义。 用 归约 ,并把非合法编码的串送到 之外的某个固定串。于是由归约方向定理, 不可判定。其次 :把 映到 ,其中 在输入 上模拟 在 上的运行,若 接受则接受,若 拒绝则进入无限循环。于是 在 上停机当且仅当 接受 。最后 :把 映到 ,其中 忽略其输入,先把 写到带上再运行 ; 在空输入上停机当且仅当 在 上停机。 的补集不可能是可识别的,因为 被通用机器识别,若二者都可识别,则由补集定理 将是可判定的。
证明
(归约把可判定性反向传递)
设 把 归约到 。若 有判定器 ,则对输入 计算 并在其上运行 :这判定了 ,因为 且 是全函数。可识别情形相同,使用 的识别器。取逆否命题即得不可判定性的陈述。关于传递性,若 把 归约到 , 把 归约到 ,则 是全可计算的,并把 归约到 。
证明
(停机问题归约到每个非平凡性质)
对非法源编码,输出一个其语言不满足当前性质的固定机器。 先说明 不可判定(上面已证)。先设 。选取机器 使 。定义 ,其中 在输入 上先模拟 在 上的运行;若 接受 ,则 在 上运行 ,当且仅当 接受时接受;若 不接受 (拒绝或循环),则 永不接受。于是当 接受 时 ,否则 。所以 把 归约到语言 ,因而 不可判定。若 ,对“不在 中的可识别语言”所成的类 应用该论证,它是非平凡的且不含 ;合法编码的集合是可判定的,而 是 在其中的补集,所以 也不可判定。
证明透视
为何来源问题可以是接受问题
包装机 由非平凡性提供的机器 ,以及 和 构成。它的两种结果 与 ,恰好按 是否接受 来区分。 拒绝和 不停机,都使 什么也不接受,这没有问题,因为 把两者同样对待。正是假设 ,两种结果才有不同的答案;取补集一步只是把这个假设恢复。映射 可计算,是因为 只是被写出来,从不被运行。
证明
(包含链及各包含为何是真包含)
:DFA 给出一个文法,每个状态对应一个变元,规则为 ,以及对接受状态 的 。:在范式假设下, 的范式文法的规则 与 是非收缩的;若 ,则加入新的起始变元 与规则 。 即上下文有关一章中成员问题的可判定性。 是显然的。 是平凡的。
关于真包含: 是上下文无关的但不是正则的。 是上下文有关的但不是上下文无关的。对 ,使用相同固定字母表 ,其中含前三个反例所需的不同符号。变元名取自一个固定的可数列表的、 上的非收缩文法是有限对象,所以可以被可计算地枚举为 ; 上的每个上下文有关语言在变元重命名意义下都是某个 。枚举 为 ,令 。 可判定:给定 ,找到 使 ,构造 ,并用长度引理判定成员问题。但对每个 有 ,因为 恰属于二者之一。对 ,见证是 。对 ,机器是有限串,因而只有可数多个,而 的子集由康托尔(Cantor)论证是不可数多的。
反例模式
反方向的归约什么也证明不了
断言(错误):要证明 不可判定,只需把 归约到某个可判定语言,或把某个可判定语言归约到 。取可判定语言 。把每个输入都映到某个固定的不停机的对的常值函数,就是 到 的映射归约,但这并不能告诉我们 是否可判定。同样,把 归约到一个可判定语言只会表明 可判定,而这是假的。修正:要证明目标语言 不可判定,应把已知不可判定的语言 归约到 ,并且可计算映射 必须在两个方向上都满足 。
概念视角算法
交错执行作为搜索的调度
识别器是这样一种搜索:答案为“是”时在有限步内成功,答案为“否”时可能永远不结束。判定器把两个这样的搜索结合起来,一个搜索成员资格,一个搜索非成员资格,并交替运行,使得无论哪一个成功都会被注意到。交错执行不是一种优化;它是避免卡在永远不会结束的那个搜索中的唯一办法。
例题
例题 5.1.10
( 时 的判定器)
未列出的状态与符号组合均进入拒绝状态并保留当前符号;未说明写入的移动也保留符号,因此转移函数全定义。
设机器的带符号为 ,转移如下:在 读到 时,写 ,右移,进入 ;在 读到 时,右移进入 ;在 读到其他符号时拒绝。在 ,向右越过 与 ;读到 时,写 ,左移,进入 ;读到 时拒绝。在 ,向左越过 与 ;读到 时右移并进入 。在 向右越过 ,读到 时接受,读到 或 时拒绝。输入 上: 接受。每一遍 配对一个 与一个 ;机器恰在所有 都用完时到达 ,然后仅当不再剩有 时接受。
例题 5.1.11
(玩具表上的对角线模式)
设四台机器和四个输入给出接受表(1 表示接受,0 表示不接受),各行为 、、、。对角线是 ;翻转得 。翻转后的行在第 列与第 行不同,对每个 都成立,所以它不出现在表中的任何地方。真正的证明把这一点用到所有机器对所有机器编码的无限表上,翻转后的对角线就是 的语言,而假设的判定器 使得翻转后的对角线是可计算的。
例题 5.1.12
(使用莱斯定理,以及它何时不适用)
令 。语言 可识别且属于 , 可识别且不属于 ,所以 不可判定。相反,“ 至多有五个状态”涉及的是 的描述而不是语言 :语言相同的两台机器规模可以不同。莱斯(Rice)定理不适用,事实上这个问题通过读取 就可判定。类似地,“ 在十步之内接受 ”通过模拟十步即可判定。
常见错误
常见错误
(等待识别器不能揭示非成员关系)
不要混淆识别器与判定器。识别器在语言之外的字上可能不停机,所以运行它并等待并不能揭示非成员关系。
常见错误
(不可判定不等于无法分析)
不要说停机问题表明某台特定的机器“无法被分析”:对固定的机器和固定的输入,问题有确定的是或否的答案,并且存在输出该答案的平凡机器。不可判定性说的是对所有实例的同一个统一过程。
常见错误
(莱斯定理针对语言,而非描述)
不要把莱斯定理应用到机器描述或运行时间的性质上。
总结
图灵机有格局,通用机器可以根据描述模拟任何机器。一个语言可判定当且仅当它与其补集都可识别,这由交错执行证明。对角线论证表明自接受不可判定,归约把这一结论传递到接受、停机和空输入上的停机。莱斯定理使被识别语言的每个非平凡性质都不可判定。正则、上下文无关、上下文有关、可判定和可识别这几个类构成一条严格的链,前三个环节依赖前面各章。
练习
练习 5.1.13
(证明可判定语言对补和交封闭,可识别语言对并和交封闭。)
核心证明
解答(3)
- 1
判定器:补与交
若 判定 ,交换接受与拒绝就判定补集。对两个判定器的交集,同时运行两者并仅当二者都接受时接受;两者都停机。
- 2
识别器:交集
对识别器 ,先运行 再运行 ,仅当二者都接受时接受。若 ,两个阶段都以接受结束;若 在任一语言之外,相应阶段永不接受,所以 被正确地永不接受。
依据: 识别器从不接受语言之外的字,无论它是否停机。
- 3
识别器:以交错执行处理并集
∎交错执行两台机器,只要其中一台接受就接受;先后运行是错误的,因为第一台机器可能在第二台接受的字上循环。
练习 5.1.14
(证明 且 蕴含 ,并证明 蕴含 。)
核心证明
解答(3)
- 1
复合两个映射
设 与 为全可计算函数,使 且 。则 。
- 2
验证复合映射是归约
是全可计算的,所以 。
依据: 全可计算函数的复合仍是全可计算函数。
- 3
补集使用同一个映射
∎对等价式 取否定,得 ,所以同一个 把 归约到 。
快速检查
(证明 不可判定。)
这描述的是语言的哪一种性质?它是否非平凡?
解答 · 答案
令 为无限的可识别语言所成的集合。 可识别且无限,所以属于 ; 可识别但不是无限的。所以 非平凡,莱斯定理适用。
快速检查
(在第一个例题的机器上跟踪输入 ,并说明结果。)
每一轮把一个 与一个 配对。
解答 · 答案
。在 读到 时机器拒绝。该字的 比 多,所以拒绝是正确的。