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

I am not sure about this. This is my try :

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 :)

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

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.