圖靈機(jī)雜思(增改)

                                   劉未鵬 /文

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

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

圖 靈機(jī)是圖靈為了研究可計(jì)算問題而構(gòu)思的一個(gè)理論裝置，你只要想一想有限狀態(tài)機(jī)就可以大概知道圖靈機(jī)是個(gè)什么概念了，只不過圖靈機(jī)的內(nèi)存（紙帶）是潛無窮的 （也就是可以任意長(zhǎng)啦，“潛無窮”是古稀蠟人的說辭）。圖靈機(jī)的定義形象的說來就像老式的電傳機(jī)：一個(gè)讀寫頭，一根紙帶（可能任意長(zhǎng)），讀寫頭不斷讀取紙 帶上的符號(hào)，并根據(jù)內(nèi)在的狀態(tài)轉(zhuǎn)換規(guī)則轉(zhuǎn)換當(dāng)前狀態(tài)，同時(shí)進(jìn)行一些動(dòng)作，譬如插除或改寫當(dāng)前字符，向前/向后移動(dòng)讀寫頭或保持不動(dòng)等。至于其抽象的定義大抵就是有限狀態(tài)機(jī)的定義了。圖靈機(jī)的這一定義現(xiàn)在我們看起來似乎是很顯然的，然而當(dāng)時(shí)卻代表著一種思想上的革命，一種從無到有。圖靈機(jī)實(shí)質(zhì)上抽象出了我們平素進(jìn)行機(jī)械式計(jì)算的核心規(guī)律，所以才等價(jià)于“一個(gè)人+紙筆+一定的規(guī)則”進(jìn)行機(jī)械運(yùn)算呢。這么個(gè)理論機(jī)器首先就指明了創(chuàng)建計(jì)算機(jī)的可能性，然而這還不夠，如果為了某一個(gè)問題就去創(chuàng)建一個(gè)特定的圖靈機(jī)的話效率就太低了。圖靈機(jī)理論的一個(gè)最美妙的結(jié)論就是存在“元圖靈機(jī)（Universal Turing-Machine，直譯應(yīng)為一般圖靈機(jī)/通用圖靈機(jī)，然而“元圖靈機(jī)”更精確地表達(dá)了其意思），所謂元圖靈機(jī)其實(shí)就是把圖靈機(jī)作為運(yùn)算對(duì)象的圖靈機(jī)，假設(shè)有一個(gè)元圖靈機(jī)M，一個(gè)圖靈機(jī)P以及P的輸入數(shù)據(jù)D，那么將(P,D)喂給元圖靈機(jī)M，M就能夠吐出P(D)（即P在D上的結(jié)果）。而這便是現(xiàn)在我們所用的計(jì)算機(jī)的始祖模型，其中M就好比我們的計(jì)算機(jī)（元圖靈機(jī)），P則是程序（編碼后的圖靈機(jī)），D則是程序P的輸入數(shù)據(jù)。元圖靈機(jī)的存在表明了我們可以用一臺(tái)機(jī)器來解決所有圖靈可計(jì)算（turing-computable）的問題——只要喂給它解決這個(gè)特定問題的圖靈機(jī)編碼（程序）以及問題的輸入數(shù)據(jù)即可，該元圖靈機(jī)就會(huì)模擬我們喂給它的那個(gè)圖靈機(jī)P的行為，最終給出結(jié)果。元圖靈機(jī)的存在性為計(jì)算機(jī)的誕生點(diǎn)燃了一盞明燈，這是圖靈機(jī)理論中最漂亮的發(fā)現(xiàn)。

圖1. 元圖靈機(jī)

關(guān)于圖靈機(jī)還有兩個(gè)有名的Halt Problem和Busy Beaver Problem，不過前者更有名，但沒有后者有意思，所以具體就不說了，可以google。 這兩個(gè)問題說明了圖靈機(jī)并不是“萬能”的，它只能解決可以“機(jī)械地”解決的問題，只不過這個(gè)“機(jī)械地”定義太過含糊，沒有準(zhǔn)確地界定，所以有必要精確定義 一下圖靈機(jī)到底能解決哪些問題，換句話說，到底哪些問題是圖靈可計(jì)算的。這里有一個(gè)非常漂亮的證明，是關(guān)于哪些數(shù)是圖靈可計(jì)算的，說有無窮多個(gè)實(shí)數(shù)是圖靈 不可計(jì)算的。首先說明一下一個(gè)數(shù)是圖靈可計(jì)算的是個(gè)什么概念，一個(gè)數(shù)是圖靈可計(jì)算的就是說存在一個(gè)圖靈機(jī)，給它一個(gè)空紙帶，最終它能打印出任意逼近該數(shù)的 結(jié)果。像pi、自然常數(shù)E以及所有多項(xiàng)式的根就都是圖靈可計(jì)算的（可由機(jī)械步驟任意逼近），這很好理解，因?yàn)槲覀兛梢詫懸粋€(gè)程序來迭代任意逼近它們，譬如E就是一個(gè)無窮級(jí)數(shù)的和。但還有其它實(shí)數(shù)呢？有沒有圖靈不可計(jì)算的實(shí)數(shù)？要想弄明白這個(gè)問題，先要考慮一共存在多少個(gè)圖靈機(jī)（廢話，當(dāng)然是無窮多個(gè)了，但“無窮多”也有一個(gè)級(jí)別問題J），為此先將圖靈機(jī)進(jìn)行編碼，由于圖靈機(jī)的狀態(tài)是有限的，將圖靈機(jī)編碼為一個(gè)五元組（5-tuple）（Old_State,Symbol,New_State,New_Symbol,Move）的序列（或更多/更少都有可能，這是比較常見的一種編碼方式，但總之一定是N-TUPLE，N有限），那么我們來考慮一個(gè)N-state(N個(gè)狀態(tài))，M-symbol的圖靈機(jī)一共有多少種可能，為此，先考慮對(duì)應(yīng)N-state、M-symbol的5-tuple（見上面的定義）有多少個(gè)，根據(jù)簡(jiǎn)單的排列組合規(guī)律，一共是N*M*N*M*3（最后一個(gè)3是指Move的可能性——靜止/向前/向后），換句話說，也就是以M,N為參數(shù)的一個(gè)upper-bounded function。OK，現(xiàn)在來考慮一個(gè)圖靈機(jī)的編碼形式，一個(gè)圖靈機(jī)其實(shí)就是由一集5-tuple所構(gòu)成，所以既然N-state,M-symbol的5-tuple一共有N*M*N*M*3個(gè)，換句話說，這個(gè)由所有可能的5-tuple所構(gòu)成的集合中一共有N*M*N*M*3個(gè)元素，那么這個(gè)集合的所有子集合的個(gè)數(shù)也就是N-state,M-symbol的所有圖靈機(jī)的個(gè)數(shù)，根據(jù)冪集的定義，這也就是2^N*M*N*M*3個(gè)。這里為了簡(jiǎn)單起見，我們暫且固定M為M­­₀，即symbol的個(gè)數(shù)，這樣所有M₀-state的圖靈機(jī)的個(gè)數(shù)就是:

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

