# How to prove the language of all Turing Machines that accept an undecidable language is undecidable?

I want to prove that $$L=\{\langle M \rangle |L(M)\text{ is undecidable}\}$$ is undecidable

Suppose L is decidable. Let $$E$$ be the decider from $$L$$. Let $$A$$ be a TM which is recognizing $$A_{TM}$$. Let $$S$$ be a TM which works on input $$\langle M,w \rangle$$ in the following way(the goal is that $$S$$ will be a decider for $$A_{TM}$$):

1. Construct a TM $$N$$ which works on Input $$x$$ as follows: Run $$M$$ on $$w$$. If $$M$$ $$accepts$$ run $$A$$ on $$x$$ and accept $$x$$ if $$A$$ accepts.(In this case is $$L(N)=A_{TM}$$). If $$M$$ $$rejects$$ $$w$$, $$accept$$ $$x$$.(In this case is $$L(N)=\Sigma^*$$)
2. Run $$E$$ on $$N$$ and accept if N accepts. Otherwise reject

I am not sure if my reduction is the right way or not. Maybe someone can help to finish the reduction :)

• I want to prove that L is undecidable, for this I want to reduce Atm . Jul 25 '20 at 18:01
• The language of turing machines that accept undecidable languages is empty and therefore decidable by the Turing machine that never accepts.
– Jake
Jul 26 '20 at 23:02

I think you are on the right track but things need to be made more explicit. First, what machine exactly is $$A$$? Any machine? Where does your contradiction appear?
First, you need to explicitly say that $$A$$ is a machine for an undecidable language, for example, let $$A$$ be the universal machine, that on inputs $$\langle M \rangle w$$ simulates $$M$$ on $$w$$, and accepts if $$M$$ accepts $$w$$.
Then, say explicitly that $$S$$ is a decider (a machine that always halts), and include the simple extra steps that show that $$S$$ accepts $$\langle M \rangle w$$ if and only if $$w \in L(M)$$. Finally, recall that $$S$$ is then a decider for a problem we already know is undecidable; a contradiction.
Edit: Sorry, it seems that $$A_{TM}$$ is standard notation for the universal machine. Forget about that comment if that is the notation used in your context.