形式陈述

语言 $L\subseteq\Sigma^*$$L\subseteq {\mathrm{\Sigma }}^{\ast }$ 称为图灵可识别语言，若存在图灵机 $M$$M$ 满足：当 $w\in L$$w\in L$ 时，$M$$M$ 最终接受；当 $w\notin L$$w\notin L$ 时，$M$$M$ 可以拒绝，也可以永不停机。若对所有输入都停机，则 $M$$M$ 是判定器，$L$$L$ 可判定。等价地，可识别语言可以由枚举器列出；并且

$$ L\text{ 可判定} \quad\Longleftrightarrow\quad L\text{ 与 }\overline L\text{ 都可识别}. $$$$L\text{ 可判定}⟺L\text{ 与 }\bar{L}\text{ 都可识别}.$$

后一结论通过交错模拟两个识别器得到。

直觉

识别器对“是”实例必须最终给出证据，但对“否”实例可以一直搜索。判定器则必须在有限时间内同时解决正反两面。

例子与边界

接受问题 $A_{TM}=\{\langle M,w\rangle:M\text{ 接受 }w\}$$A_{TM}=\{⟨M,w⟩:M\text{ 接受 }w\}$ 可识别：直接模拟 $M$$M$；它不可判定，其补语言也不可识别。一个有限语言当然可判定，因而可识别。可识别不等于“随机试验最终大概率发现”，定义要求每个成员输入确定地在有限步内被接受。

推论与应用

可识别性刻画半判定过程、定理枚举和存在性搜索。它建立递归可枚举集合、部分可计算函数定义域与图灵机接受语言之间的对应，并为 Rice 定理和映射归约提供对象层次。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 3–4, Turing-recognizable and decidable languages。
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1936，Full paper, computable sequences and machine enumeration。