Question

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."

Was it helpful?

Solution

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.

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top