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 &quot;only if&quot; 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 &quot;Only if&quot; part for the theorem &quot;A language is Turing-recognizable iff some enumerator enumerates it.&quot;
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.