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?
 A: 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$.
