程序可以回答某些关于其他程序的问题。例如,运行一个程序并观察到它停止,就证明这次运行会停机。但等了很久仍看不到它停止,并不能告诉我们它以后会不会停止。核心问题是:是否存在一个算法,能对所有情形给出答案,包括被模拟程序永远运行的情形?
我们先在明确的计算模型下证明答案是否定的,再用归约证明另一个问题不可判定。这个结论并不是说每个实例都很难,也不是说人永远无法判断某个具体程序的行为;它说的是,不存在一个对所有编码实例都停机且答案正确的统一算法。
识别和判定
固定一套标准的有效编码,把图灵机(Turing machine)写成有限字符串。我们可以检查字符串在语法上是否为有效编码,也可以逐步模拟一台机器。用 表示 的编码,用 表示可有效解码的机器与输入的配对。
定义 5.2.1
(判定器与识别器)
语言 的判定器对每个输入都停机,并恰好接受 中的字符串;对其余字符串停机并拒绝。 的识别器接受 的所有字符串,也不会错误接受 以外的字符串,但在 以外的输入上可以永远运行。
因此每个判定器都是识别器,但定义并不要求识别器对否定实例发出信号。“尚未接受”与“已经拒绝”是不同的观察。
定义 5.2.2
(停机语言)
停机语言是
这里停机包括 接受或拒绝,并不只指接受。格式不正确的编码不属于该语言,可以先经语法检查而拒绝。
常见错误
(停机不等于接受)
容易把 读成 接受的配对 所成的集合。但一台机器立即拒绝 时它已经停机,所以 。 接受的配对所成的集合是另一个语言。
例题 5.2.3
(识别器可以确认肯定实例)
给定有效配对 ,模拟 在 上的运行;一旦模拟停止就接受。当 真的停止时,识别器最终会接受;若 永远运行,识别器也一直运行。它不会错误接受不停机的配对。这识别了 ,但下面会证明,不能把它修补成适用于所有配对的判定器。
假设判定器存在,再反转它的答案
定理 5.2.4
(停机问题的不可判定性)
没有判定器:不存在一台图灵机,对每个输入都停机,并恰好接受那些 在 上停机的字符串 。
证明
(对角机与任何停机判定器矛盾)
反设存在判定器 :对每个有效配对 都停机,且恰在 于 上停机时回答“是”,否则回答“否”。
构造接受一个字符串 的机器 :
- 若 不是有效的机器编码,拒绝。
- 若 ,把配对 交给 。
- 若 回答“是”,永远循环;若回答“否”,立即接受。
是合法机器:检查编码、构造配对以及调用 都可以有效进行,最后两个分支也已明确指定。因此它自己的有限编码 是它的有效输入。
在输入 上运行 ,它会问 : 在 上是否停机?由于假设 是判定器,这次调用必须回答“是”或“否”。
若 答“是”,其正确性表示 停机;但 的定义却使这次运行永远循环。若 答“否”,其正确性表示该次运行不停机;但 会立即接受,因而停机。两种答案都与 的假设正确性矛盾。
所以这种判定器不存在, 不可判定。上面的识别器依然存在:不可判定是指不存在对所有输入停机且正确的判定器,并不是指不能识别肯定实例。
证明透视
对角线证明在哪里用到假设
的总停机性用来保证 的第 2 步一定有答案。若 在 上可以永远运行,那么 在 上只是不停机,而这并不矛盾。 的正确性只用在一个配对 上。不显然的一步是把 自己的编码交给 ,让 去预测自己,再令 做出与预测相反的行为。论证之所以封闭,是因为总停机的 只能给出两种答案,而每一种都与正确性矛盾。
这里的自引用并不是要求机器去猜一个不可能的输出。机器及其输入都是同一套有效编码系统中的字符串; 把自己已经存在的有效编码当作数据接收。矛盾依赖于 在这个配对上既必然停机又正确;去掉其中任何一个保证,就不能原封不动地得到同一结论。
例题 5.2.5
(反驳两个具体的候选判定器)
取候选 ,它对每个配对都回答“否”,并设 为由它构造的对角机。对有效编码, 得到“否”并接受,所以 在 上停机,而 却对配对 回答“否”。再取 ,它对每个配对都回答“是”。由它构造的 对每个有效编码都永远循环,特别是在 上,而 却声称它会停机。每个候选都在自己对角机的对角输入上答错。边界情形:对不是有效编码的字符串, 与 都直接拒绝;反驳只用到对角输入。
反例模式
时间上限不能判定停机
固定正整数 。假设测试模拟 共 步,仍未停止就回答“否”。但一台机器可以先做 步无害的工作,然后停机;测试就在这个停机实例上答错。提高固定上限只会改变反例,不会使方法普遍正确。
归约:改变输入,但保留答案
考虑看似更窄的语言:
定义 5.2.6
(多对一归约)
从语言 到 的多对一归约,记作 ,是字符串上的全函数且可计算的函数 ,满足
构造新实例时不能先知道旧实例的答案。若有 的判定器,就先算出 ,再运行该判定器并返回它的答案;两个阶段都停机,便得到 的判定器。
定理 5.2.7
(空输入停机问题不可判定)
下面构造的映射 是多对一归约 。因此 不可判定。
证明
(从任意输入停机归约到空输入停机)
对有效的 ,有效地构造机器 :忽略它自己的输入,模拟 在固定字符串 上的运行。我们可以机械地把 与 的有限描述嵌入模拟程序,因此这段代码可以有效生成。令
若 格式不正确,就输出一台固定的永远循环机器的编码。这使 对所有字符串都有定义,也保持了格式错误的字符串不属于 这个事实。
在空输入上, 恰在 于 上停机时停机。因此
所以 。若 有判定器,上述程序就能判定 ,与对角线论证矛盾。故 不可判定。
证明透视
为什么归约映射只负责写代码
映射 只写出 的代码,从不运行 :若构造 需要先知道 在 上是否停机,这个归约就已经解决了停机问题。 对所有字符串都有定义,这解释了格式错误的分支:由 构造出的 判定器必须处理每一个字符串。等价式的两个方向都用到: 在 上停机,就是 在空输入上停机;不停机则仍然不停机。最后,方向至关重要:被转移到目标 的,是来源 经对角线论证得到的不可判定性。
常见错误
(把归约方向弄反)
箭头方向很重要:我们把已知不可判定的问题转成目标问题。只证明 并不能推出 不可判定,因为容易的问题也可能归约到困难问题。事实上这里也存在反方向的归约,但证明中用到的不是它。
例题 5.2.8
(把归约应用到具体输入)
设 在输入 上停机,在其他每个输入上都永远运行。对 ,机器 忽略自己的输入并模拟 ,所以它在 上停机: 且 。对 , 模拟 并永远运行,所以 且 。两个像都由同一个机械的包装程序产生,不需要运行 。边界情形:若 不是有效配对, 是固定循环机器的编码,于是 且 ,等价式对格式错误的字符串同样成立。
尽管如此, 是可识别的:给定有效的 ,模拟 在 上的运行;若停止就接受。若永远循环,则没有否定答案,与 的情形一样。这并没有产生判定器。
练习与解答
快速检查
(模拟已经运行了一百万步仍未停止,这能证明它永远不停机吗?)
想一想有限轨迹能排除什么、不能排除什么。
解答 · 答案
不能。若程序在第一百万零一步停止,到目前为止的观察完全相同。有限轨迹可以证明某次运行已经停机,但这个观察本身不能证明它永远不会停止。
快速检查
(对角线证明中,若 说 在自己的编码上停机,会发生什么?)
看看 回答“是”时 走哪个分支。
解答 · 答案
的定义使它在 说“是”时永远循环; 的正确性却要求同一次运行停机,构成矛盾。回答“否”则有相反的矛盾,因为 会立即接受并停机。
快速检查
(给定 及 ,描述归约使用的空输入机器。构造它时是否要先判定 在 上是否停机?)
写出包装程序的代码,与运行它是同一回事吗?
解答 · 答案
生成一个嵌入 及 的包装机器 ;它忽略自己的输入并模拟 。因此 在 上的行为恰好是 的行为。生成代码是有限的语法操作,不需要把模拟运行到结束,也不需要先判断它是否停机。
快速检查
(若问题 可归约到不可判定问题 ,单凭这一点可以推出 不可判定吗?)
想一个明显可判定的 ,以及它到某个已知不可判定语言的映射。
解答 · 答案
不能。例如,空语言可以归约到任何有可计算固定非成员的语言,但空语言本身可判定。若要用 证明目标 不可判定,要从已知不可判定的 出发,构造可计算归约 。
不可判定性说的是,指定的问题不存在对所有输入都终止的统一程序。对个别程序,我们仍可能给出简短的停机或不停机证明;不能保证的是对每个编码程序与输入都作出正确的有限回答。