可识别语言

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

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

语言 ${\mathrm{NONEMPTY}}_{TM}=\{⟨M⟩:L(M)\ne \varnothing \}$ 可识别。先按长度再按字典序列出 $w_0,w_1,\dots$；第 $s$ 轮把前 $s+1$ 个输入各自从头模拟 $s$ 步，发现接受便接受机器编码。若某个 $w_j$ 在 $t$ 步接受，轮次 $s\ge max(j,t)$ 就一定找到它，每轮又都是有限工作。重复模拟虽然低效，却清楚证明所有有限成功运行都会被覆盖。

不能先把 $M(w_0)$ 跑完再处理 $w_1$：第一项可能永远循环，遮住后面的见证。若语言为空，各轮仍可继续而永远不接受；Rice 定理说明不存在统一判定器把这种无限等待普遍转换成否定答案。

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

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

Martin-Löf 随机性理路Martin-Löf 随机性Martin-Löf randomness · 马丁–勒夫随机性以统一可枚举、概率预算趋于零的开集检验，定义单条无限比特序列的随机性，并构造通用检验。把这种枚举机制用于描述无限比特序列的异常：程序统一列出带层号的有限前缀，每层所覆盖的概率受给定预算限制。关键是同一台程序描述整列检验；仅仅让每一层各自存在一个枚举器，会丢失所需的统一有效性。

余可识别性理路余可识别语言Co-recognizable language · Co-r.e. language补语言可识别的单边可计算性；用交错模拟、停机反例与全称谓词区分负面证据和总停机判定。把保证接受的一侧换成补集。两类在可判定语言处重合，但彼此都不包含：停机集可识别而不余可识别，其补集恰好相反。单边证据的方向不同，不能由同样允许发散就把两种定义混为一谈。