Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

Proof

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|improve this question
add comment

1 Answer

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|improve this answer
    
thank you for the reply! What do you mean by "dovetail" ? –  Epsilon Feb 19 '13 at 0:28
2  
@Epsilon Sure. I hope my edit makes it clearer. –  Trevor Wilson Feb 19 '13 at 0:34
add comment

Your Answer

 
discard

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.