可识别语言

识别器提供单边可靠性：对“是”实例必须最终给出接受证据，非成员却可能被拒绝，也可能一直搜索、永远运行。因而“接受”是可有限验证的事件，“尚未接受”不是结论。这个不对称恰好容纳无界搜索——只要见证存在，按系统方式枚举总会找到；不存在见证时没有统一的停止时刻。判定器则必须在有限时间内同时解决正反两面。

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

语言 ${\mathrm{NONEMPTY}}_{TM}=\{⟨M⟩:L(M)\ne \varnothing \}$ 可识别：按层交错模拟 $M$ 在所有字符串上的运行，一旦某个输入被接受便接受机器编码。它由 Rice 定理可知不可判定，展示了“存在某个成功输入”天然给出半判定而非判定。

识别器若在非成员上始终明确拒绝，它就已经是判定器。概率上偶尔接受错误实例的过程也不是这里的识别器，因为定义要求语言恰好等于被接受输入集合，而非高概率近似。

可识别性刻画半判定过程、定理枚举和存在性搜索，建立递归可枚举集合、部分可计算函数定义域与图灵机接受语言之间的对应；在Chomsky 层级公理库Chomsky 层级Chomsky hierarchy按产生式限制排列正则、上下文无关、上下文有关与递归可枚举语言，并由典型语言证明严格包含。中，它正是最一般的 Type 0 语言层。枚举器公理库枚举器Enumerator machine按某种顺序打印语言中全部字且不打印外部字的图灵机变体。与识别器等价：可交错模拟所有输入并输出被接受者，也可等待枚举器打印当前输入。若 $L$ 与补语言都可识别，则并行运行两台机器得到判定器公理库可判定语言Decidability · Recursive language · Decidable language存在对所有输入都停机并正确回答成员资格的图灵机语言类。；这把余可识别语言公理库余可识别语言Co-recognizable language · Co-r.e. language补语言可被图灵机识别的语言。与可判定性精确连接起来。