現(xiàn)在我們看到，這個(gè)和式的每一項(xiàng)都是coutable的，而Z_＋×Z_＋尚且是可列集，就別說這里每項(xiàng)都有限的情況了，所以很容易就可以和Z_＋建立起單射(injective)，換句話說，所有M₀-state的圖靈機(jī)的集合是一個(gè)可列集。好了，現(xiàn)在把M₀換成變量，既然所有M_0－state的圖靈機(jī)集合都是可列的，而M₀又是自然數(shù)（可列集），再加上“可列集個(gè)可列集”仍然是可列集這一性質(zhì)，就容易得出一切圖靈機(jī)構(gòu)成的集合是可列集這一結(jié)論了。

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

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

首先，既然所有圖靈機(jī)的集合是一可列集，我們就可以用M₀,M₁,M₂,…來表示它們?，F(xiàn)在假設(shè)M_i能計(jì)算出的實(shí)數(shù)為A_i0.A_i1A_i2A_i3…。那么我們構(gòu)造一個(gè)新的實(shí)數(shù)B=B₀.B₁B₂B₃...，使其滿足B₁≠A₁₁,B₂≠A₂₂,B₃≠A₃₃,…,B_n≠A_nn。這樣構(gòu)造出來的一個(gè)實(shí)數(shù)B可以保證不與任何A_i相等，同時(shí)這個(gè)B并不為任何圖靈機(jī)所計(jì)算出來（因?yàn)閯偛诺?span lang="EN-US">A_i序列已經(jīng)耗盡了所有的圖靈機(jī)）。這某種程度上就表明圖靈機(jī)的勢(shì)為阿列夫0（盡管對(duì)圖靈機(jī)并不能稱“勢(shì)”）。

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

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

說到這里，想起還有一個(gè)經(jīng)典的函數(shù)也是圖靈不可計(jì)算的。上面已經(jīng)提到，所有圖靈可計(jì)算的實(shí)數(shù)所構(gòu)成的集合是一可列集，記為S={s|s為圖靈可計(jì)算的}（這是因?yàn)樗袌D靈機(jī)構(gòu)成的集合是可列集），現(xiàn)構(gòu)造這樣一個(gè)函數(shù)f，使得f(j,i)=S_j(i)；其中S_j就是S中的以j為下標(biāo)的元素,S_j(i)則是指S_j的第i位的值。我們斷言這樣一個(gè)f就是圖靈不可計(jì)算的。欲證明這一點(diǎn)，我們假設(shè)存在一個(gè)圖靈機(jī)P，滿足P(j,i)=S_j(i)?，F(xiàn)使用對(duì)角線法構(gòu)造出一個(gè)新的不屬于集合S的實(shí)數(shù)r，r滿足：

我們發(fā)現(xiàn)，只要P存在，那么r就也是圖靈可計(jì)算的，而這又跟r不屬于S是矛盾的，所以推出“P不存在”這一結(jié)論。（注：為什么只要P存在r就也是圖靈可計(jì)算的呢？這樣想，我們構(gòu)造一個(gè)新的圖靈機(jī)Q，使?jié)M足：

這么個(gè)新的圖靈機(jī)Q，只要喂給它一個(gè)下標(biāo)i，就會(huì)吐出r的第i位，于是r就成了圖靈可計(jì)算的了。

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

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

另外，嚴(yán)格來說，現(xiàn)今任何計(jì)算機(jī)其實(shí)都不是turing-equivalent的，因?yàn)樗鼈兊膬?nèi)存是有窮的。而圖靈機(jī)的內(nèi)存則是潛無窮的。只不過只要不出現(xiàn)內(nèi)存不耗盡的情況都一樣啦:)

前面提到的constructive mathematics和intuitive logic不屬于圖靈機(jī)的內(nèi)容，有空再寫吧。

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