1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I want to prove that L is undecidable, for this I want to reduce Atm . $\endgroup$ – Frank Jul 25 '20 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 Jul 26 '20 at 23:02
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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