余可识别语言

可识别性只要求成员最终被接受，非成员上的计算可以永远不结束；余可识别性把这种单边保证放到补语言上。因此，可把两者想成两台可能不停止的程序：一台寻找“是”的有限证据，另一台寻找“否”的有限证据。若两边都存在这样的半判定过程，就能交错运行它们，必有一台先给出答案，从而得到真正的判定器。

停机问题语言 $HALT$，通常记作 $HAL{T}_{TM}$，是可识别的：直接模拟 $M(w)$，一旦停机就接受；它的补语言不可识别，否则同时运行两台识别器便能判定停机问题。因此 $HAL{T}_{TM}$ 不是余可识别语言，而 $\overline{HAL{T}_{TM}}$ 是余可识别但不可识别的标准例子。

可识别机器在非成员上允许永不停止，所以“程序在有限时间内没有接受”不能作为拒绝证据：它也许只是在慢慢运行。余可识别既不是概率意义上的“高概率拒绝”，也不等于交换某台半判定器的接受与拒绝状态，因为发散行为不会因此变成接受；它也不意味着枚举所有非成员后可以立即判断缺席，无限枚举中的缺席本身无法在有限时刻观察。

余可识别性精确区分可判定、半可判定和不可半判定问题，并揭示程序验证中正负证据的不对称；它也是进入算术层级和证明不可判定性的基础。由 可识别语言公理库可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。 与余可识别语言的交汇可刻画 可判定性公理库可判定语言Decidability · Recursive language · Decidable language存在对所有输入都停机并正确回答成员资格的图灵机语言类。：$L$ 可判定当且仅当 $L$ 与 $\bar{L}$ 都可识别。这个等价是许多不可判定性论证的收束点，并可与 映射归约公理库映射归约Mapping reduction · Many-one reduction用可计算函数把一个语言成员关系变换为另一个语言成员关系。 配合，把“一边可识别、另一边不可识别”的边界传递到新问题。