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?


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.

  • $\begingroup$ So does the machine continues simulating $s_i$ at next $(i + 1)^{th}$ step by running the machine just one more step if $s_i$ did not halt on the previous $i$ steps? $\endgroup$
    – AABBCC
    Dec 12 '19 at 4:09
  • 1
    $\begingroup$ @AABBCC Correct. $\endgroup$ Dec 13 '19 at 17:07

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


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.