【正文】 l定義 69：通用圖靈機(jī)。machinel因此，應(yīng)該存在一個圖靈機(jī)，它可以實現(xiàn)對所有圖靈機(jī)的模擬，也就是說，該圖靈機(jī)可以實現(xiàn)所有有效的算法，稱該圖靈機(jī)為通用圖靈機(jī)（ universal直觀地，一臺通用的計算機(jī)，如果不受存儲空間和運(yùn)行時間的限制的話，它應(yīng)該能夠?qū)崿F(xiàn)所有的有效算法。l描述算法有三種基本方式：形式描述、實現(xiàn)描述和高水平描述。lTM等同于各種存儲指令的計算機(jī)系統(tǒng)。l定理：如果隨機(jī)存取機(jī) RAM的基本指令都能夠用圖靈機(jī)來實現(xiàn)，那么，就可以用圖靈機(jī)實現(xiàn)隨機(jī)存取 機(jī) RAM。l顯然，如果選擇一個適當(dāng)?shù)闹噶罴希S機(jī)存取機(jī) RAM就可以用來模擬任何的現(xiàn)代數(shù)字計算機(jī)。l隨機(jī)存取機(jī)含有無窮多個存儲單元，這些存儲單元按照 0， 1， 2， … 進(jìn)行編號，每個存儲單元可以存放一個任意整數(shù)。access從而對可計算性的實質(zhì)有了清楚的認(rèn)識?，F(xiàn)統(tǒng)稱為丘奇 —— 圖靈論點(diǎn)。于是這三類可計算函數(shù)實際上就是一種。l也就在 1936年，數(shù)學(xué)家圖靈定義了另一類可計算函數(shù) —— 圖靈可計算函數(shù)，并且提出了圖靈論點(diǎn)：能行可計算的函數(shù)都是用圖靈機(jī)可計算的函數(shù)。事隔不久，丘奇、克林就分別證明了 l可定義函數(shù)正好就是一般遞歸函數(shù)，即這兩類可計算函數(shù)是等價的、一致的。一般遞歸函數(shù)就是由初始函數(shù)出發(fā)，經(jīng)過有窮次使用代入、原始遞歸式和 m算子而做成的可定義函數(shù)。所謂原始遞歸函數(shù)是指由初始函數(shù)出發(fā)，經(jīng)過有限次的代入與原始遞歸式而做出的函數(shù)。l其中心問題是：計算的本質(zhì)是什么 ?哪些問題是可計算的 ?哪些問題是不可計算的 ?不可解的程度如何 ?這些問題經(jīng)過長期的探索，終于在本世紀(jì) 30年代由于遞歸論的建立而得到了確切地解決。l丘奇 —— 圖靈論點(diǎn)是遞歸論中最重要的基本結(jié)論。l 因為，只能列出算法的有限性、機(jī)械可執(zhí)行性、確定性、終止性等特征，即有效算法說明的可解性概念是非形式化的、不嚴(yán)格的，而圖靈機(jī)的概念卻是形式化的和嚴(yán)格的。l后來人們實際上是把這一論點(diǎn)看作是對直觀概念能行可計算的數(shù)學(xué)定義。因為這一論點(diǎn)原本就不是一條定理，其中包含了一個數(shù)學(xué)上意義不明確的概念 —— 能行可計算。不過這是由另一門學(xué)科—— 計算復(fù)雜性理論來研究的。當(dāng)然，這是從理論意義上來講的。 對于一般遞歸函數(shù)以外的函數(shù)，計算機(jī)是無法計算的。 該論題還沒有被嚴(yán)格的證明。1936年圖靈使用計算模型 — 圖靈機(jī)來描述（定義）算法。另一種觀點(diǎn)則忽略停機(jī)問題，從而擴(kuò)大了可計算問題的范圍。l根據(jù)這個觀點(diǎn)，對于某些輸入不能夠停機(jī)的圖靈機(jī)就不能夠稱為算法，也就是說，如果某個圖靈機(jī)使用永不停機(jī)的方式表示對某個輸入串不能夠接收的話，該圖靈機(jī)就不是算法；而只有對任何輸入都必定停機(jī)的圖靈機(jī)，才稱為算法。l6l一個任意的圖靈機(jī)可以被一個記數(shù)機(jī)模擬。l 用于計數(shù)的單向無窮帶上只能有兩種字符，一個為相當(dāng)于作為棧底符號的 Z，該字符也當(dāng)作是記數(shù)帶的首字符，它僅僅出現(xiàn)在記數(shù)帶的最左端；另一個就是空白字符 B，一條記數(shù)帶上所記的數(shù)就是該記數(shù)帶從 Z開始到該記數(shù)帶的讀 /寫頭當(dāng)前位置所包括的空白符號符號 B的個數(shù)。)是一種離線圖靈機(jī)，具有一條只讀輸入帶，和多條用于計數(shù)的單向無窮帶（存儲帶），用帶上讀頭到最左邊符號的距離（即單元的個數(shù)）表示所計的數(shù)。l5?計數(shù)機(jī)l計數(shù)機(jī) (counterl定理 68 stackl另外，存儲帶上的讀 /寫頭在向右移動時，一般情況下，應(yīng)該在當(dāng)前掃描的帶單元印刷上一個非空白符號（在特殊情況下，也可以印刷上一個空白 B，如下面介紹的計數(shù)機(jī)圖靈機(jī)）。 machine)具有一條只讀輸入帶，和多條模擬堆棧的存儲帶；輸入帶上的讀 /寫頭不能夠向左移動，存儲帶上可以印刷上規(guī)定的符號，并且存儲帶上的讀 /寫頭可以向左或向右進(jìn)行移動。l4?多棧機(jī)l下推自動機(jī)實際上相當(dāng)于非確定的多帶圖靈機(jī)，具有一條只讀輸入帶和一條存儲帶（模擬堆棧）。為了區(qū)別每個句子，每次產(chǎn)生一個句子，就在該句子后面印刷一個分隔符號（如 “”）。l如果輸出帶的讀 /寫頭的正常移動方向是向右的話，則輸出帶的讀 /寫頭不允許向左移動。出此之外，圖靈機(jī)還可以作為語言的產(chǎn)生模型。l3最簡單的方法是讓離線圖靈機(jī) M′比基本圖靈機(jī) M多一條輸入帶，用以復(fù)制基本圖靈機(jī)的輸入串，然后將該輸入帶當(dāng)作是基本圖靈機(jī)的輸入帶，模擬基本圖靈機(jī)進(jìn)行相應(yīng)的處理。l定理 67l離線圖靈機(jī)與基本圖靈機(jī)等價。machine)。l如果只允許離線圖靈機(jī)的讀 /寫頭從左向右進(jìn)行移動，稱這種離線圖靈機(jī)為在線圖靈機(jī) (onlinel通常使用符號￠和＄標(biāo)記離線圖靈機(jī)的只讀輸入帶的左、右端點(diǎn)，只允許離線圖靈機(jī)的讀 /寫頭在￠和＄標(biāo)記的區(qū)域內(nèi)來回進(jìn)行移動。 Turing多頭圖靈機(jī)與基本圖靈機(jī)等價。l定理 66 Turingl在多頭圖靈機(jī)的一個動作中，各個讀 /寫頭在輸入帶上所印刷的新符號和所移動的方向都可以是相互獨(dú)立的。l多頭圖靈機(jī)的多個讀 /寫頭，統(tǒng)一地受圖靈機(jī)的狀態(tài)控制器的控制。 Turing其他圖靈機(jī)l1machine）。l如果圖靈機(jī)的讀 /寫頭可以沿著 k維移動，該圖靈機(jī)稱為 k維圖靈機(jī)（ kdemensionalTuring也就是說，圖靈機(jī)的輸入帶要么是只可以向右無限延長的，要么是只可以向左或向右無限延長的，因而，圖靈機(jī)的讀 /寫頭只能夠向前或向后進(jìn)行移動。l定理 65l不確定的圖靈機(jī)和確定的圖靈機(jī)是等價的。定理 64l若語言 L能被不確定的圖靈機(jī)所識別，則存在確定的圖靈機(jī) M，有 L(M)=L。l對于不確定圖靈機(jī) M， 一方面可以認(rèn)為，對于給定的輸入串， M能夠自動地選擇一系列正確的動作，使得 M能夠最終進(jìn)入接收狀態(tài)，即不確定的圖靈機(jī) M具有具有一定的 “智能 ”。q0， q0， 即對于某個狀態(tài) q和掃描到的帶上符號 x， 圖靈機(jī)可能有多個動作（即 M的狀態(tài)轉(zhuǎn)換函數(shù) δ可能將 Q∑′映射到 Q∑′{L， R， N}的一個子集上）。l確定有限狀態(tài)自動機(jī) DFA可以向非確定有限狀態(tài)自動機(jī) NFA的進(jìn)行擴(kuò)展，類似地，確定的圖靈機(jī)也能夠擴(kuò)展為非確定的圖靈機(jī)。q′， W ， {L， R， N})l稱該圖靈機(jī)是確定的圖靈機(jī)。q0， 由于基本圖靈機(jī)是多帶圖靈機(jī)的一個特例，所以，只需要證明：對于任意一個多帶圖靈機(jī)，都有一個與之等價的基本圖靈機(jī)。l多帶圖靈機(jī)與基本圖靈機(jī)等價。l多帶圖靈機(jī)的一個動作可以描述為：l1)改變圖靈機(jī)當(dāng)前的狀態(tài)；l2)在各自的輸入帶上印刷一個符號；l3)各個讀 /寫頭向各自希望的方向進(jìn)行移動。Turing machine)。l雙向多帶多讀 /寫頭圖靈機(jī)簡稱為多帶圖靈機(jī) (multitape這種雙向的多輸入帶圖靈機(jī)具有多條雙向的無窮輸入帶，每一個輸入帶都有自己的讀 /寫頭。多帶多讀 /寫頭圖靈機(jī) 如果語言 L能夠被一個雙向無窮帶圖靈機(jī)所接收，則該語言 L也能夠被一個單向無窮帶圖靈機(jī)（即基本圖靈機(jī)）所接收。 l雙向無窮帶圖靈機(jī)，讀寫頭可以向左或向右任意移動，其他定義與基本圖靈機(jī)的一致。輸入帶上所有空單元（包括左邊和右邊，全部標(biāo)記為 B）。所以，對于基本的圖靈機(jī)，讀 /寫頭是不能夠向左移動出該左端點(diǎn)的。l這與本書前面的較為嚴(yán)格的論述不同。對基本的圖靈機(jī)進(jìn)行擴(kuò)展，使得構(gòu)造復(fù)雜的圖靈機(jī)變得更加簡便和容易。l為了區(qū)別擴(kuò)展的圖靈機(jī)，上面介紹的單向無窮帶圖靈機(jī)，稱為基本圖靈機(jī)。直觀地，一臺通用的計算機(jī)，如果不受存儲空間和運(yùn)行時間的限制的話，它應(yīng)該能夠?qū)崿F(xiàn)所有的有效算法。l描述算法有三種基本方式：形式描述、實現(xiàn)描述和高水平描述。l從現(xiàn)實意義上講，計算機(jī)還有一個現(xiàn)實可計算性的問題。l丘奇 —— 圖靈論點(diǎn)常常又被說成：凡可計算的函數(shù)都可用計算機(jī)計算?？梢哉f，遞歸性是使用計算機(jī)的前提。l對于計算機(jī)科學(xué)，丘奇 —— 圖靈論點(diǎn)的意義是很直接的，它明確刻畫了計算機(jī)的本質(zhì)或計算機(jī)的計算能力，確定了計算機(jī)只能計算一般遞歸函數(shù)。l丘奇 圖靈論題（又稱為丘奇假說）：l至此，人們便把直觀的能行可計算函數(shù)歸結(jié)為一般遞歸函數(shù)了。 這樣一來，丘奇論點(diǎn)和圖靈論點(diǎn)也就是一回事了。l一年后，圖靈進(jìn)一步證明了圖靈可計算函數(shù)與 l可定義函數(shù)是等價的．l當(dāng)然也和一般遞歸函數(shù)是等價的。l在這一有力的證據(jù)基礎(chǔ)之上，丘奇公開發(fā)表了他早在 1934年就孕育過的一個論點(diǎn) 即著名的丘奇論點(diǎn)： 每個能行可計算的函數(shù)是一般遞歸的。l同時，數(shù)學(xué)家丘奇、克林也提出了一類可計算的叫做 l可定義的函數(shù)。l1934年哥德爾在他人的啟示下，又提出了 一般遞歸函數(shù) 的概念。l遞歸論的建立首先得益于 哥德爾 等人關(guān)于原始遞歸函數(shù)的提出。l遞歸論又稱可計算性理論，它是研究計算的一般性質(zhì)的數(shù)學(xué)理論。l另一種觀點(diǎn)則忽略停機(jī)問題，從而擴(kuò)大了可計算問題的范圍。l根據(jù)這個觀點(diǎn)，對于某些輸入不能夠停機(jī)的圖靈機(jī)就不能夠稱為算法，也就是說，如果某個圖靈機(jī)使用永不停機(jī)的方式表示對某個輸入串不能夠接收的話，該圖靈機(jī)就不是算法；l而只有對任何輸入都必定停機(jī)的圖靈機(jī)，才稱為算法。對于任何輸入， 算法 都應(yīng)該能夠終止q q1 q1 q1 q14教學(xué)活動結(jié)束 主程序圖靈機(jī)使用了 12個狀態(tài)：q q q q q5l圖靈機(jī)共有 15個狀態(tài)，其中：Bm+n+1+10mnm個 0都消完，循環(huán)結(jié)束消去多余串 10n1:q10， 1， q11， B， Rq11， 0， q11， B， Rq11， 1， q14， B， N此時，圖靈機(jī)帶上的符號形式為： 上一次循環(huán)結(jié)束，本次循環(huán)開始q8， B， q10， B， R子程序結(jié)束，讀 /寫頭仍然在 0n的第一個 0處主程序：q5， 0， q7， 0， Lq7， 1， q8， 1， Lq8， 0， q9， 0， Lq9， 0， q9， 0， Lq9， B， q0， B， Rn個 0都已復(fù)制q4， 2， q4， 0， L準(zhǔn)備復(fù)制下一個 0q1， 1， q4， 1， Lq3， 2， q1， 2， Rq3， 1， q3， 1， L復(fù)制一個 0向左尋找 0n中剩余的 0（尋找標(biāo)記 2）遇到標(biāo)記 1（第二個 1）q2， B， q3， 0， L將 0標(biāo)記為 2，以方便復(fù)制 0nq2， 0， q2， 0， R此時，將掃描原來 0n的第一個 0子程序：q1， 0， q2， 2， R主程序消除多余符號初始化 (不止執(zhí)行一次 )：q0， 0， q6， B， Rq6， 0， q6， 0， Rq6， 1， q12， 1， Rq12， 0， q12， 0， Rq12， B， q13， 1， L//在最后增加標(biāo)記 1q12， 1， q13， 1， L主程序消除 0Bmq810n10m*n=*Bm+n+1+1q140m*n子程序增加 0nBh0mh1q50n10h*n主程序消除 0Bh0mh1q10n10(h1)*n=*Bh0mh1q10n10(h1)*nq00m10n=*初始化：=*Bh0mh1q50n10h*nl整個圖靈機(jī)的格局轉(zhuǎn)換情況：讀 /寫頭指向 0n的第一個 0l子程序?qū)?yīng)的格局轉(zhuǎn)換為：l進(jìn)入圖靈機(jī)子程序時，輸入帶上符號串的形式情況及讀 /寫頭位置為：子程序 TM從它的開始狀態(tài) q1啟動，Bmq810n10m*n=*Bm+n+1+1q140m*n其中，狀態(tài) q14是接收狀態(tài)l3)子程序：得到最后的結(jié)果串。Bh0mh1q50n10h*n 進(jìn)入子程序=*Bh0mh1q10n10并將這個 0改為 B，準(zhǔn)備進(jìn)入下次循環(huán)對應(yīng)的格局轉(zhuǎn)換為：Bhq00mh10n10(h1)*n 當(dāng)退出子程序時，狀態(tài)為 q5（ q5也就是子程序圖靈機(jī)的結(jié)束狀態(tài)） 進(jìn)入子程序，將 n個 0增加到第