可识别语言

可识别语言是形式语言理论中的字符串集合，不是对自然语言难易程度的分类。语言L可识别，意味着存在图灵机M，对每个输入x，M接受x当且仅当x∈L。对于非成员，M不能接受，但可以明确拒绝，也可以一直运行而不停止。

可判定语言要求更强：同一机器必须对所有输入停机，成员接受、非成员拒绝。因此每个可判定语言都可识别，反向却不成立。一个识别器已经运行很久，并不能仅凭等待时间判断输入不属于语言，除非另有已证明的停止界。

参考：[1]

可识别语言也称递归可枚举语言或可计算可枚举语言。这里“枚举”是指有一台程序能陆续输出恰好属于该语言的字符串，不要求按字典序、不要求每个只出现一次，也不要求输出过程最终结束。空语言可以对应从不输出字符串的枚举器。

给定枚举器，识别输入x的方法是一直查看输出，看到x就接受。反过来，给定识别器，不能先把它在第一个字符串上运行到底再处理下一个，因为一次无限循环会堵住所有后续输入。应按阶段扩展候选列表，并对各模拟交错推进有限步，打印已经接受的字符串。

参考：[3]

通用机器接受语言A_TM由所有〈M,w〉组成，其中M最终接受w。通用图灵机逐步模拟M在w上的运行，一旦看到接受就接受，因此A_TM可识别。但不存在能对所有机器与输入都正确回答这一问题并总会停机的判定器，故它不可判定。

其补语言包含M拒绝w以及M在w上永不停机的情况，不只是“明确拒绝”的那一部分。这个补语言不可识别。区分拒绝和不停机十分重要：如果把无限运行漏掉，得到的集合就不是A_TM的真正补集。

参考：[2]

假定L有识别器R，补语言有识别器S。构造一个新机器，在同一个输入上交替模拟R一步、S一步。R先接受便回答是，S先接受便回答否。每个输入恰好属于两边之一，所以相应识别器最终一定接受，新机器也一定停止，而且不会把答案弄反。

这一论证解释了A_TM的补集为何不可识别：若两边都可识别，就会推出A_TM可判定，与已知结果冲突。交错模拟是避免被不终止分支拖住的通用技巧，但它本身并不提供运行时间上界；“最终能确认”与“能迅速确认”仍是不同的计算性质。

参考：[2] [3]