Turing Recognisable => enumerable

Question

I get the proof of going from an enumerator to a Turing Machine (keep running enumerator and see if it matches input) but I don't see how the other way works.

According to my notes and the book (Intro to the Theory of Computation - Sipser), to get Turing enumerator from a Turing machine, we basically write all combinations of the alphabet. You then run the TM on this input, if it accepts print it out, replace with new string repeat ad infinitum.

The problem I am having is surely this requires the language to be decidable. Otherwise it might get stuck on the third word in some infinite loop doomed never to accept or reject and certainly never print out the whole language.

What am I missing?

Answer 1

What's missing is the way you run the Turing Machine $M$ on strings to get the Enumerator. Rather than generate each string, run $M$, and then output this string if the $M$ accepts – which as you identified will not work – you do something like the following, which adopts the strategy of simulating many instances of the $M$ on different strings "in parallel".

Assume the tape has contents $\langle w_1, S_1\rangle \# \cdots \# \langle w_n, S_n\rangle$, where $w_i$ is some word under consideration and $S_i$ is the current state of $M$ operating on $w_i$. This represents that $n$ copies of $M$ are being simulated. $w_i$ is stored so we know what the original input was.

Now run the following loop

1. At the end the tape write the next string from $w\in\Sigma^*$, along with the initial configuration $S$ of $M$, that is, write $\# \langle w, S\rangle$.
2. Simulate each copy of the $M$ on the tape for one step. (Presumably use another tape.)
3. If any of the $M$s enters an accepting state, put the corresponding string onto the output tape. Remove this instance of $M$ from the tape.
4. If any of the $M$s enters a rejecting state, remove that instance of $M$ from the tape.
5. Goto step 1.

It is not hard to argue that all strings $w\in\Sigma^*$ accepted by $M$ will eventually be output on the tape.