【正文】 那些比較煩瑣的描述，包括一些形式化的描述。l這與本書前面的較為嚴格的論述不同。但是，根據(jù)基本思想和基本方法的介紹，讀者較容易給出相應的形式化的描述和嚴格的證明，只不過這些形式化的描述和嚴格的證明，比較煩瑣而已。雙向無窮帶圖靈機l基本的圖靈機的模型中，輸入帶上規(guī)定有左端點。所以，對于基本的圖靈機，讀 /寫頭是不能夠向左移動出該左端點的。l對基本圖靈機取消左端點的限制，得到雙向無窮帶圖靈機，雙向無窮帶圖靈機的輸入帶向左和向右都是無限的。輸入帶上所有空單元（包括左邊和右邊，全部標記為 B）。 l雙向無窮帶圖靈機，讀寫頭可以向左或向右任意移動，其他定義與基本圖靈機的一致。l定理 62l 如果語言 L能夠被一個雙向無窮帶圖靈機所接收，則該語言 L也能夠被一個單向無窮帶圖靈機（即基本圖靈機）所接收。多帶多讀 /寫頭圖靈機 l基本圖靈機的另一個重要的擴展是雙向多帶多讀 /寫頭圖靈機。這種雙向的多輸入帶圖靈機具有多條雙向的無窮輸入帶，每一個輸入帶都有自己的讀 /寫頭。l在每一個動作中，圖靈機根據(jù)當前的狀態(tài)以及每個讀 /寫頭正在掃描的帶上符號確定圖靈機的下一個狀態(tài)，并且各個讀 /寫頭可以相互獨立地向各自希望的方向進行移動。l雙向多帶多讀 /寫頭圖靈機簡稱為多帶圖靈機 (multitape Turing machine)。將具有 K條輸入帶的圖靈機簡稱 為 K帶圖靈機 (KtapeTuringmachine)。l多帶圖靈機的一個動作可以描述為：l1)改變圖靈機當前的狀態(tài)；l2)在各自的輸入帶上印刷一個符號；l3)各個讀 /寫頭向各自希望的方向進行移動。lK帶圖靈機的狀態(tài)轉換函數(shù)的形式為：lδ(p， (X1， X2， X3， … ， Xk))=(q，[Y1， D1]， [Y2， D2]， [Y3， D3]， …， [Yk， Dk])定理 63l多帶圖靈機與基本圖靈機等價。l證明：l由于基本圖靈機是多帶圖靈機的一個特例，所以，只需要證明：對于任意一個多帶圖靈機，都有一個與之等價的基本圖靈機。l略。不確定圖靈機l對于前面介紹的圖靈機是一個五元式， TM=(Q， ∑， q0， qα， δ）；l其中：lδ是 Q∑′→Q∑′{L ， R， N}的狀態(tài)轉換函數(shù)：lδ（ q， x） =(q′， W ， {L， R， N})l稱該圖靈機是確定的圖靈機。l對于一個給定的狀態(tài)和讀入符號，確定的圖靈機只能有一種可選動作。l確定有限狀態(tài)自動機 DFA可以向非確定有限狀態(tài)自動機 NFA的進行擴展，類似地，確定的圖靈機也能夠擴展為非確定的圖靈機。定義 67l圖靈機 M稱為不確定的圖靈機（或非確定的圖靈機），除狀態(tài)轉換函數(shù) δ的定義外，它的其余部分的定義同確定的圖靈機。即對于某個狀態(tài) q和掃描到的帶上符號 x， 圖靈機可能有多個動作（即 M的狀態(tài)轉換函數(shù) δ可能將 Q∑′映射到 Q∑′{L， R， N}的一個子集上）。l不確定的圖靈機是一個五元式， TM=（ Q， ∑， q0， qα， δ）；l其中：lQ是有限狀態(tài)集合；l∑是帶上字母表的有限集合，用∑′=∑U{B}代表 ∑的增廣集合；lq0∈ Q， 是開始狀態(tài)；lqα∈ Q， 是接收狀態(tài)；lδ是 Q∑′→2Q∑′{L ， R， N}的狀態(tài)轉換函數(shù)，即對于任意的：（ q， X）∈ Q∑′，lδ（ q， X） ={(q1， Y1， D1)， (q2，Y2， D2)， … ， (qn， Yn， Dn)}定義 68l不確定圖靈機 M=（ Q， ∑， q0， qα，δ） 在字母表 ∑上接收的語言為 L(M)，則lL(M)={w|w∈ ∑*， 且存在 w1，w2∈ (∑′)*，有 q0w=*w1qαw2}。l對于不確定圖靈機 M， 一方面可以認為，對于給定的輸入串， M能夠自動地選擇一系列正確的動作，使得 M能夠最終進入接收狀態(tài)，即不確定的圖靈機 M具有具有一定的 “智能 ”。l另一方面，由于處理一個輸入串的所有可能的動作系列都是可以逐個列舉的，所以，對于任意的輸入串，可以讓不確定的圖靈機 M逐一地按照當前列舉出的動作系列去處理該輸入串，l如果該輸入串是不確定圖靈機 M所能夠識別的串（即該輸入串是不確定圖靈機 M接收語言的句子），則 M最終能夠執(zhí)行接收該輸入串的動作系列，不確定圖靈機與確定圖靈機的等價性證明就是基于這一思想的。定理 64l若語言 L能被不確定的圖靈機所識別，則存在確定的圖靈機 M，有 L(M)=L。l證明：l需要證明，對于任意一個不確定的圖靈機，都存在一個與之等價的確定的基本圖靈機。l定理 65l不確定的圖靈機和確定的圖靈機是等價的。l證明：l略。多維圖靈機l前面接觸過的圖靈機的輸入帶都是一維的。也就是說，圖靈機的輸入帶要么是只可以向右無限延長的，要么是只可以向左或向右無限延長的，因而，圖靈機的讀 /寫頭只能夠向前或向后進行移動。l現(xiàn)在，將圖靈機的輸入帶擴展為多維的，這種圖靈機的讀 /寫頭可以沿著多個維移動，該圖靈機稱為多維圖靈機（multidemensionalTuringmachine）。l如果圖靈機的讀 /寫頭可以沿著 k維移動，該圖靈機稱為 k維圖靈機（ kdemensionalTuringmachine）。lk維圖靈機可以轉換為一維圖靈機。其他圖靈機l1多頭圖靈機l多頭圖靈機 (multihead Turingmachine)是指圖靈機只有一條輸入帶，但有多個讀 /寫頭。l多頭圖靈機的多個讀 /寫頭，統(tǒng)一地受圖靈機的狀態(tài)控制器的控制。多頭圖靈機根據(jù)當前的狀態(tài)和多個讀 /寫頭當前掃描的多個字符，確定當前多頭圖靈機的一個動作。l在多頭圖靈機的一個動作中，各個讀 /寫頭在輸入帶上所印刷的新符號和所移動的方向都可以是相互獨立的。l如果多頭圖靈機有 K個讀 /寫頭，該圖靈機稱為 k頭圖靈機（ khead Turingmachine）。l定理 66l多頭圖靈機與基本圖靈機等價。l證明：l2離線圖靈機l離線圖靈機 (offline Turing machine)是一種多帶圖靈機，但對于其中一條輸入帶，只能讀，不能印刷上符號（即不能寫）。l通常使用符號￠和＄標記離線圖靈機的只讀輸入帶的左、右端點，只允許離線圖靈機的讀 /寫頭在￠和＄標記的區(qū)域內來回進行移動。l離線圖靈機實際上是多帶圖靈機的一個特例。l如果只允許離線圖靈機的讀 /寫頭從左向右進行移動，稱這種離線圖靈機為在線圖靈機 (onlineTuringmachine)。l雖然離線圖靈機是多帶圖靈機的一個特例，但離線圖靈機卻能夠模擬任何一個圖靈機。l定理 67l離線圖靈機與基本圖靈機等價。l 證明：l 對于基本圖靈機 M，構造離線圖靈機 M′模擬 M。最簡單的方法是讓離線圖靈機 M′比基本圖靈機 M多一條輸入帶，用以復制基本圖靈機的輸入串，然后將該輸入帶當作是基本圖靈機的輸入帶，模擬基本圖靈機進行相應的處理。l 具體證明過程略。l3作為枚舉器的圖靈機l圖靈機是遞歸可枚舉語言的識別器和非負整函數(shù)的計算器。出此之外，圖靈機還可以作為語言的產生模型。l產生語言的圖靈機稱為作為枚舉器的圖靈機，是一個特殊的多帶（多頭）的圖靈機，其中一個帶專門作為輸出帶，并且規(guī)定，一旦一個字符被印刷在輸出帶上，就不能再被更改。l如果輸出帶的讀 /寫頭的正常移動方向是向右的話，則輸出帶的讀 /寫頭不允許向左移動。l基本的圖靈機每次啟動后，只處理輸入帶的一個輸入串（即對于多個串，需要多次啟動）；而作為枚舉器的圖靈機，在啟動之后，在輸出帶上將產生相應語言的每一個句子。為了區(qū)別每個句子，每次產生一個句子，就在該句子后面印刷一個分隔符號（如 “”）。l注意：l如果作為枚舉器的圖靈機產生的語言是一個無窮的語言，則作為枚舉器的圖靈機將永不停機。l4?多棧機l下推自動機實際上相當于非確定的多帶圖靈機，具有一條只讀輸入帶和一條存儲帶（模擬堆棧）。l多棧機 (multistack machine)具有一條只讀輸入帶，和多條模擬堆棧的存儲帶；輸入帶上的讀 /寫頭不能夠向左移動，存儲帶上可以印刷上規(guī)定的符號，并且存儲帶上的讀 /寫頭可以向左或向右進行移動。l需要注意的是，存儲帶上的讀 /寫頭在向左移動時，必須在當前掃描的帶單元中印刷上空白符號 B， 因此，存儲帶上的讀 /寫頭在向左移動時，該讀 /寫頭的右部全是空白符號 B（ 將當前的單元作為了棧頂）。l另外，存儲帶上的讀 /寫頭在向右移動時，一般情況下，應該在當前掃描的帶單元印刷上一個非空白符號（在特殊情況下，也可以印刷上一個空白 B，如下面介紹的計數(shù)機圖靈機）。l一個確定的雙棧機 (double stackmachine)是一個確定的圖靈機，具有一條只讀輸入帶和兩條模擬堆棧的存儲帶；存儲帶上的讀 /寫頭向左移動時，只能印刷上空白符號 B。l定理 68l一個任意的單帶圖靈機可以被一個確定的雙棧機模擬。l5?計數(shù)機l計數(shù)機 (countermachine)是一種離線圖靈機，具有一條只讀輸入帶，和多條用于計數(shù)的單向無窮帶（存儲帶），用帶上讀頭到最左邊符號的距離（即單元的個數(shù)）表示所計的數(shù)。l一個具有 n條用于計數(shù)的帶的計數(shù)機稱為 n計數(shù)機。l 用于計數(shù)的單向無窮帶上只能有兩種字符，一個為相當于作為棧底符號的 Z，該字符也當作是記數(shù)帶的首字符，它僅僅出現(xiàn)在記數(shù)帶的最左端；另一個就是空白字符 B，一條記數(shù)帶上所記的數(shù)就是該記數(shù)帶從 Z開始到該記數(shù)帶的讀 /寫頭當前位置所包括的空白符號符號 B的個數(shù)。l定理 69l一個任意的圖靈機可以被一個記數(shù)機模擬。l證明：l略。l6丘奇 圖靈論題與隨機存取機l在研究可計算性問題時，一種觀點認為：對于任何的輸入，算法都應該能夠終止，否則，只能稱其為 (計算 )過程。l根據(jù)這個觀點，對于某些輸入不能夠停機的圖靈機就不能夠稱為算法，也就是說，如果某個圖靈機使用永不停機的方式表示對某個輸入串不能夠接收的話，該圖靈機就不是算法；而只有對任何輸入都必定停機的圖靈機，才稱為算法。l或者說，接收遞歸語言的圖靈機是算法，接收遞歸可枚舉語言的圖靈機不一定是算法。另一種觀點則忽略停機問題，從而擴大了可計算問題的范圍。l1934年，丘奇使用稱為 λ演算的記號系統(tǒng)來定義算法； 1936年圖靈使用計算模型 — 圖靈機來描述（定義）算法。l丘奇 圖靈論題（又稱為丘奇假說）：對于任何可以用有效算法解決的問題，都存在解決此問題的圖靈機。 該論題還沒有被嚴格的證明。l對于計算機科學， 丘奇 —— 圖靈論點的意義是很直接的，它明確刻畫了計算機的本質或計算機的計算能力，確定了計算機只能計算一般遞歸函數(shù)。對于一般遞歸函數(shù)以外的函數(shù)，計算機是無法計算的?？梢哉f，遞歸性是使用計算機的前提。 l因此，丘奇 —— 圖靈論點常常又被說成：凡可計算的函數(shù)都可用計算機計算。當然，這是從理論意義上來講的。從現(xiàn)實意義上講，計算機還有一個現(xiàn)實可計算性的問題。不過這是由另一門學科—— 計算復雜性理論來研究的。l需要說明的是，丘奇 —— 圖靈論點并不象哥德爾不完備性定理那樣能給出一個嚴格的數(shù)學證明。因為這一論點原本就不是一條定理，其中包含了一個數(shù)學上意義不明確的概念 —— 能行可計算。即一面是直觀的日常概念，另一面是明確的數(shù)學概念 (一般遞歸函數(shù) )，要證明二者是一致的，這是不可能的。l后來人們實際上是把這一論點看作是對直觀概念能行可計算的數(shù)學定義。既然是對一個不明確的概念給以明確的定義，這就無所謂正確與否， 因此用不著證明也無法證明。l 因為，只能列出算法的有限性、機械可執(zhí)行性、確定性、終止性等特征，即有效算法說明的可解性概念是非形式化的、不嚴格的，而圖靈機的概念卻是形式化的和嚴格的。但是，圖靈機作為人們普遍接受的計算模型，使得將算法集中在可以用圖靈機描述的計算上，因此，可以認為，可計算問題可以等同于圖靈機的可計算問題。l丘奇 —— 圖靈論點是遞歸論中最重要的基本結論。遞歸論又稱可計算性理論，它是研究計算的一般性質的數(shù)學理論。l其中心問題是：計算的本質是什么 ?哪些問題是可計算的 ?哪些問題是不可計算的 ?不可解的程度如何 ?這些問題經(jīng)過長期的探索，終于在本世紀 30年代由于遞歸論的建立而得到了確切地解決。l遞歸論的建立首先得益于哥德爾等人關于原始遞歸函數(shù)的提出。所謂原始遞歸函數(shù)是指由初始函數(shù)出發(fā)，經(jīng)過有限次的代入與原始遞歸式而做出的函數(shù)。1934年哥德爾在他人的啟示下，又提出了一般遞歸函數(shù)的概念。一般遞歸函數(shù)就是由初始函數(shù)出發(fā)，經(jīng)過有窮次使用代入、原始遞歸式和 m算子而做成的可定義函數(shù)。l同時，數(shù)學家丘奇、克林也提出了一類可計算的叫做 l可定義的函數(shù)。事隔不久，丘奇、克林就分別證明了 l可定義函數(shù)正好就是一般遞歸函數(shù)，即這兩類可計算函數(shù)是等價的、一致的。在這一有力的證據(jù)基礎之上，丘奇公開發(fā)表了他早在 1934年就孕育過的一個論點，即著名的丘奇論點：每個能行地可計算的函數(shù)都是一般遞歸的。l也就在 1936年，數(shù)學家圖靈定義了另一類可計算函數(shù) —— 圖靈可計算函數(shù)，并且提出了圖靈論點：能行可計算的函數(shù)都是用圖靈機可計算的函數(shù)。一年后，圖靈進一步證明了圖靈可計算函數(shù)與l可定義函數(shù)是等價的．l當然也和一般遞歸函數(shù)是等價的。于是這三類可計算函數(shù)實際上就是一種。這樣一來，丘奇論點和圖靈論點也就是一回事了?，F(xiàn)統(tǒng)稱為丘奇 —— 圖靈論點。至此，人們便把直觀的能行可計算函數(shù)歸結為一般遞歸函數(shù)了。從而對可計算性的實質有了清楚的認識。l隨機存取機 (randomaccessmachineRAM)是更接近現(xiàn)代數(shù)字計算機的（圖靈機）模型。l隨機存取機含有無窮多個存儲單元，這些存儲單元按照 0， 1， 2， … 進行編號，每個存儲單元可以存放一個任意整數(shù)。隨機存取機還包含有窮個能保存任意整數(shù)的算術寄存器，這些整數(shù)可以譯碼成通常的各類計算機指令。l顯然，如果選擇一個適當?shù)闹噶罴?，隨機存取機 RAM就可以用來模擬任何的現(xiàn)代數(shù)字計算機。l圖靈機與隨機存取機 RAM具有相同的能力。l定理：如果隨機存取機 RAM的基本指令都能夠用圖靈機來實現(xiàn)，那么，就可以用圖靈機實現(xiàn)隨機存取 機 RAM。l證明：l略。lTM等同于各種存儲指令的計算機系統(tǒng)。l可以將 TM用作算法定義的精確模型。l描述算法有三種基本方式：形式描述、實現(xiàn)描述和高水平描述。l形式描述需要詳細給出圖靈機的狀態(tài)定義，轉換函數(shù)的定義，是最詳細程度的算法描述；l實現(xiàn)描述通常使用自然語言來描述圖靈機的動作，如讀 /寫頭的移動，怎樣存儲數(shù)據(jù)等，不需要給出具體的狀態(tài)轉換函數(shù)的描述；l高水平描述采用自然語言描述，忽略了圖靈機的實現(xiàn)模型，即通常意義上的算法描述。通用 圖靈機l圖靈機是一個算法的實現(xiàn)裝置。直觀地，一臺通用的計算機，如果不受存儲空間和運行時間的限制的話，它應該能夠實現(xiàn)所有的有效算法。按照丘奇 圖靈論題，圖靈機應該是現(xiàn)代計算機的形式化的模型。l因此，應該存在一個圖靈機，它可以實現(xiàn)對所有圖靈機的模擬，也就是說，該圖靈機可以實現(xiàn)所有有效的算法，稱該圖靈機為通用圖靈機（ universalTuringmachine）。l定義 69：通用圖靈機。l通用圖靈機就是能夠模擬所有的圖靈機的圖靈機。編碼的目的l為了使通用圖靈機模擬某個圖靈機 M， 需要將圖靈機 M作為通用圖靈機的輸入信息