# Language that is recursively enumerable, but not recursive

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?

-
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

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

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