# How would I prove that nondeterministic Turing machines are undecidable?

How would I go about proving that the language:

$$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$

is undecidable?

I looked at the proof for $$A_{TM}$$ being undecidable, but am struggling to figure out how to prove the above. Any ideas?

• I assume $A_{TM}$ is the language of all Turing Machine-input pars $\langle T, w \rangle$. In that case it suffices to observe that the decidability of $A_{NTM}$ would imply the decidability of $A_{TM}$. Taking contrapositive of the implication (and noticing, as you point out, that $A_{TM}$ is undecidable) shows that $A_{NTM}$ is also undecidable. – Steven Oct 16 '20 at 8:27
• @Steven Thanks! I suppose that I'm still confused about this part of your comment: "In that case it suffices to observe that the decidability of $A_{NTM}$ would imply the decidability of $A_{TM}$." How does the decidability of $A_{NTM}$ imply the decidability of $A_{TM}$? – Gareth Bradshaw Oct 16 '20 at 14:54
• Every deterministic Turing machine is also a (special) non-deterministic Turing machine. Therefore $A_{TM} \subset A_{NTM}$. – Steven Oct 16 '20 at 18:23