# Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it."

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.

• 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? Dec 12, 2019 at 4:09
• @AABBCC Correct. Dec 13, 2019 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).