圖靈機雜思 (rev#2)

By 劉未鵬

C++ 的羅浮宮 ( http://blog.csdn.net/pongba )

C++ Template 是圖靈完備 的 （ turing-complete ，或者更確切的說，是圖靈等價（ turing-equivalent ）），關于這一點是沒什么懸念的，只是前幾天有位朋友問到為什么說 C++ Template 是圖靈完備的，為了找出當初的連接，于是又去搜了一下 wikipedia 和 standford encyclopaedia ，誰之這一搜之下又帶出了一大堆內容，于是又花了好幾個時辰將圖靈機的相關理論復習了一遍，順便以四十五度角仰視了一下 Alan Turing 的生平，神奇的是在追尋鏈接和搜索的過程中居然翻到了一篇關于 constructive mathematics 以及一篇關于 Intuitionistic Logic 的東東，那是后話，暫且不提。先來說說 C++ Template 和圖靈機。

圖靈機是圖靈為了研究可計算問題而構思的一個理論裝置，你只要想一想有限狀態機就可以大概知道圖靈機是個什么概念了，只不過圖靈機的內存（紙帶）是潛無窮的（也就是可以任意長啦， “ 潛無窮 ” 是古稀蠟人的說辭）。圖靈機的定義形象的說來就像老式的電傳機：一個讀寫頭，一根紙帶（可能任意長），讀寫頭不斷讀取紙帶上的符號，并根據內在的狀態轉換規則轉換當前狀態，同時進行一些動作，譬如插除或改寫當前字符，向前 / 向后移動讀寫頭或保持不動等。至于其抽象的定義大抵就是 有限狀態機 的定義了。

圖靈機的這一定義現在我們看起來似乎是很顯然的，然而當時卻代表著一種思想上的革命，一種從無到有。圖靈機實質上抽象出了我們平素進行機械式計算的核心規律，所以才等價于 “ 一個人 + 紙筆 + 一定的規則 ” 所 進行的機械運算。

這么個理論機器首先就指明了創建計算機的可能性，然而這還不夠，如果為了某一個問題就去創建一個特定的圖靈機的話效率就太低了。圖靈機理論的一個最美妙的結論就是存在 “ 元圖靈機 （ Universal Turing-Machine ，直譯應為一般圖靈機 / 通用圖靈機，然而 “ 元圖靈機 ” 更精確地表達了其意思），所謂元圖靈機其實就是把圖靈機作為運算對象的圖靈機，假設有一個元圖靈機 M ，一個圖靈機 P 以及 P 的輸入數據 D ，那么將 (P, D) 喂給元圖靈機 M ， M 就能夠吐出 P(D) （即 P 在 D 上的結果）。而這便是現在我們所用的計算機的始祖模型，其中 M 就好比我們的計算機（元圖靈機）， P 則是程序（編碼后的圖靈機）， D 則是程序 P 的輸入數據。元圖靈機的存在表明了我們可以用一臺機器來解決所有圖靈可計算（ turing-computable ）的問題 —— 只要喂給它解決這個特定問題的圖靈機編碼（程序）以及問題的輸入數據即可，該元圖靈機就會模擬我們喂給它的那個圖靈機 P 的行為，最終給出結果。 元圖靈機的存在性為計算機的誕生點燃了一盞明燈 ，這是圖靈機理論中最漂亮的發現。

關于圖靈機還有兩個有名的 Halting Problem 和 Busy Beaver Problem ，不過前者更有名，但沒有后者有意思，所以具體就不說了，可以 google 。這兩個問題說明了圖靈機并不是 “ 萬能 ” 的，它只能解決可以 “ 機械地 ” 解決的問題，只不過這個 “ 機械地 ” 定義太過含糊，沒有準確地界定，所以有必要精確定義一下圖靈機到底能解決哪些問題，換句話說，到底哪些問題是圖靈可計算的。

這里有一個非常漂亮的證明，是關于 哪些數是圖靈可計算的 。我們說有無窮多個實數是圖靈不可計算的。首先說明一下一個數是圖靈可計算的是個什么概念，一個數是圖靈可計算的就是說存在一個圖靈機，給它一個空紙帶，最終它能打印出任意逼近該數的結果。像 pi 、自然常數 E 以及所有多項式的根就都是圖靈可計算的（可由機械步驟任意逼近），這很好理解，因為我們可以寫一個程序來迭代任意逼近它們，譬如 E 就是一個無窮級數的和。但還有其它實數呢？有沒有圖靈不可計算的實數？要想弄明白這個問題，先要考慮一共存在多少個圖靈機（廢話，當然是無窮多個了，但 “ 無窮多 ” 也有一個級別問題 :) ），為此先將圖靈機進行編碼，由于圖靈機的狀態是有限的，將圖靈機編碼為一個五元組 ( Old_State, Symbol, New_State, New_Symbol, Move) 的序列（或更多 / 更少都有可能，這是比較常見的一種編碼方式，但總之一定是 N-TUPLE ， N 有限），那么我們來考慮一個 N-state(N 個狀態 ) ， M-symbol 的圖靈機一共有多少種可能，為此，先考慮對應 N-state 、 M-symbol 的 5-tuple （見上面的定義）有多少個，根據簡單的排列組合規律，一共是 N*M*N*M*3 （最后一個 3 是指 Move 的可能性 —— 靜止 / 向前 / 向后），換句話說，也就是以 M,N 為參數的一個 upper-bounded function 。 OK ，現在來考慮一個圖靈機的編碼形式，一個圖靈機其實就是由一集 5-tuple 所構成，所以既然 N-state,M-symbol 的 5-tuple 一共有 N*M*N*M*3 個，換句話說，這個由所有可能的 5-tuple 所構成的集合中一共有 N*M*N*M*3 個元素，那么這個集合的所有子集合的個數也就是 N-state,M-symbol 的所有圖靈機的個數，根據冪集的定義，這也就是 2 ^N*M*N*M*3 個。這里為了簡單起見，我們暫且固定 M 為 M-- ₀ ，即 symbol 的個數，這樣所有 M ₀ -state 的圖靈機的個數就是 ：

2 ^1*M0*1*M0*3 +2 ^2*M0*2*M0*3 +2 ^3*M0*3*M0*3 +… = 。

現在我們看到，這個和式的每一項都是 countable 的，而 Z _＋ ×Z _＋ 尚且是可列集，就別說這里每項都有限的情況了，所以很容易就可以和 Z _＋ 建立起單射 (injective) ，換句話說，所有 M ₀ -state 的圖靈機的集合是一個可列集。好了，現在把 M ₀ 換成變量，既然所有 M _{0 －} state 的圖靈機集合都是可列的，而 M ₀ 又是自然數（可列集），再加上 “ 可列集個可列集 ” 仍然是可列集這一性質，就容易得出一切圖靈機構成的集合是可列集這一結論了。

其實證明一切圖靈機所構成的集合的可列性還有一種更簡單但取巧一點的辦法：我們知道計算機語言是圖靈等價的，所以討論 “ 一切圖靈機 ” 其實相當于討論 “ 一切計算機程序 ” ，而從二進制層面來看，一個計算機程序可以被看成 0 和 1 的序列，基于這種表示， “ 一切計算機程序 ” 所成集合的勢也就呼之欲出了，因為 “ 一切計算機程序 ”=“ 所有長度為 1 的計算機程序 ”+“ 所有長度為 2 的計算機程序 ”+“ 所有長度為 3 的計算機程序 ”+… 。把 “ 所有長度為 i 的計算機程序 ” 所成集合記為 S _i ， “ 一切計算機程序 ” 所成集合記為 S ，立即有： ; 以及 。我們記 S _i 中的第 j 個元素為 S _i (j) ，那么很容易就可以建立 S 跟 Z _＋ 之間的 injective function （單射），只須令 f: S _i (j)->2 ⁱ 3 ^j ; 顯然 f 就是 injective 的。這就證明了 S 的可列性質。

那么，這一結論有什么重要意義呢？非常重要，我們知道，實數集是不可列的，其勢（或稱 “ 基 ” ）為阿列夫 1 （而 Z ，即整數集的勢則是阿列夫 0 ），所以即便耗盡所有圖靈機仍然還是會有 “ 列不出 ” 的實數。要想嚴格證明這一點也很簡單，只要運用 cantor 在證明集合論時運用的經典的 “ 對角線 ” 手法，不妨簡單描述一下：

首先，既然所有圖靈機的集合是一可列集，我們就可以用 M ₀ ,M ₁ ,M ₂ ,… 來表示它們。現在假設 M _i 能計算出的實數為 A _i0 .A _i1 A _i2 A _i3 … 。那么我們構造一個新的實數 B=B ₀ .B ₁ B ₂ B ₃ ... ，使其滿足 B ₁ ≠A ₁₁ ,B ₂ ≠A ₂₂ ,B ₃ ≠A ₃₃ ,…,B _n ≠A _nn 。這樣構造出來的一個實數 B 可以保證不與任何 A _i 相等，同時這個 B 并不為任何圖靈機所計算出來（因為剛才的 A _i 序列已經耗盡了所有的圖靈機）。這某種程度上就表明圖靈機的勢為阿列夫 0 （盡管對圖靈機并不能稱 “ 勢 ” ）。

除此之外，函數空間的所有函數也并不都是圖靈可計算的，一個函數為圖靈可計算其實就代表存在一個圖靈機可以模擬該函數的行為。這一結論通過剛才的證明就很好解釋了：因為函數空間的勢為阿列夫 2 ，比實數集還要大，怎么可能由圖靈機來枚舉盡呢？要證明也很簡單，同樣是對角線法，就不說了。

那么，既然我們已經從原則上肯定了有些函數是不可計算的，換句話說，有些函數你雖然知道它是函數，但你就是無法用圖靈機來將它模擬出來，用今天的話說，就是無法編程實現！這可比較令人沮喪，居然有無法編程實現的函數。那么究竟能否造出這么一個函數來讓人瞧瞧怎么個不能編程實現法呢？這就是所謂的 Busy Beaver 問題。 Busy Beaver 問題就是要構造這么一個函數，它用于計算任意一個 N-state 的圖靈機的最大 “ 生產率（ Productivity ） ” ，生產率的定義就是給一個圖靈機一條空紙帶，最終當該圖靈機 halt 的時候數紙帶上的 1 的個數，就是其生產率。所有 N-state 的圖靈機的最大生產率就是指一切 N 狀態的圖靈機的生產率中的最大者。很顯然，這是一個 N 的函數。記為 L(n) 。那么問題是，這個 L(n) 是否是圖靈可計算的？答案是不行！用反證法：假設存在這么一個圖靈機 B ，能夠模仿 L(n) 的行為，那么我們將它接到一個特殊的 n-state 的圖靈機 I 后面（ I 的作用是在紙帶上留下 n 個 1 ，作為 B 的輸入，可以證明，這樣的 I 是存在的），這樣形成一個新的圖靈機 IB ，這個新的圖靈機的作用就是計算 L(n) ，其中 n 就是 I 的狀態數，也是 I 的輸出， B 的輸入。我們再在后面接上一個 B ，得到 IBB 這么一個圖靈機，其效果為 L(L(n)) 。那么現在考慮 IBB 自身的狀態數，是 I 的狀態數（即 n ） +2 倍的 B 的狀態數，假設 B 的狀態數為 b （ b 為有限值），那么 IBB 的狀態數就是 n+2b ，那么可想而知 n+2b 狀態的圖靈機的最大 productivity 是肯定大于等于 L(L(n)) 的，因為已經有一個圖靈機的 productivity 是 L(L(n)) 了，它就是 IBB 。這個不等式就是 L(n+2b)>=L(L(n)) ，由此我們可以推出 n+2b>=L(n) （ L(i)>=L(j)=>i>=j 這一結論易證），又根據 n 的任意性，我們可以令其等于 n+11 ，于是得 n+11+2b>=L(n+11) ，而我們知道 11 狀態可以實現出一個將紙帶上的 1 的數目翻倍的這樣一個圖靈機（試試看吧 :) 很簡單），于是 L(n+11)>=2n （只要把前面的 n 狀態用于一個產生 n 個 1 的圖靈機，后面的 11 狀態做成一個翻倍 1 的數目的圖靈機即可），于是得到 n+11+2b>=2n ，于是得到 11+2b>=n 。根據 n 的任意性， b 的有限性，這就得到了矛盾！（其實這里還隱含著另一層意思，即要實現這么一個圖靈機，必須要有無窮多個狀態才行，即 b 要任意大，而根據圖靈機的定義， b 是有限的）。

