A_TM 的補集（complement of A_TM）

A_TM 的補集，寫成 co-A_TM，是所有「M 不接受 w」的 (M, w) 對之集合——要嘛 M 拒絕，要嘛 M 永遠迴圈而從不接受。它是 A_TM 的完全相反名單，由把每個「是」翻成「否」而成。研究它能把抽象的「可判定／可識別／共可識別」圖像化為具體之物：co-A_TM 是教科書級「連可識別都做不到」的語言範例。

論證簡短又漂亮。有一條定理說：語言 L 可判定，若且唯若 L 與它的補集「都」是圖靈可識別的。我們已知 A_TM 可識別（每當 M 接受時通用機就接受）但不可判定（對角線證明）。現在為了反證，假設 co-A_TM 也可識別。那麼 A_TM 與 co-A_TM 就都可識別，這條定理便會使 A_TM 變成可判定——與我們剛證明的矛盾。因此 co-A_TM 不可識別。

對「為什麼確認 co-A_TM 成員資格毫無希望」有個令人滿意的直覺。要接受 co-A_TM 中的一對 (M, w)，你得確認 M 永遠不接受 w，但「永遠」正是麻煩：在任何有限時刻 M 都可能還在跑，而且下一步就可能接受。你可以靠「等夠久看到它」來確認接受，卻永遠無法靠「等待」來確認「永久不接受」，因為沒有任何有限的等待能排除未來的某次接受。這個不對稱正是 A_TM 可識別而 co-A_TM 不可識別的原因。