形式陈述

语言 $L$$L$ 称余可识别，若其补集 $\overline L$$\bar{L}$ 可由图灵机识别：对 $x\notin L$$x\notin L$，机器最终接受；对 $x\in L$$x\in L$，机器可以拒绝或永不停止。一个语言可判定当且仅当它同时可识别且余可识别。证明反向时可交错模拟识别 $L$$L$ 与识别 $\overline L$$\bar{L}$ 的两台机器，二者必有一台最终接受。

直觉

可识别性提供“是”的有限证据，余可识别性提供“否”的有限证据；两类证据都存在时，交错搜索总会找到其中之一，于是得到真正的判定程序。

例子与边界

停机问题语言 $HALT$$HALT$ 可识别：直接模拟并在停机时接受；其补集不可识别，否则 $HALT$$HALT$ 将可判定。可识别机器在非成员上允许永不停止，因此“运行后没有接受”不是有限拒绝证据。余可识别不是概率意义上的“高概率拒绝”，也不等于把某台半判定器的接受与拒绝状态交换，因为发散行为不会交换成接受。

推论与应用

该概念精确区分可判定、半可判定和不可半判定问题，是证明不可判定性、算术层级入口以及程序验证中正负证据不对称性的基础。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1936，Full paper。