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.
2 Answers
Maybe try to use Rice' theorem, instead of reducing from $\overline{A_{TM}}$.
-
$\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éonJun 14, 2021 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, 2021 at 15:22
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.