1
$\begingroup$

So I want to prove that $$ \big\{\langle M \rangle : \text{ M is a TM and } L(M) \text{ is decidable} \big\}$$ is undecidable.
To do so I want to reduce it from$\ \overline{A_{TM}}$ with a function which looks like this :
On input $\langle M,w \rangle$ run $M$ on $w$, if $M$ accepts $w$ output $M'$ where $M'$ should be a TM for an undecidable language.
Furthermore the function loops if $M$ does not accept $w$ such that if $M$ reject $w$, $M'$ loops on every input.
Hence if $\langle M,w \rangle \in \overline{A_{TM}}$, $M$ rejects $w$ and $L(M') = \emptyset$ which is decidable.
My problem is when $\langle M,w \rangle \in A_{TM}$ and I want to output a TM $M'$ such that $L(M')$ is undecidable but I don't know how to create such a TM.

$\endgroup$
1
$\begingroup$

Maybe try to use Rice' theorem, instead of reducing from $\overline{A_{TM}}$.

$\endgroup$
2
  • $\begingroup$ This is indeed what I saw when I looked online but I haven't seen this theorem in class so I would like to not have to use it here if possible ! $\endgroup$
    – Léon
    Jun 14 at 12:35
  • $\begingroup$ @Léon You can always pretty much imitate (one of) the proof(s) of Rice's theorem, by swapping in your particular non-trivial property. I just found a nice reference with several different proofs of Rice's theorem: dcc.fc.up.pt/~acm/ricep.pdf $\endgroup$ Jun 14 at 15:22
1
$\begingroup$

I finally understood what was blocking me.
We only need a TM that recognizes an undecidable language so we just have to take a TM $M'$ that recognizes $A_{TM}$ for example and return it when $M$ accepts $w$.
We have $L(M') = A_{TM}$ which is undecidable.

$\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.