# Showing the language of TMs that halt on a decidable set of words is not in RE

I need to show that the following language, L = {$$\langle M \rangle$$ | The set of words which M halts on is decidable}, is not recursively enumerable. In the instructions they advise thinking of a reduction that is similar to the one used in the proof for Rice's Theorem in Sipser's 3rd edition (page 243). I couldn't think of a proper proof by myself. I assume L $$\notin RE\cup CO-RE$$ so there's no point in trying to prove $$\bar{L}$$ is in RE to show L is not in RE. Can anyone help?

Here is a reduction from coHALT (given a Turing machine, determine whether it doesn't halt on the empty input) to $$L$$. Given a Turing machine $$M$$, construct a new Turing machine $$M'$$ which acts as follows:

• Run $$M$$ on the empty input.
• If $$M$$ halts, interpret the input as a Turing machine and run in on the empty input.

If $$M$$ doesn't halt on the empty input, then the set of words on which $$M'$$ halts is the empty set, which is decidable, and so $$M' \in L$$. If $$M$$ does halt on the empty input, then the set of inputs on which $$M'$$ halts is HALT, which is not decidable, and so $$M' \notin L$$.