Rice 定理（Rice's theorem）

一旦你知道停機問題不可判定，你也許會盼望它只是個孤立的怪胎，而大多數關於程式的有用問題仍可回答。Rice 定理一筆橫掃就摧毀了這個盼望。它說：程式所識別之「語言」的任何「非平凡」性質都是不可判定的。「這個程式識別的是空語言嗎？」「它接受字串 hello 嗎？」「它的語言有限嗎？」「它的語言是正規的嗎？」每一個都不可判定。幾乎每個關於程式的有趣語意問題都被排除在外。

讓我們小心陳述，以免過度宣稱。考慮語言的一個性質 P——一個關於字串集合的是非問句，例如「這個集合是空的嗎？」。若有某個可識別語言具有 P、又有某個可識別語言不具有 P（也就是 P 既非永遠為是、也非永遠為否），則稱 P 是非平凡的。Rice 定理說：對於可識別語言的任何非平凡性質 P，問題「給定機器 M，語言 L(M) 是否具有性質 P？」都是不可判定的。證明是從 A_TM 做歸約：若你能判定性質 P，你就能設計一台機器，使它的語言恰好在某給定 (M, w) 屬於 A_TM 時具有 P，於是判定了 A_TM——而那是不可能的。

兩條界線讓定理保持誠實。第一，性質必須是關於機器所識別的「語言」，而非機器的「文字」——「M 恰好有 7 個狀態嗎？」或「M 的程式碼裡含有字母 q 嗎？」都是可判定的，因為你只要讀程式碼。第二，性質必須非平凡；恆真性質（「L(M) 是某個可識別語言」）與恆假性質都顯然可判定。在這兩道護欄之內，Rice 定理寬廣得令人屏息：沒有一般演算法能判定一個程式的行為究竟是什麼。