动机
Cantor 论证从假定列表中构造一个遗漏对象。可计算性进一步要求:列表或构造能否由有限、有效的步骤完成?程序至多可数只说明某些集合不可判定,却不能识别某个具体问题。停机问题用更精确的自输入对角化,迫使假定判定程序违背自己的预测。
结论针对必须在每个合法输入上终止并正确回答的统一算法,不表示每个具体程序都无法分析。显式无限循环可证明不停机,有限运算可证明停机;不存在的是通吃所有程序及输入的终止方法。
定义
定义 5.1.1
(图灵机与可计算函数)
固定确定性图灵机(Turing machine)模型:有限状态集、含空白的有限纸带字母表、以整数编号的纸带格、一个读写头和有限转移表。每个非终止步骤读取当前符号、写入符号、左右移动一格并改变状态。输入为其余全空白纸带上的有限二进制字。指定终止状态表示停机,用固定有效约定把自然数输入输出编码为有限字。
机器计算部分函数 :停机时返回输出值,不停机时无定义。可约定每次停机都返回某个自然数。若对每个输入都停机给出函数值,则为全可计算函数。部分性不允许在不停机输入上随意指定一个答案。
有限描述可有效枚举为 ;非法描述解释为固定不停机机器。记其部分函数为 。通用模拟器对 解码转移表并逐步模拟 。配置由状态、读写头位置和有限多个非空白格表示,所以每个有限步骤可在有限字符串上有效执行,得到部分可计算 。通用性不保证终止。
定义 5.1.2
(可判定集、半可判定集与多一归约)
可判定,指其特征函数全可计算;半可判定(可计算可枚举),指某程序恰在成员上停机。会停机拒绝的识别器可改为拒绝时循环,符合此约定。多一归约 是全可计算函数 ,满足 。
定理/命题
定理 5.1.3
(对角停机集)
对角停机集
半可判定而不可判定。
定理 5.1.4
(互补的半判定)
集合可判定,当且仅当它与其补集都半可判定。因此 不半可判定。
定理 5.1.5
(以归约转移)
若 ,则 可判定推出 可判定; 半可判定推出 半可判定。把已知不可判定的 归约到 ,便可证明 不可判定。
定理 5.1.6
(Rice 定理(部分函数))
部分可计算函数的任意非平凡性质 ,其指标集 都不可判定。非平凡指有函数满足、也有函数不满足;性质必须只依赖计算出的部分函数,而非程序字面或运行时间。
证明思路
证明
(对角程序击败任何停机判定器)
模拟 ,它停机时才停机,便半判定 。假设全程序 判定 ,成员输出 ,否则输出 。构造 :先算 ;若为 则永久循环,若为 则停机。设 的指标为 。 会使 不停机,违背成员预测; 又使它停机,违背非成员预测。两种答案都矛盾。假设 存在时,对它的调用可以写成有限程序,故 确实在枚举中。
证明透视
对角矛盾的精确依赖
矛盾同时假设 正确且全定义。全定义保证 总能走到分支,因此 的预测确实决定 是否停机;正确性随后在以自身代码为输入时遭到两种分支共同否定。若 只是停机识别器,它可能不终止,分支论证就不成立,因而不会与通用模拟矛盾。
另一个条件是有效自应用:指标是自然数,所以程序描述可以作为普通数值输入。机器不需要神秘地察看自身,也不需要在运行中先算出自己的指标。在假设下写出有限描述 后,数学论证知道它有某个指标 ,再考察输入 。外部证明与程序实际执行的指令是两层不同的推理。明确这一区别,既排除假自指的疑虑,也说明为何同样的构造排除了对所有列出程序都全定义的通用求值器。
证明
(交错执行两个半判定器)
可判定集显然给出两个方向的半判定:遇到不要的答案就循环。反过来,交替执行 与其补集的半判定程序,每次各一步,直到一个停机,再返回对应答案。恰有一个最终停机。这个交错模拟不能先等第一个完全结束再运行第二个。若 的补集也半可判定,就会得到 的判定器,矛盾。
证明
(与全可计算归约复合)
归约定理中先计算必终止的 ,再运行 的相应程序;成员等价保证正确。若预处理不保证终止,就不能从简单的 得到判定器。
证明
(仅在 停机后才运行 的包装程序)
Rice 定理中,令 为处处无定义函数。先设 ,固定一个属于 的部分可计算函数 。从 有效写出程序 :先模拟 ,停机后才运行 。把数字 插入固定包装程序是总能完成的语法操作,映射 全可计算。若 ,所得函数为 ;若 ,所得函数为 。因此判定语义性质便判定了 。若 ,对不含 的互补性质应用同一论证;判定一个集合也能判定其补集,故仍矛盾。
反例模式
Rice 定理需要关于所计算函数的性质
声称:程序指标的每个非平凡性质,其指标集都不可判定。取
它是非平凡的。一台只有起始状态和终止状态的机器,若在起始状态中重写所读符号并永远向右移动,就属于 并计算 。再添加十一个无法到达的状态,所得机器仍计算 ,却不属于 ;因此 不是由 决定的。然而 可判定:给定 ,解码其描述(非法描述代表固定的不停机机器,其状态数已知)并数状态,这种有限的语法分析总会终止。
Rice 的证明在此失效,因为其归约需要 是否属于该集合只取决于它计算 还是 。对 而言,这取决于包装程序的大小,与 是否停机无关。修正后的假设是外延性: 必须推出 ,这正是说 对某个部分函数性质 形如 。
例题
例题 5.1.7
(有界停机可判定)
给定 ,模拟至多 步,检查是否到终止状态,并统一约定初始配置为时刻零。这是有限过程。无界停机询问是否存在某个时间而不给界。逐个搜索能半判定;若不存在,搜索无法证实失败。
概念视角结构
半可判定集是可判定关系的投影
有界停机给出半可判定性的第二种描述。集合 半可判定,当且仅当对某个可判定关系 有 。若程序 恰在 上停机,就令 表示“ 在输入 上于 步内停机”。反过来,给定 ,依次检验 ,首次成功时停机。在可判定关系前加上一个无界存在量词,正是半判定程序所做的搜索。
例题 5.1.8
(固定输入也困难)
令 。给定 ,写一个忽略输入而模拟 的程序。其代码 可有效计算,且 。所以 不可判定。写包装程序时不需要先解决被模拟的运算。
例题 5.1.9
(语义与语法)
“描述是否至多十个状态”可解析有限文本判定。“是否计算恒零全函数”是非平凡语义性质,由 Rice 不可判定。“是否对每个输入停机”也是。Rice 本身不判断这些问题是否半可判定;它只排除判定器。
例题 5.1.10
(可数性比停机对角化弱)
所有程序可数,所有自然数子集不可数,故存在不可判定集合,但不能据此认定 。自输入论证才识别 。同理,不存在列出全部全可计算函数且具有全可计算求值器 的有效枚举,否则 全可计算,却不同于每个列出的函数。全部部分可计算函数则有通用的部分求值器;其可能不终止恰好阻止这个矛盾。
例题 5.1.11
(识别与枚举等价)
“可计算可枚举”有直接的过程含义。若程序恰在 上停机,阶段 中对输入 各模拟 步,打印已检测到停机的输入,允许重复。打印的都在 ;若 于 步停机,任何足够大的阶段 都能检测它。因此恰好所有成员最终都会被打印。空集由永不打印的过程表示。
反向,若可计算的持续过程恰打印 的成员,允许重复或停顿,则给定 ,模拟至打印 时停机,便半判定成员关系。不需要判断沉默是否永久。无限可枚举集若另有严格递增的有效枚举,就会更强:搜索到输出达到或超过 即可判定是否属于,因为无限递增自然数序列无界。因此 这样的不可判定可枚举集,不会有有效的递增枚举。重复不改变集合,但列表的到达次序可以带来额外的计算信息。
参数与自指
上面几个论证都从指标 出发,写出一个把 内置其中的新程序的代码。这一步用得极多,值得精确陈述;把它单独提出后,还能得到一个关于程序的不动点定理。
若两边都无定义,或两边都有定义且相等,记 。二元部分函数经固定的可计算双射 接收单一输入 。
定理 5.1.12
(参数定理(s-m-n))
对每个部分可计算函数 ,存在全可计算函数 ,使所有 都满足 。
证明
(把参数写死在程序里)
固定一台在配对输入上计算 的机器 。对给定的 ,令 为这样的机器:在输入 上,先把 的二进制字写在输入左边,再由这两个字算出 ,然后对结果运行 。只有第一阶段依赖 :它是一串新状态, 的每一位对应一个,各自写下该位并左移,之后以固定步骤回到字的开头。其余阶段使用固定的转移表。因此从 产生 的转移表,是对有限字符串一致而必然终止的操作, 的指标 是全可计算的。按构造, 停机当且仅当 停机,而且输出相同。
Rice 定理证明中的包装程序 、把 归约到 的映射,以及把每个半可判定集归约到 的映射,都是这个定理的实例:每次都只写一个二元程序,再由 固定第一个变元。
定理 5.1.13
(Kleene 递归定理)
对每个全可计算函数 ,存在指标 ,使 作为部分函数成立。
证明
(被求值而不是被否定的对角线)
令 :运行 ,若它停机并给出值 ,就在输入 上运行程序 。这是部分可计算函数,所以参数定理给出全可计算的 ,使 有定义时 ,而 无定义时 处处无定义。复合 全可计算,故对某个指标 有 。由于 全定义, 有定义,因此
所以 就是所需指标。
证明透视
停机证明在此处否定,这个证明在此处求值
两个证明都把指标输入给自己。停机论证构造一个与假定判定器的预测背道而驰的程序,矛盾说明判定器不存在。这里没有任何否定: 只是模仿 所指的程序。先在自应用之前施加 ,再取 ,便使程序 与 计算同一个部分函数。 的全定义性只用了一次,用来保证 有定义。定理并不断言 ;两个不同指标可以计算同一函数,一般情况下也确实如此。
例题 5.1.14
(输出自身指标的程序)
设 是“忽略输入并输出 ”的程序的指标。对 应用参数定理,可知 全可计算。递归定理给出 使 ,即取值恒为 的常数函数。所以程序 在每个输入上都输出自己的指标。这种自指是关于一个固定有效编号的定理,不是机器模型额外附加的功能;这也说明证明中让构造出的程序“使用自己的代码”是合法的。
定理 5.1.15
(全定义性既不半可判定,其补集也不半可判定)
令 。 与 都不半可判定。
证明
(从停机集出发的两个归约)
第一,参数定理给出全可计算的 :程序 在输入 上模拟 ,模拟停机时输出 。于是 时 全定义, 时处处无定义。所以 把 归约到 。若 半可判定, 也会半可判定,这是错的。
第二,令 为全可计算函数,使程序 在输入 上模拟 共 步:若模拟在这些步内已停机,便永久循环,否则输出 。若 ,每个输入都得到 ,故 。若 且 在 步后停机,则程序 在每个 上都不停机。所以 把 归约到 , 也不半可判定。
Rice 定理只给出 不可判定。这两个归约说得更多: 甚至不能归约到 ,因为多一归约到半可判定集 的集合都半可判定。
常见错误
常见错误
(沉默不是拒绝)
半判定器沉默不是否定;超时只说明尚未停机。
常见错误
(从已知困难问题出发归约)
归约要把已知困难问题送到新问题,反向箭头不证明新问题困难。
常见错误
(停机定理关乎模型,而非计算速度)
Church–Turing 论题把非形式的有效计算与形式模型联系起来,不是仅靠定义一种模型就证明的定理。停机定理则是该模型中的精确结论。单纯加快同一有效框架中的计算速度不会避开矛盾。本节也没有对物理上可实现的超计算作判断。
允许机器查询一个固定集合,会把这里每个论证相对化,并产生严格更难的停机问题。
通往推广的路径
可以查询一个固定集合的机器
允许机器查询一个固定集合,会把这里每个论证相对化,并产生严格更难的停机问题。
允许机器在一步之内询问某个数是否属于固定集合 ,即谕示(oracle)。程序仍是有限描述,通用模拟器仍然存在,对角证明也照样成立:带谕示 的机器的停机集 相对于 半可判定,却不相对于 可判定。取 ,便得到一个连能够查询 的机器也无法判定的停机问题。
总结
有限描述允许通用模拟,自输入对角化排除停机的全判定器。交错模拟区分判定与半判定,有效归约传递障碍,Rice 定理把它扩展到计算所得部分函数的所有非平凡性质。参数定理把“把指标写进程序”形式化,Kleene 递归定理再把它变成每个有效程序变换的不动点;全定义性既不半可判定,其补集也不半可判定。
练习
快速检查
(证明两个半可判定集的并、交仍半可判定,并解释补集为何不同。)
解答 · 答案
并集交替模拟两者,任何一个停机就停;交集交替模拟并记录各自是否已停机,两个都停后才停。非成员永远不会满足相应条件。 半可判定而补集不半可判定,说明补集不封闭。
快速检查
(用固定可计算配对编码,证明 半可判定且不可判定。)
解答 · 答案
通用模拟器半判定 。映射 全可计算并把 归约到 ,所以 的判定器将给出 的判定器。配对编码只改变输入格式且可有效逆转。
快速检查
(证明“部分函数定义域为空”不可判定,并判断其补性质是否半可判定。)
解答 · 答案
空定义域是非平凡语义性质,由 Rice 不可判定。非空定义域可半判定:阶段 中,对输入 各模拟 步,只要任何一个停机就停。存在停机输入时足够大的阶段会检测到。若空定义域也半可判定,互补半判定定理便会给出判定器,故它不半可判定。
快速检查
(学生提议运行程序,直到停机或配置重复。为何对只有有限配置的确定性机器有效,而对一般图灵机无效?)
解答 · 答案
确定性使重复配置进入永久循环;配置数有限时,鸽巢原理保证不停机运行必重复,故检查会完成。无限纸带则可能产生无限多个不同配置。一直向右走并在新格写标记的程序永不重复,检验它的过程也永远不结束。状态有限不等于配置有限。
快速检查
(由递归定理推出 Rice 定理:若对非平凡性质 , 可判定,构造一个与递归定理矛盾的全可计算函数 。)
解答 · 答案
取 、,令 时 , 时 。 的判定器使 全可计算,所以某个 满足 。是否属于 只取决于所计算的函数。若 ,则 且 ,故 ;若 ,则 且 ,故 。两种情况都矛盾。
快速检查
(证明存在指标 ,使每个 都有 。)
解答 · 答案
对 应用参数定理,得到全可计算的 ,使 。递归定理给出 使 ,所以每个 都有 。取 即可。
快速检查
(令 。沿用 证明中的两个归约,证明 及其补集都不半可判定。)
解答 · 答案
映射 把 送到定义域为空(因而有限)的程序,把 送到全定义程序,其定义域无限。所以 把 归约到 , 不半可判定。映射 把 送到全定义程序,把停机时间为 的 送到定义域为 的程序。所以 把 归约到 ,补集也不半可判定。