# Where is the flaw in the following proof?

Where is the flaw in the following proof, that if a language is Turing recognizable then we can enumerate it?

Proof

Let $TM1$ be a Turing machine for language $L$.

We can create an enumerator $E$ for $L$ as follows:

• Repeat the following for $i = 1, 2, 3, \dots$

• Run $TM1$ on $S_i$

• If accepted, print out $S_i$

Other than the proof being incomplete by not showing an Turing state machine, I cannot think of any flaws in the proof. I would appreciate any help with this problem as I have spent hours on it and don't seem to be making any progress.

I'm assuming "Turing recognizable" means the same thing as semi-decidable. This is equivalent to being recursively enumerable, but the given proof doesn't work because for some $i$ the step "run $M$ on $s_i$" may never complete, in which case the program will never even consider $s_{i+1}$. To get around this problem you will need to "dovetail" many computations simultaneously. That is, while you are still running $M$ on $s_i$, proceed to run it on $s_{i+1}$, $s_{i+2}$, etc. in case it never halts on $s_i$. You can do this in such a way that at any step you are only running $M$ on a finite number of $s_i$.
More precisely, first run $M$ for one step on $s_0$. Then do the next step for $s_0$ and the first step for $s_1$. Then do the third step for $s_0$, the second step for $s_1$, and the first step for $s_2$, and so forth. Or you can pick your favorite bijection $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ and use that instead. The important thing is that we must begin the computation for $s_{i+1}$ before we have finished the computation for $s_i$, but still come back to the $s_i$ computation infinitely many times.