[Math] Language that is recursively enumerable, but not recursive

automatacomputabilityturing-machines

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?

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

Related Question