說到這里，想起還有一個經典的函數也是圖靈不可計算的。上面已經提到，所有圖靈可計算的實數所構成的集合是一可列集，記為 S={s|s 為圖靈可計算的 } （這是因為所有圖靈機構成的集合是可列集），現構造這樣一個函數 f ，使得 f(j,i)=S _j (i) ；其中 S _j 就是 S 中的以 j 為下標的元素 ,S _j (i) 則是指 S _j 的第 i 位的值。我們斷言這樣一個 f 就是圖靈不可計算的。欲證明這一點，我們假設存在一個圖靈機 P ，滿足 P(j,i)=S _j (i) 。現使用對角線法構造出一個新的不屬于集合 S 的實數 r ， r 滿足：

我們發現，只要 P 存在，那么 r 就也是圖靈可計算的，而這又跟 r 不屬于 S 是矛盾的，所以推出 “P 不存在 ” 這一結論。（注：為什么只要 P 存在 r 就也是圖靈可計算的呢？這樣想，我們構造一個新的圖靈機 Q ，使滿足：

這么個新的圖靈機 Q ，只要喂給它一個下標 i ，就會吐出 r 的第 i 位，于是 r 就成了圖靈可計算的了。

Church-Turing Thesis 大意就是說，在所有以自然數為定義域的函數中，只有那些遞歸函數（這里遞歸函數也包括有限步驟的函數）才是圖靈可計算的。這一結論界定了圖靈機的計算能力。乃是非常重要的。其實想想也很直觀，一個無窮不循環的函數自然需要無窮多個狀態才能計算了。而一個圖靈機的狀態是有限的，在這個有限空間中轉來轉去最終肯定是墜入循環，這就好像兩整數相除一樣，要么除盡，要么無限循環小數，用鴿籠原理可以很容易地證明。

