Enumerator (computer science)
An enumerator is an automaton 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. An enumerator is equivalent to a Turing machine. Formal definition. An enumerator formula_1 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: formula_2 where 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. This shows Turing recognizable languages are also recursively enumerable. Proof A Turing Recognizable language can be Enumerated by an Enumerator Consider a Turing Machine formula_12 and the language accepted by it be formula_13. Since the set of all possible strings over the input alphabet formula_4 i.e. the Kleene Closure formula_15 is a countable set, we can enumerate the strings in it as formula_16 etc. Then the Enumerator enumerating the language formula_13 will follow the steps: Now the question comes whether every string in the language formula_13 will be printed by the Enumerator  we constructed. For any string formula_22 in the language formula_13 the TM formula_12 will run finite number of steps(let it be formula_25 for formula_22) to accept it. Then in the formula_25-th step of the Enumerator formula_22 will be printed. Thus the Enumerator will print every string formula_12 recognizes but a single string may be printed several times. An Enumerable Language is Turing Recognizable It's very easy to construct a Turing Machine formula_12 that recognizes the enumerable language formula_31. We can have two tapes. On one tape we take the input string and on the other tape, we run  the enumerator to enumerate the strings in the language one after another. Once a string is printed in the second tape we compare it with the input in the first tape. If its a match, then we accept the input, else reject.