A_TM 的不可判定性（undecidability of A_TM）

這就是那塊拱心石定理：A_TM =（(M, w)：M 接受 w）是不可判定的。沒有任何圖靈機能總是停機並正確告訴你「給定的機器是否接受給定的輸入」。我們已經見過通用機 U，它透過模擬來識別 A_TM；新的、更深的論斷是沒有任何機器能「判定」它，也就是總能以正確的「是」或「否」結束。證明就是把對角線自我指涉論證直接套用到 A_TM 上。

為了反證，假設存在某個判定器 H，它總會停機並正確回答「M 是否接受 w」。造一台機器 D，它接收一個機器描述 M，在 (M, M) 上執行 H，然後把結果反轉：若 H 說 M 接受 M，則 D 拒絕（或迴圈）；若 H 說 M 不接受 M，則 D 接受。現在在 D 自己的描述上執行 D。若 D 接受 D，那 H 必定在 M = D 時說了「M 不接受 M」，意即 D 不接受 D——矛盾。若 D 不接受 D，那 H 必定說了「M 接受 M」，意即 D 接受 D——矛盾。那個被假設的判定器 H 不可能存在。

這為什麼如此重要？A_TM 是日後幾乎所有不可判定性結果生長的種子，通常透過歸約：要證明某個新問題 B 不可判定，你就證明「B 的判定器能被改造成 A_TM 的判定器」，而我們已知後者不可能。因此 A_TM（以及等價的停機問題）的不可判定性是可計算性的基岩——第一道硬牆，其餘每個不可能性定理都倚著它。