動機
Cantor 論證從假定列表中構造一個遺漏對象。可計算性進一步要求:列表或構造能否由有限、有效的步驟完成?程式至多可數只說明某些集合不可判定,卻不能識別某個具體問題。停機問題用更精確的自輸入對角化,迫使假定判定程式違背自己的預測。
結論針對必須在每個合法輸入上終止並正確回答的統一算法,不表示每個具體程式都無法分析。顯式無限循環可證明不停機,有限運算可證明停機;不存在的是通吃所有程式及輸入的終止方法。
定義
定義 5.1.1
(圖靈機與可計算函數)
固定確定性圖靈機(Turing machine)模型:有限狀態集、含空白的有限紙帶字母表、以整數編號的紙帶格、一個讀寫頭和有限轉移表。每個非終止步驟讀取當前符號、寫入符號、左右移動一格並改變狀態。輸入為其餘全空白紙帶上的有限二進制字。指定終止狀態表示停機,用固定有效約定把自然數輸入輸出編碼為有限字。
機器計算部分函數 :停機時返回輸出值,不停機時無定義。可約定每次停機都返回某個自然數。若對每個輸入都停機給出函數值,則為全可計算函數。部分性不允許在不停機輸入上隨意指定一個答案。
有限描述可有效枚舉為 ;非法描述解釋為固定不停機機器。記其部分函數為 。通用模擬器對 解碼轉移表並逐步模擬 。配置由狀態、讀寫頭位置和有限多個非空白格表示,所以每個有限步驟可在有限字串上有效執行,得到部分可計算 。通用性不保證終止。
定義 5.1.2
(可判定集、半可判定集與多一歸約)
可判定,指其特徵函數全可計算;半可判定(可計算可枚舉),指某程式恰在成員上停機。會停機拒絕的識別器可改為拒絕時循環,符合此約定。多一歸約 是全可計算函數 ,滿足 。
定理/命題
定理 5.1.3
(對角停機集)
對角停機集
半可判定而不可判定。
定理 5.1.4
(互補的半判定)
集合可判定,當且僅當它與其補集都半可判定。因此 不半可判定。
定理 5.1.5
(以歸約轉移)
若 ,則 可判定推出 可判定; 半可判定推出 半可判定。把已知不可判定的 歸約到 ,便可證明 不可判定。
定理 5.1.6
(Rice 定理(部分函數))
部分可計算函數的任意非平凡性質 ,其指標集 都不可判定。非平凡指有函數滿足、也有函數不滿足;性質必須只依賴計算出的部分函數,而非程式字面或運行時間。
證明思路
證明
(對角程式擊敗任何停機判定器)
模擬 ,它停機時才停機,便半判定 。假設全程式 判定 ,成員輸出 ,否則輸出 。構造 :先算 ;若為 則永久循環,若為 則停機。設 的指標為 。 會使 不停機,違背成員預測; 又使它停機,違背非成員預測。兩種答案都矛盾。假設 存在時,對它的調用可以寫成有限程式,故 確實在枚舉中。
證明透視
對角矛盾的精確依賴
矛盾同時假設 正確且全定義。全定義保證 總能走到分支,因此 的預測確實決定 是否停機;正確性隨後在以自身代碼為輸入時遭到兩種分支共同否定。若 只是停機識別器,它可能不終止,分支論證就不成立,因而不會與通用模擬矛盾。
另一個條件是有效自應用:指標是自然數,所以程式描述可以作為普通數值輸入。機器不需要神秘地察看自身,也不需要在運行中先算出自己的指標。在假設下寫出有限描述 後,數學論證知道它有某個指標 ,再考察輸入 。外部證明與程式實際執行的指令是兩層不同的推理。明確這一區別,既排除假自指的疑慮,也說明為何同樣的構造排除了對所有列出程式都全定義的通用求值器。
證明
(交錯執行兩個半判定器)
可判定集顯然給出兩個方向的半判定:遇到不要的答案就循環。反過來,交替執行 與其補集的半判定程式,每次各一步,直到一個停機,再返回對應答案。恰有一個最終停機。這個交錯模擬不能先等第一個完全結束再運行第二個。若 的補集也半可判定,就會得到 的判定器,矛盾。
證明
(與全可計算歸約複合)
歸約定理中先計算必終止的 ,再運行 的相應程式;成員等價保證正確。若預處理不保證終止,就不能從簡單的 得到判定器。
證明
(僅在 停機後才運行 的包裝程式)
Rice 定理中,令 為處處無定義函數。先設 ,固定一個屬於 的部分可計算函數 。從 有效寫出程式 :先模擬 ,停機後才運行 。把數字 插入固定包裝程式是總能完成的語法操作,映射 全可計算。若 ,所得函數為 ;若 ,所得函數為 。因此判定語義性質便判定了 。若 ,對不含 的互補性質應用同一論證;判定一個集合也能判定其補集,故仍矛盾。
反例模式
Rice 定理需要關於所計算函數的性質
聲稱:程式指標的每個非平凡性質,其指標集都不可判定。取
它是非平凡的。一部只有起始狀態和終止狀態的機器,若在起始狀態中重寫所讀符號並永遠向右移動,就屬於 並計算 。再添加十一個無法到達的狀態,所得機器仍計算 ,卻不屬於 ;因此 不是由 決定的。然而 可判定:給定 ,解碼其描述(非法描述代表固定的不停機機器,其狀態數已知)並數狀態,這種有限的語法分析總會終止。
Rice 的證明在此失效,因為其歸約需要 是否屬於該集合只取決於它計算 還是 。對 而言,這取決於包裝程式的大小,與 是否停機無關。修正後的假設是外延性: 必須推出 ,這正是說 對某個部分函數性質 形如 。
例題
例題 5.1.7
(有界停機可判定)
給定 ,模擬至多 步,檢查是否到終止狀態,並統一約定初始配置為時刻零。這是有限過程。無界停機詢問是否存在某個時間而不給界。逐個搜尋能半判定;若不存在,搜尋無法證實失敗。
概念視角結構
半可判定集是可判定關係的投影
有界停機給出半可判定性的第二種描述。集合 半可判定,當且僅當對某個可判定關係 有 。若程式 恰在 上停機,就令 表示「 在輸入 上於 步內停機」。反過來,給定 ,依次檢驗 ,首次成功時停機。在可判定關係前加上一個無界存在量詞,正是半判定程式所作的搜尋。
例題 5.1.8
(固定輸入也困難)
令 。給定 ,寫一個忽略輸入而模擬 的程式。其代碼 可有效計算,且 。所以 不可判定。寫包裝程式時不需要先解決被模擬的運算。
例題 5.1.9
(語義與語法)
「描述是否至多十個狀態」可解析有限文本判定。「是否計算恆零全函數」是非平凡語義性質,由 Rice 不可判定。「是否對每個輸入停機」也是。Rice 本身不判斷這些問題是否半可判定;它只排除判定器。
例題 5.1.10
(可數性比停機對角化弱)
所有程式可數,所有自然數子集不可數,故存在不可判定集合,但不能據此認定 。自輸入論證才識別 。同理,不存在列出全部全可計算函數且具有全可計算求值器 的有效枚舉,否則 全可計算,卻不同於每個列出的函數。全部部分可計算函數則有通用的部分求值器;其可能不終止恰好阻止這個矛盾。
例題 5.1.11
(識別與枚舉等價)
「可計算可枚舉」有直接的過程含義。若程式恰在 上停機,階段 中對輸入 各模擬 步,列印已檢測到停機的輸入,允許重複。列印的都在 ;若 於 步停機,任何足夠大的階段 都能檢測它。因此恰好所有成員最終都會被列印。空集由永不列印的過程表示。
反向,若可計算的持續過程恰列印 的成員,允許重複或停頓,則給定 ,模擬至列印 時停機,便半判定成員關係。不需要判斷沉默是否永久。無限可枚舉集若另有嚴格遞增的有效枚舉,就會更強:搜尋到輸出達到或超過 即可判定是否屬於,因為無限遞增自然數序列無界。因此 這樣的不可判定可枚舉集,不會有有效的遞增枚舉。重複不改變集合,但列表的到達次序可以帶來額外的計算資訊。
參數與自指
上面幾個論證都從指標 出發,寫出一個把 內置其中的新程式的代碼。這一步用得極多,值得精確陳述;把它單獨提出後,還能得到一個關於程式的不動點定理。
若兩邊都無定義,或兩邊都有定義且相等,記 。二元部分函數經固定的可計算雙射 接收單一輸入 。
定理 5.1.12
(參數定理(s-m-n))
對每個部分可計算函數 ,存在全可計算函數 ,使所有 都滿足 。
證明
(把參數寫死在程式裏)
固定一台在配對輸入上計算 的機器 。對給定的 ,令 為這樣的機器:在輸入 上,先把 的二進制字寫在輸入左邊,再由這兩個字算出 ,然後對結果運行 。只有第一階段依賴 :它是一串新狀態, 的每一位對應一個,各自寫下該位並左移,之後以固定步驟回到字的開頭。其餘階段使用固定的轉移表。因此從 產生 的轉移表,是對有限字串一致而必然終止的操作, 的指標 是全可計算的。按構造, 停機當且僅當 停機,而且輸出相同。
Rice 定理證明中的包裝程式 、把 歸約到 的映射,以及把每個半可判定集歸約到 的映射,都是這個定理的實例:每次都只寫一個二元程式,再由 固定第一個變元。
定理 5.1.13
(Kleene 遞歸定理)
對每個全可計算函數 ,存在指標 ,使 作為部分函數成立。
證明
(被求值而不是被否定的對角線)
令 :運行 ,若它停機並給出值 ,就在輸入 上運行程式 。這是部分可計算函數,所以參數定理給出全可計算的 ,使 有定義時 ,而 無定義時 處處無定義。複合 全可計算,故對某個指標 有 。由於 全定義, 有定義,因此
所以 就是所需指標。
證明透視
停機證明在此處否定,這個證明在此處求值
兩個證明都把指標輸入給自己。停機論證構造一個與假定判定器的預測背道而馳的程式,矛盾說明判定器不存在。這裏沒有任何否定: 只是模仿 所指的程式。先在自應用之前施加 ,再取 ,便使程式 與 計算同一個部分函數。 的全定義性只用了一次,用來保證 有定義。定理並不斷言 ;兩個不同指標可以計算同一函數,一般情況下也確實如此。
例題 5.1.14
(輸出自身指標的程式)
設 是「忽略輸入並輸出 」的程式的指標。對 應用參數定理,可知 全可計算。遞歸定理給出 使 ,即取值恆為 的常數函數。所以程式 在每個輸入上都輸出自己的指標。這種自指是關於一個固定有效編號的定理,不是機器模型額外附加的功能;這也說明證明中讓構造出的程式「使用自己的代碼」是合法的。
定理 5.1.15
(全定義性既不半可判定,其補集也不半可判定)
令 。 與 都不半可判定。
證明
(從停機集出發的兩個歸約)
第一,參數定理給出全可計算的 :程式 在輸入 上模擬 ,模擬停機時輸出 。於是 時 全定義, 時處處無定義。所以 把 歸約到 。若 半可判定, 也會半可判定,這是錯的。
第二,令 為全可計算函數,使程式 在輸入 上模擬 共 步:若模擬在這些步內已停機,便永久循環,否則輸出 。若 ,每個輸入都得到 ,故 。若 且 在 步後停機,則程式 在每個 上都不停機。所以 把 歸約到 , 也不半可判定。
Rice 定理只給出 不可判定。這兩個歸約說得更多: 甚至不能歸約到 ,因為多一歸約到半可判定集 的集合都半可判定。
常見錯誤
常見錯誤
(沉默不是拒絕)
半判定器沉默不是否定;逾時只說明尚未停機。
常見錯誤
(從已知困難問題出發歸約)
歸約要把已知困難問題送到新問題,反向箭頭不證明新問題困難。
常見錯誤
(停機定理關乎模型,而非計算速度)
Church–Turing 論題把非形式的有效計算與形式模型聯繫起來,不是僅靠定義一種模型就證明的定理。停機定理則是該模型中的精確結論。單純加快同一有效框架中的計算速度不會避開矛盾。本節也沒有對物理上可實現的超計算作判斷。
容許機器查詢一個固定集合,會把這裏每個論證相對化,並產生嚴格更難的停機問題。
通往推廣的路徑
可以查詢一個固定集合的機器
容許機器查詢一個固定集合,會把這裏每個論證相對化,並產生嚴格更難的停機問題。
容許機器在一步之內詢問某個數是否屬於固定集合 ,即神諭(oracle)。程式仍是有限描述,通用模擬器仍然存在,對角證明也照樣成立:帶神諭 的機器的停機集 相對於 半可判定,卻不相對於 可判定。取 ,便得到一個連能夠查詢 的機器也無法判定的停機問題。
總結
有限描述允許通用模擬,自輸入對角化排除停機的全判定器。交錯模擬區分判定與半判定,有效歸約傳遞障礙,Rice 定理把它擴展到計算所得部分函數的所有非平凡性質。參數定理把「把指標寫進程式」形式化,Kleene 遞歸定理再把它變成每個有效程式變換的不動點;全定義性既不半可判定,其補集也不半可判定。
練習
快速檢查
(證明兩個半可判定集的並、交仍半可判定,並解釋補集為何不同。)
解答 · 答案
聯集交替模擬兩者,任何一個停機就停;交集交替模擬並記錄各自是否已停機,兩個都停後才停。非成員永遠不會滿足相應條件。 半可判定而補集不半可判定,說明補集不封閉。
快速檢查
(用固定可計算配對編碼,證明 半可判定且不可判定。)
解答 · 答案
通用模擬器半判定 。映射 全可計算並把 歸約到 ,所以 的判定器將給出 的判定器。配對編碼只改變輸入格式且可有效逆轉。
快速檢查
(證明「部分函數定義域為空」不可判定,並判斷其補性質是否半可判定。)
解答 · 答案
空定義域是非平凡語義性質,由 Rice 不可判定。非空定義域可半判定:階段 中,對輸入 各模擬 步,只要任何一個停機就停。存在停機輸入時足夠大的階段會檢測到。若空定義域也半可判定,互補半判定定理便會給出判定器,故它不半可判定。
快速檢查
(學生提議運行程式,直到停機或配置重複。為何對只有有限配置的確定性機器有效,而對一般圖靈機無效?)
解答 · 答案
確定性使重複配置進入永久循環;配置數有限時,鴿巢原理保證不停機運行必重複,故檢查會完成。無限紙帶則可能產生無限多個不同配置。一直向右走並在新格寫標記的程式永不重複,檢驗它的過程也永遠不結束。狀態有限不等於配置有限。
快速檢查
(由遞歸定理推出 Rice 定理:若對非平凡性質 , 可判定,構造一個與遞歸定理矛盾的全可計算函數 。)
解答 · 答案
取 、,令 時 , 時 。 的判定器使 全可計算,所以某個 滿足 。是否屬於 只取決於所計算的函數。若 ,則 且 ,故 ;若 ,則 且 ,故 。兩種情況都矛盾。
快速檢查
(證明存在指標 ,使每個 都有 。)
解答 · 答案
對 應用參數定理,得到全可計算的 ,使 。遞歸定理給出 使 ,所以每個 都有 。取 即可。
快速檢查
(令 。沿用 證明中的兩個歸約,證明 及其補集都不半可判定。)
解答 · 答案
映射 把 送到定義域為空(因而有限)的程式,把 送到全定義程式,其定義域無限。所以 把 歸約到 , 不半可判定。映射 把 送到全定義程式,把停機時間為 的 送到定義域為 的程式。所以 把 歸約到 ,補集也不半可判定。