余可识别语言

两边都有识别器，为什么就能判定 ​

一个语言满足

从左到右很直接：判定器总会停机，交换它的接受与拒绝即可判定补语言。

反向则不能先把识别 $L$ 的机器运行到底，再运行识别 $\bar{L}$ 的机器，因为第一台可能永远不结束。正确方法是交错模拟：第一台走一步，第二台走一步，反复进行。若第一台接受，回答“属于 $L$”；若第二台接受，回答“不属于 $L$”。某台拒绝时不据此停止整个过程，继续给另一台运行机会。

每个输入恰好属于 $L$ 或其补集，所以相应的识别器必定在有限步后接受；公平交错保证这一步终将被模拟到。因此组合后的机器对每个输入都停机，而且给出正确答案。这是把两个单边半判定过程拼成完整判定过程的机制。[1]

停机与不停机：最典型的不对称 ​

令

它可识别：直接模拟 $M(w)$，看到停机就接受。停机这一事实有有限证据——一段以停机状态结束的运行轨迹。关于“停机”与“不停机”的解释限于有效编码；无效编码可单独识别并归入补集，不影响以下结论。

停机问题不可判定性理路停机问题不可判定性Halting problem · Undecidability of halting用总停机判断器的自反转构造证明 HALT 不可判定，并区分识别、有限步数检查与局部终止性证明。说明 $HALT$ 没有总停机判定器。由上一节定理，它也不可能余可识别；否则停机与不停机各有一个识别器，交错运行就能判定停机问题。

于是

这里的逻辑方向容易弄反：不停机语言之所以余可识别，是因为它的补集“会停机”可识别，而不是因为我们能通过模拟最终看见“永远不停机”。

对某个具体程序，循环不变式或其他证明可能足以确认不停机；结论排除的是一个对所有不停机实例都最终给出确认的通用识别器，并不是说任何具体不停机事实都无法证明。

为什么交换两个状态不够 ​

对判定器交换接受与拒绝，可以得到补语言判定器；对一般识别器这样做则不成立。原机器在某个非成员上若永远运行，交换两个终止状态并不会让这条无限运行突然停机。

“已经跑了一百万步仍没接受”也只是有限观察，不能证明以后不会接受。无限枚举同样如此：一个元素迟迟没有出现，不代表它不会在更晚出现。等待的时间再长，只要没有额外的可计算界，就不会自动转化为负面证据。

因此可识别与余可识别是两种算法能力，不能由“把输出取反”这种表面操作互相转换；只有原过程总会结束时，取反才充分。

与全称条件、闭包和归约的联系 ​

把时间编码为自然数，可以把余可识别性写成

其中 $R$ 是可判定谓词。例如让 $R(x,t)$ 表示“补语言识别器在前 $t$ 步内没有接受 $x$”。反过来，遇到这样的全称式，可以逐个检查 $t$，一旦发现反例就接受补语言。因此余可识别集合正对应算术层级中的 ${\mathrm{\Pi }}_1^0$ 集合。这些检查只要求可计算，不要求多项式时间，不能把它与复杂度中的 coNP 混为一谈。

有限并与有限交也保留余可识别性：取补后分别变为可识别语言的有限交与有限并，再用交错模拟构造识别器即可。若 $f$ 是总可计算函数，$B$ 余可识别，则 $f^{-1}(B)$ 也余可识别：先算出 $f(x)$，再运行 $\bar{B}$ 的识别器。这是映射归约理路映射归约Mapping reduction · Many-one reduction用可计算函数把一个语言成员关系变换为另一个语言成员关系。传递单边可识别性的基础。

文法歧义理路文法歧义Grammar ambiguity同一终端字有不同语法树的性质；通过完整推导区分展开次序、消歧改写、固有歧义与解析器冲突。提供另一个具体例子：歧义可以由两棵有限语法树见证，无歧义 CFG 的集合因而余可识别。要证明它是否还能可识别，只需结合相应的不可判定性与“两边识别等于判定”的定理，而不必重新设计另一套机器。

与可识别语言理路可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。比较，余可识别性为非成员提供最终接受的保证。停机集及其补集证明两类互不包含；两类的交恰是可判定语言。因此这里比较的是半判定证据朝向，既不是互斥分类，也不是同一个单边算法的两种名称。