Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Where is the flaw in the following proof, that if a language is Turing recognizable then we can enumerate it?


Let $TM1$ be a Turing machine for language $L$.

We can create an enumerator $E$ for $L$ as follows:

  • Repeat the following for $i = 1, 2, 3, \dots$

  • Run $TM1$ on $S_i$

  • If accepted, print out $S_i$

Other than the proof being incomplete by not showing an Turing state machine, I cannot think of any flaws in the proof. I would appreciate any help with this problem as I have spent hours on it and don't seem to be making any progress.

Many thanks in advance!

share|cite|improve this question
up vote 2 down vote accepted

I'm assuming "Turing recognizable" means the same thing as semi-decidable. This is equivalent to being recursively enumerable, but the given proof doesn't work because for some $i$ the step "run $M$ on $s_i$" may never complete, in which case the program will never even consider $s_{i+1}$. To get around this problem you will need to "dovetail" many computations simultaneously. That is, while you are still running $M$ on $s_i$, proceed to run it on $s_{i+1}$, $s_{i+2}$, etc. in case it never halts on $s_i$. You can do this in such a way that at any step you are only running $M$ on a finite number of $s_i$.

More precisely, first run $M$ for one step on $s_0$. Then do the next step for $s_0$ and the first step for $s_1$. Then do the third step for $s_0$, the second step for $s_1$, and the first step for $s_2$, and so forth. Or you can pick your favorite bijection $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$ and use that instead. The important thing is that we must begin the computation for $s_{i+1}$ before we have finished the computation for $s_i$, but still come back to the $s_i$ computation infinitely many times.

share|cite|improve this answer
thank you for the reply! What do you mean by "dovetail" ? – Epsilon Feb 19 '13 at 0:28
@Epsilon Sure. I hope my edit makes it clearer. – Trevor Wilson Feb 19 '13 at 0:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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