形式陈述

枚举器是带输出装置的图灵机，可在无限运行中依次打印有限串。它枚举的语言是曾被打印过的所有串；允许重复、乱序和有限或无限停顿。语言可被枚举当且仅当它可识别。由识别器到枚举器时，对所有输入做 dovetailing 交错模拟；由枚举器到识别器时，持续运行并在看到目标串时接受。若语言可判定，还可按长度—字典序无重复地枚举。

直觉

识别器从给定候选出发寻找接受证据，枚举器则系统地生成所有有证据的对象。交错模拟保证不会因某个永不停止的候选而阻塞后续候选。

例子与边界

所有会停机的程序—输入对可通过逐轮多跑一步的方式枚举。简单地“先模拟第一个输入直到结束，再模拟第二个”是错误的，因为第一个可能永不停止。枚举顺序通常不携带语义；只有对可判定语言，才能可靠判断某个较小候选不会在未来才出现，从而产生规范有序枚举。空语言由永不输出的机器枚举。

推论与应用

枚举器刻画递归可枚举集合，解释证明搜索、程序生成与形式系统定理集合为何常能被机械列出却不能总能判定非成员。

参考资料

• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., Cengage, 2013，Chs. 0–10。
• Alan M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem,” Proceedings of the London Mathematical Society, 1936，Full paper。