# Undecidability of TMs recognizing a decidable language

The language $$L = \{ \text{M} \mid \text{M is a TM and the set of words w such that M halts on w is decidable} \}$$ is given.

I need to prove that $$L$$ is NOT Turing recognizable. I've got a hint: it should be similar to prove to the Rice Theorem, using a reduction. However, this hint isn't very helpful to me.

• Can you add a bit more details to the questions? Is there a specific issue that you're having in trying to complete a proof? Probably nobody will be very happy to solve your exercises... – Steven Nov 6 '19 at 16:02
• currently, I am unable to find/think of any solution .... the only hint i've got is that the reduction should be something like rice proof. – Roy Padina Nov 7 '19 at 17:22

## 1 Answer

Given a machine $$A$$, construct a machine $$M$$ which on input $$x$$, acts as follows: run $$A$$ on the empty input, and if it ever halts, run the Turing machine encoded by $$x$$ on the empty input.

If $$A$$ halts on the empty input then the language $$M$$ recognizes is the halting language, while if $$A$$ doesn't halt on the empty input then the language $$M$$ recognizes is the empty language.

• i don't see how this solves or proves the question ... – Roy Padina Nov 9 '19 at 14:06