枚举器

识别器从给定候选出发寻找接受证据，枚举器则把语言看成一条可能无限延伸的输出流，系统地生成所有有证据的对象，而不是逐个回答成员资格。某个字符串只要最终被打印出来，就获得了有限的正证据；没有出现则无法在有限时间内判断它永远不会出现。交错模拟保证不会因某个永不停止的候选而阻塞后续候选，而允许重复和任意次序不会改变可枚举的集合，因为这些都可由额外 bookkeeping 消除。

所有二进制串可按长度和字典序依次输出：$\mathtt{\text{varepsilon}},\mathtt{\text{0}},\mathtt{\text{1}},\mathtt{\text{00}},\mathtt{\text{01}},\dots$。要枚举某台机器接受的语言，或所有会停机的程序—输入对，则应做 dovetailing：第 $s$ 轮各模拟前 $s$ 个输入 $s$ 步，发现接受或停机便输出。不能先把第一个输入模拟到结束再处理第二个，因为第一个可能永不停止并阻塞后续候选。一般枚举顺序不携带语义；只有对可判定语言，才能可靠确认某个较小候选不会到未来才出现，从而产生规范有序枚举。空语言则由永不输出的机器枚举。

枚举顺序若被额外要求严格递增，能力会变化：对可判定语言可以先判定再按序扫描；一般可识别语言未必有可计算的无重复有序枚举。有限时间内尚未输出某串，也不能据此拒绝它。

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