0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Steven Oct 16 at 8:27
  • $\begingroup$ @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}$? $\endgroup$ – Gareth Bradshaw Oct 16 at 14:54
  • $\begingroup$ Every deterministic Turing machine is also a (special) non-deterministic Turing machine. Therefore $A_{TM} \subset A_{NTM}$. $\endgroup$ – Steven Oct 16 at 18:23

Your Answer

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

Browse other questions tagged or ask your own question.