# Proof that languages are Turing-recognizable iff computably-enumerable

A very small question on this proof, which I found as Theorem 3.21 in Sipser's, and in my lecture notes.

In the "only if" direction, we assume that a Turing machine $$M$$ recognizes some language $$L$$. We list all the strings in the input alphabet (in lexicographic order, say) as $$s_1,s_2,s_3,\dots$$

We then construct an enumerator $$E$$ that for each $$i=1,2,3,\dots$$ simply runs $$M$$ for $$i$$ steps on each input $$s_1,s_2,s_3,\dots, s_i$$; then it prints any $$s_j$$ which is accepted by $$M$$. $$E$$ is what we need.

Now, since I know that strings are finite, why should I run $$M$$ for $$i$$ steps on the first $$i$$ strings, when I could just run it on the $$i$$-th string? It feels like an unnecessary complication.

P.S. Another question was asked about this, but it addressed a different doubt: Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it."

If you run $$M$$ on the $$i$$-th string then it might never halt, so your algorithm will be stuck. The idea is that if $$M$$ does halt on the $$i$$-th string, say after $$j$$ steps, then we will see it once we get to the $$\max(i,j)$$-th string.