圖靈機的空集與等價問題（emptiness and equivalence problems）

在「這台機器是否接受這個輸入」之外，還有關於機器整體行為的更大問題：它到底是否接受任何輸入（空集）、兩台機器是否接受完全相同的輸入集（等價）、它接受的集合是否為正規語言（正規性）、它是否對每個輸入都停機（全域性）？每一個聽起來都像是夠聰明的分析器應該能解決的事。每一個其實都不可判定，而我們之所以知道，靠的就是歸約。

以空集為例，E_TM = {M : M 不接受任何字串}。要證明它不可判定，就把 A_TM 歸約到它。給定 (M, w)，造一台新機器 M_w，它忽略自己的輸入，模擬 M 在固定字串 w 上的執行，並只在 M 接受 w 時才接受。於是 M_w 至少接受一個字串（其實是接受每個字串）恰好發生在 M 接受 w 時，而 M_w 什麼都不接受恰好發生在 M 不接受 w 時。所以對 M_w 套用空集判定器，就會告訴我們 M 是否接受 w，判定了 A_TM，這是不可能的。等價 EQ_TM = {(M1, M2) : 它們接受相同語言} 甚至更簡單：拿任何 M 去和一台什麼都不接受的固定機器 M_reject 比較；那麼 M 等價於 M_reject 若且唯若 M 什麼都不接受，於是空集歸約到等價，等價也不可判定。

正規性（被識別的語言是否正規？）與全域性（機器是否對所有輸入停機？）以同樣方式倒下，而 Rice 定理把空集、正規性與「等價於某固定機器」打包成一個橫掃的結果：圖靈機所識別之語言的每一個非平凡性質都不可判定。誠實的界線是：這些是機器所「識別之語言」的性質，不是其原始碼的性質。問 M 是否恰好有 7 個狀態、或其紙帶字母表是否含某符號，是語法性質，完全可判定。只有當你問及「行為」——最終被接受的輸入集合——時，不可判定性才咬人。