Question for “Only if” part for the theorem “A language is Turing-recognizable iff some enumerator enumerates it.”

Question

I am trying to prove the theorem

A language is Turing-recognizable iff some enumerator enumerates it.

I proved the "if" part, but I have no idea of proving the "only if" part, so I searched a proof for the "only if" part of this theorem. In the proof that I found, it says

Let $\sum$ be the alphabet of the Turing machine $M$, and let $s_1$, $s_2$, ... be a list of all possible strings of $\sum^{*}$. We define the enumerator $E$ as follows:
1. Run $M$ for $i$ steps on each input $s_1$, $s_2$, ... , $s_i$.
2. If any computation of $M$ accepts, print out the accepted string.

In this proof, I can't understand why do we need to run $M$ for only $i$ steps. I think the number of simulation steps may not be enough to simulate strings. Is it guaranteed that simulating $M$ finishes in $i$ steps?

Answer 1

In slightly more detail, what's happening is:

1. Run the machine on input $s_1$ for one step. If it accepts, list the string.
2. If the machine didn't halt on the previous step, run the machine on $s_1$ for one more step and then on $s_2$ for a step. As before, if the machine accepts either string, list them and remove them from consideration.
3. Do the same thing on $s_1, s_2, s_3$.
4. Continue forever.

This process, called dovetailing, will eventually list all and only those inputs which the TM will accept.

Answer 2

A language is Turing-recognizable (or Recursively enumerable) iff there exists a Turing Machine which will enumerate all valid strings of the language.

What you probably miss in the above proof is the fact that $i$ can take any value ... when we say $i$ steps, we can mean $10$, $100$, $100000$, $\infty$ steps. Basically $i$ is an index that indicates the number of words in the language; the enumerator $E$ could very well run forever (if the language has an infinite number of strings).