1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Oooh I see, thank you very much! $\endgroup$ – davideleo Sep 17 '20 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.