Is Enumerator a variant of Turing machine that starts with empty string and builds according to the description of language

Question

My understanding is an "Enumerator" is a Turing Machine that: instead of taking an input string, then going through a series of transitions and "halting" or "not halting" on it, it does not accept any input string and it starts with a blank string and builds the final string according to the rules of the language

For example: if our language was L = { w | w is made up of 0^n1^n, where n >= 0 }

A normal Turing Machine would have a input tape and it would receive an input on that tape and this normal Turing Machine would go through a series of transitions to deduce whether this string belongs to the language or not

An enumerator, a variant of normal Turing Machine, would have 3 different tapes, an input tape + work tape + output tape. Since, we don't have any input we don't interact with input tape at all ( which means we can remove that tape if we want to ), the work tape is used as a temporary workspace for constructing strings - at the end when we finish constructing a string we may choose to copy the symbols from the work tape to output tape and adding a "#" symbol on the output tape at the end of the output tape which will act as a separator from the next string and we will then blank out the work tape, the output tape acts like a printer for string with '#' separating different strings

In an enumerator, to produce strings for the given language, we will start on a start state and then take the transition to write 'n' number of '0' on the work tape, then writing 'n' number of '1' on worktape ( using appropriate logic of crossing out / blank symbol for 'counting' ). Then once we are done with that we will go to a special state called the "enumeratored state" which will copy the symbols from the work tape to output tape ( again through a series of transitions ) and then blank out the work tape + add the separator symbol on the output tape

This will continue on forever for strings of all lengths unless we have designed to produce specific strings of this language

In a nutshell, enumerator just helps building strings according to a pattern whilst turing machines help to check if a certain strings adheres to a certain pattern

Which also gives rise to the theorem that: "A language is accepted by a Turing machine if and only if some enumerator enumerates it"

Is my understanding correct?

Answer 1

Your idea of "an enumerator" is pretty good.

In fact, you have recovered the origin of the term "recursively enumerable" as explained in the textbook Introduction to the Theory of Computation by Michael Sipser.

ENUMERATORS

As we mentioned earlier, some people use the term recursively enumerable language for Turing-recognizable language. That term originates from a type of Turing machine variant called an enumerator. Loosely defined, 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. Exercise 3.4 asks you to give a formal definition of an enumerator. The following figure depicts aschematic of this model.

Your theorem also appears in that book.

THEOREM 3.21

A language is Turing-recognizable if and only if some enumerator enumerates it.