動機
有限自動機、下推自動機和有界帶機器各自對記憶施加了限制,每種限制都排除了一些語言。圖靈(Turing)機取消了這個限制:它有一條無界的帶,可以在上面讀寫。問題也隨之改變。我們不再問哪些語言適合某個記憶界,而是問哪些語言可以由任何機械過程判定,並發現存在明確的、可證明的極限,這些極限並非來自資源不足。
我們精確陳述機器模型,證明關於識別與判定的核心定理,並把前面各章的語言類放進同一條鏈中。完整的轉移表只對一台小的示例機器給出;通用機器只在算法層面描述,其中常規的子程序假定可以實現。我們不作超出經典可計算性的任何斷言。
定義
定義 5.1.1
(圖靈機與格局)
確定型圖靈機是 ,其中 為有限狀態集, 為輸入字母表,帶字母表 ,空白符 ,轉移函數為 。帶向右無界,起初是輸入字後接空白;讀寫頭從第一個單元出發。從第一個單元左移時讀寫頭留在原處。格局是串 ,其中 ,,意為帶上是 後接空白,狀態為 ,讀寫頭掃描 的第一個符號( 為空時掃描空白)。關係 表示 由一步移動得到。
若從 出發到達處於 的格局,則機器接受 ;若到達處於 的格局,則拒絕 ;否則循環,即永遠運行。以 記被接受的字的集合。
定義 5.1.2
(識別器、判定器、可判定、可識別)
若 對某台機器 成立,則稱語言 圖靈可識別;這時 只需接受 中的字,對其他字可以循環。若 對某台在每個輸入上都停機(接受或拒絕)的機器 成立,則稱 可判定;這樣的 稱為判定器。
定義 5.1.3
(編碼與映射歸約)
固定一種可計算的單射方式,把機器 與字 寫成 上的串 與 ,並使得判斷一個串是否為合法編碼是可判定的。從 到 的映射歸約記作 ,是一個全可計算函數 ,使對所有 有 。定義 ,,(自接受),以及 。
定理
定理 5.1.4
(通用模擬)
存在圖靈機 ,在輸入 上,當且僅當 接受 時接受,當且僅當 拒絕 時拒絕,當且僅當 在 上循環時循環。因此 與 是圖靈可識別的。
定理 5.1.5
(可判定即可識別且補集可識別)
語言 可判定,當且僅當 與 都是圖靈可識別的。
定理 5.1.6
(自接受與停機問題不可判定)
不可判定。因此 、 與 不可判定,且 的補集不是圖靈可識別的。
定理 5.1.7
(歸約的方向)
設 給出 。若 可判定則 可判定;若 可識別則 可識別。等價地,若 不可判定,則 不可判定。關係 是傳遞的。
定理 5.1.8
(萊斯(Rice)定理)
設 是 上圖靈可識別語言的集合,使得某個可識別語言屬於 ,且某個可識別語言不屬於 。則 不可判定。
定理 5.1.9
(語言類的一條鏈)
在至少含三個符號的固定字母表上,,其中 CSL 是由非收縮文法生成的類,DEC 是可判定語言類,REC 是圖靈可識別語言類。每個包含都是真包含。包含 使用配套範式一章所證明的喬姆斯基(Chomsky)範式定理。
證明思路
證明
(逐步模擬構成通用機器)
機器 在帶上保存 當前格局的編碼,旁邊是編碼後的轉移表 。一個模擬步驟在格局中找到狀態與被掃描的符號,在 中查找匹配的 項,並改寫格局。這些子程序(搜尋、串比較、複製、平移)都是常規的,我們不給出其狀態。對 歸納可知,模擬 步後帶上的格局編碼了 在 上的 。若 處於 ,則 接受;若處於 ,則拒絕;若 永不停機,則 永遠運行。對 ,先複製 得到 ,再運行 。
證明
(交錯執行判定補集可識別的語言)
若 可判定,則 的判定器就是識別器,交換其接受與拒絕狀態得到補集的判定器,因而也是識別器。反之,設 識別 , 識別其補集。對輸入 ,在不同的帶道上交替運行 與 :先走 一步,再走 一步,如此繼續。這種交替運行的技巧稱為交錯執行(dovetailing)。 與 恰有一個為真,所以恰有一台機器接受 ,並且在有限步之後接受;另一台永不接受。若 接受,則接受;若 接受,則拒絕。這在每個輸入上停機並判定 。若改為先後運行兩台機器,則會失敗,因為第一台可能循環。
證明
(對自接受問題的判定器作對角化)
假設判定器 判定 。構造 :對輸入 ,若 不是機器的合法編碼就拒絕;否則在 上運行 ,當且僅當 拒絕時接受。 在每個輸入上停機。令 。則 接受 當且僅當 拒絕 ,當且僅當 ,當且僅當 不接受 ,矛盾。所以不存在判定器。這同樣是一個對角線論證:只要 正確, 的語言在輸入 處就與每台機器 的語言不同。
證明透視
對角線論證究竟用到了甚麼
需要三個要素,每個都能在正文中找到。第一,有效的編碼:每台機器 都是一個串,所以可以把 自己的描述作為 的輸入。第二,假設的判定器 必須是一台機器,這樣由它構造的 才是一台在 上行為有定義的機器。第三, 翻轉 的回答並在每個輸入上停機。矛盾只出現在唯一的輸入 上。這個論證並不說明沒有機器能識別 ——通用機器就識別它。
證明
(不可判定性沿歸約傳遞)
下列每個歸約還把非法源編碼送到目標集合外的一個固定對象,因此預處理在全部字串上都有定義。 用 歸約 ,並把非合法編碼的串送到 之外的某個固定串。於是由歸約方向定理, 不可判定。其次 :把 映到 ,其中 在輸入 上模擬 在 上的運行,若 接受則接受,若 拒絕則進入無限循環。於是 在 上停機當且僅當 接受 。最後 :把 映到 ,其中 忽略其輸入,先把 寫到帶上再運行 ; 在空輸入上停機當且僅當 在 上停機。 的補集不可能是可識別的,因為 被通用機器識別,若兩者都可識別,則由補集定理 將是可判定的。
證明
(歸約把可判定性反向傳遞)
設 把 歸約到 。若 有判定器 ,則對輸入 計算 並在其上運行 :這判定了 ,因為 且 是全函數。可識別情形相同,使用 的識別器。取逆否命題即得不可判定性的陳述。關於傳遞性,若 把 歸約到 , 把 歸約到 ,則 是全可計算的,並把 歸約到 。
證明
(停機問題歸約到每個非平凡性質)
對非法源編碼,輸出一個其語言不滿足當前性質的固定機器。 先說明 不可判定(上面已證)。先設 。選取機器 使 。定義 ,其中 在輸入 上先模擬 在 上的運行;若 接受 ,則 在 上運行 ,當且僅當 接受時接受;若 不接受 (拒絕或循環),則 永不接受。於是當 接受 時 ,否則 。所以 把 歸約到語言 ,因而 不可判定。若 ,對「不在 中的可識別語言」所成的類 應用該論證,它是非平凡的且不含 ;合法編碼的集合是可判定的,而 是 在其中的補集,所以 也不可判定。
證明透視
為何來源問題可以是接受問題
包裝機 由非平凡性提供的機器 ,以及 和 構成。它的兩種結果 與 ,恰好按 是否接受 來區分。 拒絕和 不停機,都使 甚麼也不接受,這沒有問題,因為 把兩者同樣對待。正是假設 ,兩種結果才有不同的答案;取補集一步只是把這個假設恢復。映射 可計算,是因為 只是被寫出來,從不被運行。
證明
(包含鏈及各包含為何是真包含)
:DFA 給出一個文法,每個狀態對應一個變元,規則為 ,以及對接受狀態 的 。:在範式假設下, 的範式文法的規則 與 是非收縮的;若 ,則加入新的起始變元 與規則 。 即上下文有關一章中成員問題的可判定性。 是顯然的。 是平凡的。
關於真包含: 是上下文無關的但不是正則的。 是上下文有關的但不是上下文無關的。對 ,使用相同固定字母表 ,其中含前三個反例所需的不同符號。變元名取自一個固定的可數列表的、 上的非收縮文法是有限對象,所以可以被可計算地枚舉為 ; 上的每個上下文有關語言在變元重新命名意義下都是某個 。枚舉 為 ,令 。 可判定:給定 ,找到 使 ,構造 ,並用長度引理判定成員問題。但對每個 有 ,因為 恰屬於兩者之一。對 ,見證是 。對 ,機器是有限串,因而只有可數多個,而 的子集由康托爾(Cantor)論證是不可數多的。
反例模式
反方向的歸約甚麼也證明不了
斷言(錯誤):要證明 不可判定,只需把 歸約到某個可判定語言,或把某個可判定語言歸約到 。取可判定語言 。把每個輸入都映到某個固定的不停機的對的常值函數,就是 到 的映射歸約,但這並不能告訴我們 是否可判定。同樣,把 歸約到一個可判定語言只會表明 可判定,而這是假的。修正:要證明目標語言 不可判定,應把已知不可判定的語言 歸約到 ,並且可計算映射 必須在兩個方向上都滿足 。
概念視角算法
交錯執行作為搜尋的調度
識別器是這樣一種搜尋:答案為「是」時在有限步內成功,答案為「否」時可能永遠不結束。判定器把兩個這樣的搜尋結合起來,一個搜尋成員資格,一個搜尋非成員資格,並交替運行,使得無論哪一個成功都會被注意到。交錯執行不是一種優化;它是避免卡在永遠不會結束的那個搜尋中的唯一辦法。
例題
例題 5.1.10
( 時 的判定器)
未列出的狀態與符號組合均進入拒絕狀態並保留當前符號;未說明寫入的移動也保留符號,因此轉移函數全定義。
設機器的帶符號為 ,轉移如下:在 讀到 時,寫 ,右移,進入 ;在 讀到 時,右移進入 ;在 讀到其他符號時拒絕。在 ,向右越過 與 ;讀到 時,寫 ,左移,進入 ;讀到 時拒絕。在 ,向左越過 與 ;讀到 時右移並進入 。在 向右越過 ,讀到 時接受,讀到 或 時拒絕。輸入 上: 接受。每一遍 配對一個 與一個 ;機器恰在所有 都用完時到達 ,然後僅當不再剩有 時接受。
例題 5.1.11
(玩具表上的對角線模式)
設四台機器和四個輸入給出接受表(1 表示接受,0 表示不接受),各行為 、、、。對角線是 ;翻轉得 。翻轉後的行在第 列與第 行不同,對每個 都成立,所以它不出現在表中的任何地方。真正的證明把這一點用到所有機器對所有機器編碼的無限表上,翻轉後的對角線就是 的語言,而假設的判定器 使得翻轉後的對角線是可計算的。
例題 5.1.12
(使用萊斯定理,以及它何時不適用)
令 。語言 可識別且屬於 , 可識別且不屬於 ,所以 不可判定。相反,「 至多有五個狀態」涉及的是 的描述而不是語言 :語言相同的兩台機器規模可以不同。萊斯(Rice)定理不適用,事實上這個問題通過讀取 就可判定。類似地,「 在十步之內接受 」通過模擬十步即可判定。
常見錯誤
常見錯誤
(等待識別器不能揭示非成員關係)
不要混淆識別器與判定器。識別器在語言之外的字上可能不停機,所以運行它並等待並不能揭示非成員關係。
常見錯誤
(不可判定不等於無法分析)
不要說停機問題表明某台特定的機器「無法被分析」:對固定的機器和固定的輸入,問題有確定的是或否的答案,並且存在輸出該答案的平凡機器。不可判定性說的是對所有實例的同一個統一過程。
常見錯誤
(萊斯定理針對語言,而非描述)
不要把萊斯定理應用到機器描述或運行時間的性質上。
總結
圖靈機有格局,通用機器可以根據描述模擬任何機器。一個語言可判定當且僅當它與其補集都可識別,這由交錯執行證明。對角線論證表明自接受不可判定,歸約把這一結論傳遞到接受、停機和空輸入上的停機。萊斯定理使被識別語言的每個非平凡性質都不可判定。正則、上下文無關、上下文有關、可判定和可識別這幾個類構成一條嚴格的鏈,前三個環節依賴前面各章。
練習
練習 5.1.13
(證明可判定語言對補和交封閉,可識別語言對並和交封閉。)
核心證明
解答(3)
- 1
判定器:補與交
若 判定 ,交換接受與拒絕就判定補集。對兩個判定器的交集,同時運行兩者並僅當兩者都接受時接受;兩者都停機。
- 2
識別器:交集
對識別器 ,先運行 再運行 ,僅當兩者都接受時接受。若 ,兩個階段都以接受結束;若 在任一語言之外,相應階段永不接受,所以 被正確地永不接受。
依據: 識別器從不接受語言之外的字,不論它是否停機。
- 3
識別器:以交錯執行處理並集
∎交錯執行兩台機器,只要其中一台接受就接受;先後運行是錯誤的,因為第一台機器可能在第二台接受的字上循環。
練習 5.1.14
(證明 且 蘊含 ,並證明 蘊含 。)
核心證明
解答(3)
- 1
複合兩個映射
設 與 為全可計算函數,使 且 。則 。
- 2
驗證複合映射是歸約
是全可計算的,所以 。
依據: 全可計算函數的複合仍是全可計算函數。
- 3
補集使用同一個映射
∎對等價式 取否定,得 ,所以同一個 把 歸約到 。
快速檢查
(證明 不可判定。)
這描述的是語言的哪一種性質?它是否非平凡?
解答 · 答案
令 為無限的可識別語言所成的集合。 可識別且無限,所以屬於 ; 可識別但不是無限的。所以 非平凡,萊斯定理適用。
快速檢查
(在第一個例題的機器上追蹤輸入 ,並說明結果。)
每一輪把一個 與一個 配對。
解答 · 答案
。在 讀到 時機器拒絕。該字的 比 多,所以拒絕是正確的。