枚举器

识别器检查一个给定候选，枚举器则持续产生有接受证据的对象。某个字被打印出来，便获得了有限的正证据；迟迟没有出现时，它既可能永远不出现，也可能仍在等待一段很长的计算。

允许重复不会改变可枚举集合：记录已经打印过的字，就能过滤重复。输出次序则有不同作用，要求按固定顺序递增会限制机器的能力，因为它必须处理尚未出现的较小候选。

所有二进制字可按长度—字典序依次输出：$\epsilon ,\mathtt{\text{0}},\mathtt{\text{1}},\mathtt{\text{00}},\mathtt{\text{01}},\dots$。要枚举某台机器接受的语言，可在第 $s$ 轮从头模拟前 $s$ 个输入各 $s$ 步，把在这些步内接受的输入打印出来。这样，每个会接受的输入都将在足够晚的一轮出现；某个输入上的死循环只占用有限步，不会阻挡其他候选。枚举会停机的程序—输入对时，把输出条件换成“模拟已停机”即可。

若要求按长度—字典序严格递增输出，存在这样的枚举器当且仅当语言可判定。正向构造依次检查所有字，用判定器过滤非成员。反向对无限语言，持续枚举直到打印目标字或一个比它更大的字，分别回答接受或拒绝；严格递增的无限输出必然越过每个固定位置。有限语言本身可用有限表判定，空语言可由始终不输出的机器枚举。

枚举器刻画递归可枚举集合，并与 可识别语言理路可识别语言Turing-recognizable language · Recursively enumerable language存在图灵机对语言内输入接受、对语言外输入可拒绝或不停机的语言。 给出等价描述：语言可由 图灵机理路图灵机Turing machine通过有限控制、可读写纸带和移动读写头刻画一般算法计算能力的模型。 识别，当且仅当存在机器枚举其全部成员。这个等价把半判定过程转换为生成过程，也解释了证明搜索、程序生成、程序行为枚举与形式系统定理集合为何常能被机械列出，却不能总能判定非成员。与 可判定性理路可判定语言Decidability · Recursive language · Decidable language存在统一、总能停机且正确回答成员资格的判定器；等价于语言及其补语言都可识别。 相比，差别正落在“缺席是否能在有限时间内确认”。