An enumerator is a Turing machine with an attached printer.
The Turing machine can use that printer as an output device to print strings.
Every time the Turing machine wants to add a string to the list, it sends the string to the printer.
Enumerator is a type of Turing machine variant and is equivalent with Turing machine.
is the delimiter that marks end of an element of
The second tape can be regarded as the printer, strings on it are separated by
is defined as set of the strings on the second tape (the printer).
This shows Turing recognizable languages are also recursively enumerable.
Proof A Turing Recognizable language can be Enumerated by an Enumerator Consider a Turing Machine
Since the set of all possible strings over the input alphabet
is a countable set, we can enumerate the strings in it as
will follow the steps: Now the question comes whether every string in the language
will be printed by the Enumerator we constructed.
will run finite number of steps(let it be
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
that recognizes the enumerable language
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.
If it's a match, then we accept the input, otherwise we continue.
Note that if the string is not in the language, the turing machine will never halt, thus rejecting the string.
This theoretical computer science–related article is a stub.