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.

I have a problem with this task:

Show that this language is recursive enumerable, but not recursive: $L = \{ w \in \{0,1\}^* | M_w(x)\; \text{converges for some input}\; x \}$ (where $M$ is turing machine).

I know how to do it with this one: $L = \{ w\in \{0,1\}^* | w \in L(M)\;\text{for some TM $M$} \} \to$ complement of $L$ is diagonalization, so it is not accepted by any TM, so complement of $L$ is not recursively enumerable and so $L$ is not recursive.

Is there any similar approach for original task, please? Or do you have idea how to proceed?

share|improve this question
    
For some basic information about writing math at this site see e.g. here, here, here and here. –  Julian Kuelshammer Nov 6 '12 at 8:45
    
I tried to improve your post using TeX (for better readability). Please check whether these edits did not unintentionally change the meaning of your post. –  Julian Kuelshammer Nov 6 '12 at 8:48
    
it's ok, thanks ... sorry about that, my first post ... –  kolage Nov 6 '12 at 8:52
    
I know, no worries. Welcome to math.SE. –  Julian Kuelshammer Nov 6 '12 at 8:54
    
Am I right in guessing that $M_w$ is used to denote some enumeration of all Turing machines, as $w$ varies? Also, what is the meaning of convergence here? –  Harald Hanche-Olsen Nov 6 '12 at 9:17

1 Answer 1

up vote 1 down vote accepted

Say your $L$ was recursive. Then it's complement would also be recursive, i.e. the problem of whether some $M_w$ diverges for all inputs would be decidable.

Now, say you have a turing machine $M'$ and some input $x'$. You can then find some turing machine $M$ which first writes $x'$ to the tape (overwriting the previous input), and then continues as $M'$ would. $M$ diverges for all inputs exactly if $M'$ diverges for input $x'$. Thus, if you can decide whether or not a arbitrary turing machine $M$ diverges for all inputs, you can also decide whether an arbitrary machine terminates for some arbitrary input. Which you know that you cannot, since this is the halting problem. $L$ is thus not recursive.

$L$ is recursively enumerable, though, because you can simply interate over all triples $(M_w,x,n)$ (diagonally!) and check whether $M_x(x)$ converges after $n$ steps. If $w \in L$, you'll eventually reach the input $x$ for which it converges and some $n$ which is at least as large as the number of steps it takes for $M_w(x)$ to converge, thus discovering that $w \in L$.

share|improve this answer
    
Hey, thanks for very nice explanation! I think I get it now :) –  kolage Nov 6 '12 at 9:49

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.