Enumerator (computer science)

An enumerator is a Turing machine that lists, possibly with repetitions, elements of some set S, which it is said to enumerate. A set enumerated by some enumerator is said to be recursively enumerable.

Formal definition

An enumerator $E$ is usually represented as a 2-tape Turing machine. One working tape, and one print tape. It can be defined by a 7-tuple, following the notation of a Turing machine: $E=\langle Q,\Sigma ,\Gamma ,\delta ,q_{0},q_{print},q_{reject}\rangle$ where

• $Q$ is a finite, non-empty set of states.
• $\Sigma$ is a finite, non-empty set of the output / print alphabet
• $\Gamma$ is a finite, non-empty set of the working tape alphabet
• $\delta$ is the transition function. $\delta :Q\times \Gamma \rightarrow Q\times \Gamma \times \{L,R\}\times \Sigma _{\epsilon }$
• $q_{0}\in Q$ is the start state
• $q_{print}\in Q$ is the print state.
• $q_{reject}$ is the reject state with $q_{print}\neq q_{reject}$

Equivalence of Enumerator and Turing Machines

A language over a finite alphabet is Turing Recognizable if and only if it can be enumerated by an enumerator. Sipser, Michael (2012). Introduction to the Theory of Computation - International Edition. ISBN 978-1-133-18781-3.