圖靈機雜思(增改)
劉未鵬 /文
C++的羅浮宮(http://blog.csdn.net/pongba)
C++ Template是圖靈完備（turing-complete，或者更確切的說，是圖靈等價（turing-equivalent））的，關(guān)于這一點是沒什么懸念的，只是前幾天有位朋友問到為什么說C++ Template是圖靈完備的，為了找出當初的連接，于是又去搜了一下wiki和standford encyclopaedia，誰之這一搜之下又帶出了一大堆內(nèi)容，于是又花了好幾個時辰將圖靈機的相關(guān)理論復(fù)習了一遍，順便以四十五度角仰視了一下Alan Turing的生平，神奇的是在追尋鏈接和搜索的過程中居然翻到了一篇關(guān)于constructive mathematics以及一篇關(guān)于Intuitionistic Logic的東東，那是后話，占且不提。先來說說C++ Template和圖靈機。
圖靈機是圖靈為了研究可計算問題而構(gòu)思的一個理論裝置，你只要想一想有限狀態(tài)機就可以大概知道圖靈機是個什么概念了，只不過圖靈機的內(nèi)存（紙帶）是潛無窮的（也就是可以任意長啦，“潛無窮”是古稀蠟人的說辭）。圖靈機的定義形象的說來就像老式的電傳機：一個讀寫頭，一根紙帶（可能任意長），讀寫頭不斷讀取紙帶上的符號，并根據(jù)內(nèi)在的狀態(tài)轉(zhuǎn)換規(guī)則轉(zhuǎn)換當前狀態(tài)，同時進行一些動作，譬如插除或改寫當前字符，向前/向后移動讀寫頭或保持不動等。至于其抽象的定義大抵就是有限狀態(tài)機的定義了。圖靈機的這一定義現(xiàn)在我們看起來似乎是很顯然的，然而當時卻代表著一種思想上的革命，一種從無到有。圖靈機實質(zhì)上抽象出了我們平素進行機械式計算的核心規(guī)律，所以才等價于“一個人+紙筆+一定的規(guī)則”進行機械運算呢。這么個理論機器首先就指明了創(chuàng)建計算機的可能性，然而這還不夠，如果為了某一個問題就去創(chuàng)建一個特定的圖靈機的話效率就太低了。圖靈機理論的一個最美妙的結(jié)論就是存在“元圖靈機（Universal Turing-Machine，直譯應(yīng)為一般圖靈機/通用圖靈機，然而“元圖靈機”更精確地表達了其意思），所謂元圖靈機其實就是把圖靈機作為運算對象的圖靈機，假設(shè)有一個元圖靈機M，一個圖靈機P以及P的輸入數(shù)據(jù)D，那么將(P,D)喂給元圖靈機M，M就能夠吐出P(D)（即P在D上的結(jié)果）。而這便是現(xiàn)在我們所用的計算機的始祖模型，其中M就好比我們的計算機（元圖靈機），P則是程序（編碼后的圖靈機），D則是程序P的輸入數(shù)據(jù)。元圖靈機的存在表明了我們可以用一臺機器來解決所有圖靈可計算（turing-computable）的問題——只要喂給它解決這個特定問題的圖靈機編碼（程序）以及問題的輸入數(shù)據(jù)即可，該元圖靈機就會模擬我們喂給它的那個圖靈機P的行為，最終給出結(jié)果。元圖靈機的存在性為計算機的誕生點燃了一盞明燈，這是圖靈機理論中最漂亮的發(fā)現(xiàn)。
圖1. 元圖靈機
關(guān)于圖靈機還有兩個有名的Halt Problem和Busy Beaver Problem，不過前者更有名，但沒有后者有意思，所以具體就不說了，可以google。這兩個問題說明了圖靈機并不是“萬能”的，它只能解決可以“機械地”解決的問題，只不過這個“機械地”定義太過含糊，沒有準確地界定，所以有必要精確定義一下圖靈機到底能解決哪些問題，換句話說，到底哪些問題是圖靈可計算的。這里有一個非常漂亮的證明，是關(guān)于哪些數(shù)是圖靈可計算的，說有無窮多個實數(shù)是圖靈不可計算的。首先說明一下一個數(shù)是圖靈可計算的是個什么概念，一個數(shù)是圖靈可計算的就是說存在一個圖靈機，給它一個空紙帶，最終它能打印出任意逼近該數(shù)的結(jié)果。像pi、自然常數(shù)E以及所有多項式的根就都是圖靈可計算的（可由機械步驟任意逼近），這很好理解，因為我們可以寫一個程序來迭代任意逼近它們，譬如E就是一個無窮級數(shù)的和。但還有其它實數(shù)呢？有沒有圖靈不可計算的實數(shù)？要想弄明白這個問題，先要考慮一共存在多少個圖靈機（廢話，當然是無窮多個了，但“無窮多”也有一個級別問題J），為此先將圖靈機進行編碼，由于圖靈機的狀態(tài)是有限的，將圖靈機編碼為一個五元組（5-tuple）（Old_State,Symbol,New_State,New_Symbol,Move）的序列（或更多/更少都有可能，這是比較常見的一種編碼方式，但總之一定是N-TUPLE，N有限），那么我們來考慮一個N-state(N個狀態(tài))，M-symbol的圖靈機一共有多少種可能，為此，先考慮對應(yīng)N-state、M-symbol的5-tuple（見上面的定義）有多少個，根據(jù)簡單的排列組合規(guī)律，一共是N*M*N*M*3（最后一個3是指Move的可能性——靜止/向前/向后），換句話說，也就是以M,N為參數(shù)的一個upper-bounded function。OK，現(xiàn)在來考慮一個圖靈機的編碼形式，一個圖靈機其實就是由一集5-tuple所構(gòu)成，所以既然N-state,M-symbol的5-tuple一共有N*M*N*M*3個，換句話說，這個由所有可能的5-tuple所構(gòu)成的集合中一共有N*M*N*M*3個元素，那么這個集合的所有子集合的個數(shù)也就是N-state,M-symbol的所有圖靈機的個數(shù)，根據(jù)冪集的定義，這也就是2N*M*N*M*3個。這里為了簡單起見，我們暫且固定M為M0，即symbol的個數(shù)，這樣所有M0-state的圖靈機的個數(shù)就是:
21*M0*1*M0*3+22*M0*2*M0*3+23*M0*3*M0*3+… =。
現(xiàn)在我們看到，這個和式的每一項都是coutable的，而Z＋×Z＋尚且是可列集，就別說這里每項都有限的情況了，所以很容易就可以和Z＋建立起單射(injective)，換句話說，所有M0-state的圖靈機的集合是一個可列集。好了，現(xiàn)在把M0換成變量，既然所有M0－state的圖靈機集合都是可列的，而M0又是自然數(shù)（可列集），再加上“可列集個可列集”仍然是可列集這一性質(zhì)，就容易得出一切圖靈機構(gòu)成的集合是可列集這一結(jié)論了。
注：其實證明一切圖靈機所構(gòu)成的集合的可列性還有一種更簡單但取巧一點的辦法：我們知道計算機語言是圖靈等價的，所以討論“一切圖靈機”其實相當于討論“一切計算機程序”，而從二進制層面來看，一個計算機程序可以被看成0和1的序列，基于這種表示，“一切計算機程序”所成集合的勢也就呼之欲出了，因為 “一切計算機程序”=“所有長度為1的計算機程序”+“所有長度為2的計算機程序”+“所有長度為3的計算機程序”+…。把“所有長度為i的計算機程序”所成集合記為Si，“一切計算機程序”所成集合記為S，立即有：
。我們記Si中的第j個元素為Si(j)，那么很容易就可以建立S跟Z＋之間的injective function（單射），只須令f: Si(j)->2i3j;顯然f就是injective的。這就證明了S的可列性質(zhì)。
那么，這一結(jié)論有什么重要意義呢？非常重要，我們知道，實數(shù)集是不可列的，其勢（或稱“基”）為阿列夫1（而Z，即整數(shù)集的勢則是阿列夫0），所以即便耗盡所有圖靈機仍然還是會有“列不出”的實數(shù)。要想嚴格證明這一點也很簡單，只要運用cantor在證明集合論時運用的經(jīng)典的“對角線”手法，不妨簡單描述一下：
首先，既然所有圖靈機的集合是一可列集，我們就可以用M0,M1,M2,…來表示它們?，F(xiàn)在假設(shè)Mi能計算出的實數(shù)為Ai0.Ai1Ai2Ai3…。那么我們構(gòu)造一個新的實數(shù)B=B0.B1B2B3...，使其滿足B1≠A11,B2≠A22,B3≠A33,…,Bn≠Ann。這樣構(gòu)造出來的一個實數(shù)B可以保證不與任何Ai相等，同時這個B并不為任何圖靈機所計算出來（因為剛才的Ai序列已經(jīng)耗盡了所有的圖靈機）。這某種程度上就表明圖靈機的勢為阿列夫0（盡管對圖靈機并不能稱“勢”）。
除此之外，函數(shù)空間的所有函數(shù)也并不都是圖靈可計算的，一個函數(shù)為圖靈可計算其實就代表存在一個圖靈機可以模擬該函數(shù)的行為。這一結(jié)論通過剛才的證明就很好解釋了：因為函數(shù)空間的勢為阿列夫2，比實數(shù)集還要大，怎么可能由圖靈機來枚舉盡呢？要證明也很簡單，同樣是對角線法，就不說了。
那么，既然我們已經(jīng)從原則上肯定了有些函數(shù)是不可計算的，換句話說，有些函數(shù)你雖然知道它是函數(shù)，但你就是無法用圖靈機來將它模擬出來，用今天的話說，就是無法編程實現(xiàn)！這可比較令人沮喪，居然有無法編程實現(xiàn)的函數(shù)。那么究竟能否造出這么一個函數(shù)來讓人瞧瞧怎么個不能編程實現(xiàn)法呢？這就是所謂的Busy Beaver問題。Busy Beaver問題就是要構(gòu)造這么一個函數(shù)，它用于計算任意一個N-state的圖靈機的最大“生產(chǎn)率（Productivity）”，生產(chǎn)率的定義就是給一個圖靈機一條空紙帶，最終當該圖靈機halt的時候數(shù)紙帶上的1的個數(shù)，就是其生產(chǎn)率。所有N-state的圖靈機的最大生產(chǎn)率就是指一切N狀態(tài)的圖靈機的生產(chǎn)率中的最大者。很顯然，這是一個N的函數(shù)。記為L(n)。那么問題是，這個L(n)是否是圖靈可計算的？答案是不行！用反證法：假設(shè)存在這么一個圖靈機B，能夠模仿L(n)的行為，那么我們將它接到一個特殊的n-state的圖靈機I后面（I的作用是在紙帶上留下n個1，作為B的輸入，可以證明，這樣的I是存在的），這樣形成一個新的圖靈機IB，這個新的圖靈機的作用就是計算L(n)，其中n就是I的狀態(tài)數(shù)，也是I的輸出，B的輸入。我們再在后面接上一個B，得到IBB這么一個圖靈機，其效果為L(L(n))。那么現(xiàn)在考慮IBB自身的狀態(tài)數(shù)，是I的狀態(tài)數(shù)（即n）+2倍的B的狀態(tài)數(shù)，假設(shè)B的狀態(tài)數(shù)為b（b為有限值），那么IBB的狀態(tài)數(shù)就是n+2b，那么可想而知n+2b狀態(tài)的圖靈機的最大productivity是肯定大于等于L(L(n))的，因為已經(jīng)有一個圖靈機的productivity是L(L(n))了，它就是IBB。這個不等式就是 L(n+2b)>=L(L(n))，由此我們可以推出n+2b>=L(n)（L(i)>=L(j)=>i>=j這一結(jié)論易證），又根據(jù)n的任意性，我們可以令其等于n+11，于是得 n+11+2b>=L(n+11)，而我們知道11狀態(tài)可以實現(xiàn)出一個將紙帶上的1的數(shù)目翻倍的這樣一個圖靈機（試試看吧:)很簡單），于是L(n+11)>=2n（只要把前面的n狀態(tài)用于一個產(chǎn)生n個1的圖靈機，后面的11狀態(tài)做成一個翻倍1的數(shù)目的圖靈機即可），于是得到n+11+2b>=2n，于是得到11+2b>=n。根據(jù)n的任意性，b的有限性，這就得到了矛盾！（其實這里還隱含著另一層意思，即要實現(xiàn)這么一個圖靈機，必須要有無窮多個狀態(tài)才行，即b要任意大，而根據(jù)圖靈機的定義，b是有限的）。
說到這里，想起還有一個經(jīng)典的函數(shù)也是圖靈不可計算的。上面已經(jīng)提到，所有圖靈可計算的實數(shù)所構(gòu)成的集合是一可列集，記為S={s|s為圖靈可計算的}（這是因為所有圖靈機構(gòu)成的集合是可列集），現(xiàn)構(gòu)造這樣一個函數(shù)f，使得f(j,i)=Sj(i)；其中Sj就是S中的以j為下標的元素,Sj(i)則是指Sj的第i位的值。我們斷言這樣一個f就是圖靈不可計算的。欲證明這一點，我們假設(shè)存在一個圖靈機P，滿足P(j,i)=Sj(i)?，F(xiàn)使用對角線法構(gòu)造出一個新的不屬于集合S的實數(shù)r，r滿足：
我們發(fā)現(xiàn)，只要P存在，那么r就也是圖靈可計算的，而這又跟r不屬于S是矛盾的，所以推出“P不存在”這一結(jié)論。（注：為什么只要P存在r就也是圖靈可計算的呢？這樣想，我們構(gòu)造一個新的圖靈機Q，使?jié)M足：
這么個新的圖靈機Q，只要喂給它一個下標i，就會吐出r的第i位，于是r就成了圖靈可計算的了。
Church-Turing Thesis大意就是說，在所有以自然數(shù)為定義域的函數(shù)中，只有那些遞歸函數(shù)（這里遞歸函數(shù)也包括有限步驟的函數(shù)）才是圖靈可計算的。這一結(jié)論界定了圖靈機的計算能力。乃是非常重要的。其實想想也很直觀，一個無窮不循環(huán)的函數(shù)自然需要無窮多個狀態(tài)才能計算了。而一個圖靈機的狀態(tài)是有限的，在這個有限空間中轉(zhuǎn)來轉(zhuǎn)去最終肯定是墜入循環(huán)，這就好像兩整數(shù)相除一樣，要么除盡，要么無限循環(huán)小數(shù)，用鴿弄原理可以很容易地證明。
來簡單說說C++ Template的圖靈完備性（turing-complete，更準確地說是turing-equivalent，因為turing-complete一般是指一個問題是turing-computable的）。要想證明一門語言的圖靈完備性從原則上來說就是要證明它可以解決圖靈可計算的所有問題。或者構(gòu)造出一種轉(zhuǎn)換途徑，能夠把任何圖靈可計算問題的解決方法轉(zhuǎn)換為這門語言的程序。但這里還有一個更取巧的方法，用這門語言實現(xiàn)一個Universal Turing Machine（其實差不多就是有限狀態(tài)機啦）。C++ Template就可以做到這一點，實際上這早已有人做過了。另外，一般來說一門語言只要有if判斷，遞歸或循環(huán)結(jié)構(gòu)以及最基本的賦值能力和四則運算就是圖靈完備的了，而C++ Template恰巧這些都具備，其中if判斷和遞歸結(jié)構(gòu)是借助模板偏特化能力實現(xiàn)的，估計語言的設(shè)計者當初也沒有料到這一點會給現(xiàn)代C++帶來這么大的影響:)
另外，嚴格來說，現(xiàn)今任何計算機其實都不是turing-equivalent的，因為它們的內(nèi)存是有窮的。而圖靈機的內(nèi)存則是潛無窮的。只不過只要不出現(xiàn)內(nèi)存不耗盡的情況都一樣啦:)
前面提到的constructive mathematics和intuitive logic不屬于圖靈機的內(nèi)容，有空再寫吧。
P.S 圖靈機揭示了人類機械演算的深層機理，歌德爾的著名的不完備性定理跟圖靈機的停機問題就是等價的。用通俗的話來說其實就是“沒有全知全能的上帝”，這里上帝其實就隱喻在圖靈機算模型限制之下的公理體系。不過這又是另一個故事了，有時間再寫吧:)
