Turing machine which diverges on its own code

Question

Show that the set $K^{c}$ = $\lbrace M \mid M(M) \text{ diverges} \rbrace$ is not recursively enumerable.

This question is essentially asking to show that the set of turing machines which diverge when run on their own code is not RE.

My idea is to attempt to reduce this problem to something which is the complement of the halting problem. Thus, the idea is to take a machine M and a word w, and construct a new machine which diverges on it's own code when M diverges on w, but haven't had much luck with that.

This is from a practise exam, but please treat it as a homework question so I can attempt to work through a solution.

Answer 1

The language $K^c$ is clearly co-RE: given an input $M$, simulate $M(M)$ until it halts and then reject; if it doesn't halt, the simulation doesn't halt. Now, any language that is both recursively enumerable and co-RE is actually recursive (exercise: prove this). Since $K^c$ is not recursive (exercise: prove this), it cannot be recursively enumerable, either.

Your idea of reducing to the complement of the halting problem doesn't work. Firstly, that's the wrong way around: you'd want to reduce the complement of the halting problem to $K^c$ to prove that $K^c$ is hard. Second, it's possible for a set to be neither RE nor co-RE. (Why? There are countably many RE languages and countably many co-RE languages, since each such set corresponds to a Turing machine and there are only countably many Turing machines. But there are uncountably many languages over any finite alphabet.) However, from your description, it sounds like you weren't trying to do a reduction but a diagonalization, similar to the proof of the undecidability of the halting problem. That sounds like it could work but the method I give above is much easier.

Answer 2

One way I can think to prove this is to consider a turing machine $N$ deciding $K^c$, and construct another tm $M$ such that in the input $\left < R \right >$ runs $N(\left < R\right >)$ and does the opposite of what $N$ responds. You should be able to get a contradiction when $M$ runs on its own input.

Another way would be to, given a input $\left < M,w \right >$ for the halting problem, construct a tm that ignores its input and runs $M(w)$. This tm behaves the same way independtly of its input, so in particular it halts in its own code iff $M$ halts on $w$.