動機
關於程式的許多問題問的是它接受哪些輸入,而不是它的程式碼如何撰寫。它是否接受某個字串?它的語言是否有限?它的語言是否正則?這些問題看似各不相同,但同一個歸約即可證明:所識別語言的每一個非平凡性質都是不可判定的。
關鍵在於構造這樣一部機器:視乎某個特定計算是否停機,它要麼識別一個選定的參照語言,要麼甚麼也不識別。新機器無須知道究竟屬於哪種情況,它只需在收到輸入時模擬該計算。一個假設存在的性質判定器可以區分這兩種情況,從而判定停機問題。
定義
定義 5.3.1
(可識別語言)
固定一個至少含兩個符號的有限字母表 ,指定其中兩個不同的符號分別記作 和 ,並固定一種對確定型圖靈機(Turing machine)的有效編碼,機器的輸入為 上的字。對機器 ,令 為 最終接受的字的集合。對其他字,機器可以拒絕,也可以永不停機。若一個語言等於某部這類機器的 ,則稱該語言是可識別的。
定義 5.3.2
(語言的性質與非平凡性)
性質 是 上若干可識別語言所構成的一個集合。若存在某個可識別語言屬於它,同時又存在某個可識別語言不屬於它,則稱該性質是非平凡的。相應的判定問題是:給定編碼後的機器 ,問 是否成立。我們假設採用標準編碼,其語法合法性檢查是可判定的,格式有誤的編碼可以直接拒絕。一般有效機器編碼的具體選擇不會改變歸約論證。
定理
定理 5.3.3
(萊斯定理)
可識別語言的每一個非平凡性質都是不可判定的:不存在這樣的判定器,能對每一部機器 正確地判定 是否具有該性質。
定理 5.3.4
(歸約中使用的停機問題)
不存在這樣的判定器:給定編碼後的確定型圖靈機 和輸入 ,判定 在 上是否停機。
第二個定理是可計算性配套章節中已經確立的標準停機不可判定性結果。「停機」既包括接受,也包括拒絕。萊斯(Rice)定理中的性質只涉及所接受的語言:即使兩部機器的運行時間和拒絕行為不同,只要它們接受同一個集合,就必須得到相同的答案。
證明
空語言不屬於該性質時的歸約
證明
(停機問題歸約到非平凡性質)
先假設 。由非平凡性,存在可識別語言 ,並固定一部識別 的機器 。給定一個停機問題的實例 ,有效地構造一部機器 ,它在任意輸入 上按以下方式運行:
- 在固定的字 上模擬 。
- 若該模擬停機,則在 上運行 ,並且恰在 接受時接受。
若 在 上永不停機,則對每個 ,第一步都會永遠運行下去,因此 。若 確實停機,則有限步的第一步之後是對 的模擬,因此 。無論 接受還是拒絕 ,這一點都成立;決定分支的只是是否停機。
映射 是可計算的:機器的描述可以包含 和 的有限編碼,以及兩次模擬的指令。該構造並不嘗試判定第一次模擬是否會停機。假設存在 的判定器,那麼它對 回答「是」,當且僅當 在 上停機,這與停機問題的不可判定性矛盾。
證明透視
萊斯定理的假設在何處被用到
非平凡性被用到兩次:它提供了固定的可識別語言 ,其機器 被嵌入 ;在其餘情況中,它又保證互補性質仍是非平凡的。假設 使二分成立:構造只可能產生 或 ,其中恰有一個屬於 ,因此判定器對 的回答就報告了 是否停機。語義不變性在把判定器應用於 時被用到:回答只依賴於 ,而與程式碼如何撰寫無關。不明顯的一步是: 只是等待 ,而不是檢驗 是否停機,所以映射 是可計算的,儘管要辨認它所產生的語言是不可能的。論證以反證法收尾: 的判定器與這個可計算映射複合,就會判定停機問題。
其餘情況
證明
(取互補性質處理其餘情況)
若 ,考慮可識別語言類內的互補性質 :它恰好包含那些不屬於 的可識別語言。它仍然是非平凡的,並且不含 。由前面的論證,它的判定問題是不可判定的。如果 是可判定的,把「是」與「否」的回答互換,就能判定 ,矛盾。證明完畢。
常見錯誤
(性質的補集不是語言的補集)
這裏的補集是語言性質的補集,而不是每個語言自身的補集。我們並不是斷言每個可識別語言的補集都是可識別的。一個假設的判定器對每個機器編碼返回一個布爾值,因此互換該答案就判定了互補性質,即使語言補運算本身可能相當困難。
例題詳解
例題 5.3.5
(「包含 0」這一性質的構造)
設 為含有字 的可識別語言所成的性質。於是 ,語言 屬於 ,而 可以取為恰好接受輸入 的機器。對實例 ,機器 先在 上模擬 ,然後在自己的輸入上運行 。若 在 上停機(即使是以拒絕方式停機),模擬就會結束,所以 。若 在 上永遠運行,則 永遠到不了 ,。因此「包含 」的判定器將能判定停機問題。拒絕的情形是邊界情形:決定分支的是停機,而不是接受。
例題 5.3.6
(有限性:其餘情況的例子)
設 為有限的可識別語言所成的性質,所以 ,上面的構造不能直接套用。互補性質 由無限的可識別語言組成:,而 。取 ,並令 接受每個字。於是若 在 上停機,;否則 。所以 無限,當且僅當 在 上停機。有限性的判定器把答案互換之後,就能判定停機問題。
例題 5.3.7
(空性)
性質 是非平凡的:空語言是可識別的,而 是另一個不同的可識別語言。萊斯定理表明,判定 是否成立是不可能的。它的互補性質,即非空性,同樣是不可判定的,儘管非空性是可識別的:可以對所有輸入交錯模擬,並在某次運行接受時接受。
例題 5.3.8
(有限性)
「 是有限的」是一個非平凡的語義性質。空語言是有限且可識別的,而 是無限的,並且由於字母表非空而可識別。因此,沒有判定器能夠僅從任意識別器的程式碼判定其語言是否有限。一部描述中只含有限多個狀態的機器仍可能接受無限語言;程式碼的大小與語言的大小是不同的概念。
例題 5.3.9
(所識別語言的正則性)
空語言是正則且可識別的。語言 是可識別的,但由正則語言一章中的泵引理論證可知它不是正則的。因此,正則性是可識別語言的一個非平凡性質,對任意圖靈機描述而言是不可判定的。這與對已保證輸入為 DFA 的情況所存在的與正則性相關的高效算法並不矛盾。
例題 5.3.10
(語法問題則不同)
「編碼的機器是否恰好有三個狀態?」可以透過解析一個合法的有限描述並數出狀態個數來回答。它不是語言的語義性質:接受同一語言的兩部機器,其不可達或冗餘狀態的數目可以不同。萊斯定理不適用於這個語法問題。
常見錯誤
定理說了甚麼,沒說甚麼
輸入類很重要。萊斯定理針對的是任意編碼的識別器,包括可能永遠運行的機器。如果輸入限制在帶有更強保證的表示上,某個具體性質可能是可判定的。例如,DFA 的空性可以透過圖的可達性來判定,儘管任意圖靈可識別語言的空性是不可判定的。
性質必須只依賴於 。某部機器在固定輸入上是否於固定步數內停機,可以透過有界模擬來判定,但接受同一語言的兩部機器在這一點上可以不同。它不是萊斯定理的反例,因為它並不是只關於所接受語言的性質。
常見錯誤
(不可判定不等於不可識別)
該定理證明的是不可判定性,並不自動意味著兩種回答都不可識別。語言非空的機器編碼集合是可識別的:枚舉輸入字,交錯執行機器計算的有限前綴,並在某次計算接受時立即接受。然而它仍是不可判定的。要確定另一個性質的「是」一側或「否」一側是否可識別,需要另行論證。
反例模式
並非關於機器的每個非平凡問題都不可判定
對萊斯定理一個誘人的過度解讀是:關於編碼機器的每個非平凡是非問題都不可判定。考慮「機器是否恰好有三個狀態?」它是非平凡的,因為有些機器恰有三個狀態而有些不是;但它是可判定的:解析有限描述並數出狀態即可。具體地,設 恰有三個狀態,且沒有任何轉移進入接受狀態,所以 ;設 是在 上多加一個不可達狀態所得的機器,所以 亦然。對 的答案是「是」,對 是「否」,儘管它們接受同一個語言。因此這個問題並不只是所接受語言的性質,而這恰好是萊斯定理所需的假設。
留意歸約的方向
常見錯誤
(把歸約方向弄反)
歸約從已知不可判定的停機問題的任意實例出發,把它轉化為性質問題的一個實例。若性質判定器存在,把構造出的實例交給它,就能解決原來的停機問題。這個方向至關重要:若把性質問題歸約到停機問題,只能說明假設的停機預言機如何幫助解決性質問題,並不能說明性質判定器能解決停機問題。
該構造還使用了固定的參照識別器,而不是固定的參照輸入。當被模擬的停機實例停止後,新機器必須對其所得到的任意輸入 重現 的行為。對每個這樣的 ,最初的模擬所需步數是有限的,並且與 在 上最終是接受、拒絕還是永不停機無關。因此,被接受的輸入集合恰好是 ,而不僅僅是 的子集。
當停機模擬不停止時,新機器在每個輸入上都永遠運行。對識別器而言,這種行為是容許的。若證明要求構造出的機器在每個輸入上都停機,則需要額外的論證,不能簡單地沿用這種等待式構造。本定理所涉及的是不受限制的圖靈機識別器,這一區別說明了為何輸入類的假設是實質性的。
對於非空性,交錯模擬可以明確寫出。把所有有限輸入字枚舉為 。在第 階段,對 各自運行該機器 步,格局可以重新開始,也可以保留,視乎方便而定。若任何一次運行接受,就接受該機器編碼。對任何固定的輸入及其模擬的任何固定有限步數,最終都會被到達。若沒有任何輸入被接受,該過程就永遠運行,這對識別而言是容許的,但對判定程序則不容許。
理解非平凡性
非平凡性是相對於固定字母表上的可識別語言而言的。對每個可識別語言都成立的性質,總回答「是」即可判定;對任何可識別語言都不成立的性質,總回答「否」即可判定。萊斯定理排除了這兩種平凡情況。證明中使用的見證語言不必難以識別;、 和 這類簡單語言往往就足夠。
對於正則性這類性質,其中一個見證必須是可識別但非正則的語言。僅僅舉出任意一個非正則集合而不說明它可識別,是不足夠的。語言 是可判定的:檢查區塊的順序並比較兩個計數即可,所以它是合格的見證。它的非正則性則是另一個事實,由泵引理證明。
在歸約中,一旦性質確定,參照機器 也就固定了。構造容許包含這部有限的機器描述。構造並不把性質的任意描述作為輸入,也不需要從這樣的描述計算出見證。這一區別使得從 到 的有效變換保持精確。
總結
語義性質只依賴於所接受的語言。若它是非平凡的,則可以構造一個識別器,視乎某個停機計算的結果,在空語言與一個固定見證語言之間切換。因此,該性質的判定器將能夠判定停機問題。平凡性質、機器的語法特徵以及受限的表示類,都不在本定理的假設範圍之內。
練習
快速檢查
(解釋為甚麼「包含字 」這一性質對任意圖靈機識別器是非平凡且不可判定的。)
找出兩個可識別語言,一個含有該字,一個不含。
解答 · 答案
空語言不含 ,而 含有 ;兩者都是可識別的。 是否屬於語言只依賴於所接受的語言,所以由萊斯定理,該性質是不可判定的。
快速檢查
(性質「所接受的語言等於 」是否屬於萊斯定理的適用範圍?請給出非平凡性的見證。)
檢查兩項假設:非平凡性,以及只依賴於語言。
解答 · 答案
是。 是可識別的且滿足該性質,而 是可識別的且不滿足該性質。是否等於 只依賴於語言,所以該性質是非平凡的語義性質。
快速檢查
(解釋為甚麼「機器在 100 步內接受 」不是所識別語言的語義性質。)
找兩部語言相同但運行時間不同的機器。
解答 · 答案
一部機器可以立即接受 ,而另一部機器在接受它之前先執行 101 步空操作;除此之外它們可以識別同一個語言。儘管所接受的語言相同,有限時間內的答案卻不同。有界模擬本身是可判定的。
快速檢查
(對於非空性這一性質,描述其「是」實例的一個識別器,並解釋為甚麼萊斯定理仍然適用。)
哪種程序可以同時搜尋所有輸入?
解答 · 答案
枚舉所有輸入字,並交錯模擬該編碼機器在這些字上的運行,每次運行的步數遞增且有限。若任一模擬接受,則接受。若語言非空,最終會找到某次接受運行;若語言為空,該程序可能永遠運行。該性質是非平凡的語義性質,所以儘管其「是」實例是可識別的,它仍是不可判定的。