exercise 3.4


Give a formal definition of an enumerator. Consider it to be a type of two-tape Turing machine that uses its second tape as the printer. Include a definition of the enumerated language.


An enumerator is comparable to a two-tapes Turing machine, where the second tape moves only to the right. As proved by the theorem 3.13 (Sipser), a two-tapes TM is equivalent to a single tape TM, but keep two tapes is more useful for this answer.

We can describe an enumerator as:

En = (Q, Σ, {Γ1, Γ2}, δ, qaccept, qreject)

where δ(qi, a1, a2) = (qj, b1, b2, {L, R}, {R})

Since the printer is a write-only device and it can move only to the right, it's not necessary to specify what is the current character and where the head must be moved. So the final definition of δ is

δ(qi, a1) = (qj, b1, b2, {L, R})