來簡單說說 C++ Template 的圖靈完備性（ turing-complete ，更準確地說是 turing-equivalent ，因為 turing-complete 一般是指一個問題是 turing-computable 的）。要想證明一門語言的圖靈完備性從原則上來說就是要證明它可以解決圖靈可計算的所有問題。或者構造出一種轉換途徑，能夠把任何圖靈可計算問題的解決方法轉換為這門語言的程序。但這里還有一個更取巧的方法，用這門語言實現一個 Universal Turing Machine （其實差不多就是有限狀態機啦）。 C++ Template 就可以做到這一點，實際上這早已有人做過了。另外，一般來說一門語言只要有 if 判斷，遞歸或循環結構以及最基本的賦值能力和四則運算就是圖靈完備的了，而 C++ Template 恰巧這些都具備，其中 if 判斷和遞歸結構是借助模板偏特化能力實現的，估計語言的設計者當初也沒有料到這一點會給現代 C++ 帶來這么大的影響 :)

另外，嚴格來說，現今任何計算機其實都不是 turing-equivalent 的，因為它們的內存是有窮的。而圖靈機的內存則是潛無窮的。只不過只要不出現內存不耗盡的情況都一樣啦 :)

前面提到的 constructive mathematics 和 intuitive logic 不屬于圖靈機的內容，有空再寫吧。

P.S 圖靈機揭示了人類機械演算的深層機理，歌德爾的著名的不完備性定理跟圖靈機的停機問題就是等價的。用通俗的話來說其實就是 “ 沒有全知全能的上帝 ” ，這里上帝其實就隱喻在圖靈機算模型限制之下的公理體系。不過這又是另一個故事了，有時間再寫吧 :)