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