不可判定性與停機問題
語言的性質,而非機器的性質(property of the language, not the machine)
這是 Rice 定理的細則,弄錯它會讓人嚴重過度宣稱。這個區分是在「程式做什麼」與「程式怎麼寫」之間。語言的性質(語意性質)問的是程式接受的輸入集合——它的行為。機器的性質(語法性質)問的是程式的原始文字——它的結構。Rice 定理判定第一類不可判定;它對第二類隻字未提,而第二類中許多是完全可判定的。
想像兩個程式計算的東西一模一樣,寫法卻全然不同——一個十行、一個一千行,也許風格各異。它們識別「同一個」語言,所以共享一切語意性質:相同的接受字串、相同的空性、相同的有限性。但它們在語法性質上不同:不同的行數、不同的變數名、不同的狀態數。Rice 定理講的是這兩個程式所「共享」的東西(它們共同的語言),而非區分它們文字的東西。「L(M) 含有 hello 嗎?」是語意的、不可判定;「M 恰有 7 個狀態嗎?」或「M 的原始碼含有 goto 嗎?」是語法的,只要檢視程式碼就可判定。
其實用結論能讓你避開一個常見錯誤。有人有時會「反駁」Rice 定理,指出 linter 能偵測例如無法到達的程式碼、或某函數是否有三個參數——但那些是關於文字的語法事實,完全可判定,也從未被宣稱不可判定。Rice 定理只有在你的問題真的是關於「行為」時才咬人:程式產生什麼輸出、接受什麼輸入、兩個程式行為是否一致。語法與語意之間的界線,正是可判定與不可判定分道揚鑣之處。
語意(不可判定):「M 會接受任何偶數長度的字串嗎?」語法(可判定):「M 的轉移表有超過 5 列嗎?」前者是關於行為;後者讀一讀轉移表就能解決。
Rice 定理擊中語意(行為)性質;語法(文字)性質可以保持可判定。
兩台程式碼相同的機器顯然識別同一語言,但兩台程式碼完全不同的機器也可能如此。Rice 定理只談那個共享的語言。
又称
另见