# 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
{"ft_lang_label":"__label__en","ft_lang_prob":0.8864577,"math_prob":0.9910564,"size":284,"snap":"2021-04-2021-17","text_gpt3_token_len":85,"char_repetition_ratio":0.11785714,"word_repetition_ratio":0.0,"special_character_ratio":0.28873238,"punctuation_ratio":0.10526316,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9993805,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-04-20T20:12:44Z\",\"WARC-Record-ID\":\"<urn:uuid:76565a81-5d82-4abf-91a3-e1aba21ea85c>\",\"Content-Length\":\"158980\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:0180dbee-535f-4062-a116-b170facb4bfb>\",\"WARC-Concurrent-To\":\"<urn:uuid:f9aa2bdf-f7d8-4600-9177-100ee244e124>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://cs.stackexchange.com/questions/131269/how-would-i-prove-that-nondeterministic-turing-machines-are-undecidable\",\"WARC-Payload-Digest\":\"sha1:64SAV2ZFS4IHRYC7CSQDWZDEF7RRIJWG\",\"WARC-Block-Digest\":\"sha1:DKA4HS7C5UFJHAK7AFK2SFNNUN47ESB6\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-17/CC-MAIN-2021-17_segments_1618039490226.78_warc_CC-MAIN-20210420183658-20210420213658-00236.warc.gz\"}"}