The Theory of Computation

Bernard M.E. Moret

Addison-Wesley-Longman, 1998

Detailed Solution

Chapter 5, Problem 20

Intuitively, we can use a standard enumerating machine that may cause repetitions, but store every string printed so far on a tape and verify that newly generated strings do not appear on the tape before printing them. That is a simple filtering operation; it clearly terminates in finite time (although it is equally clearly very slow and very space-consuming). The result is a non-repeating enumerator, but does it always produce an input? If our enumerator does not take any input and runs forever, it is a trivial matter to convert it to a machine that prints the ith element and halts by running the enumerator internally until it has generated i elements, then printing the last generated element and halting.