形式語言與自動(dòng)機(jī)理論：第4章 Turing機(jī)

第4章Turing機(jī)4.1Turing機(jī)的定義4.2用Turing機(jī)計(jì)算4.3Turing的擴(kuò)充4.4隨機(jī)存取Turing機(jī)4.5非確定型Turing機(jī)4.6文法4.7數(shù)值函數(shù)引論圖靈（AlanMathisomTuring）在1963年提出了圖靈模型，它是一個(gè)通用的計(jì)算模型；TM是計(jì)算機(jī)的一個(gè)簡(jiǎn)單的數(shù)學(xué)模型，與現(xiàn)今看到的計(jì)算機(jī)具有相同的功能。我們希望通過研究圖靈機(jī)，來研究它所定義的語言——遞歸可枚舉集（recursivelyenumerableset）和它所能計(jì)算的整函數(shù)——部分遞歸函數(shù)（partialrecursivefunction），同時(shí)，也為算法和可計(jì)算性的研究提供形式化描述工具。4.1Turing機(jī)的定義圖靈提出TM的目的是為了對(duì)有效的計(jì)算過程（算法）進(jìn)行形式化的描述。Turing機(jī)被設(shè)計(jì)成同時(shí)滿足以下三個(gè)標(biāo)準(zhǔn)：它們應(yīng)當(dāng)是自動(dòng)機(jī)，即它們的構(gòu)造和功能一般應(yīng)與前面研究過的裝置相同；它們應(yīng)當(dāng)盡量簡(jiǎn)單，這是就描述、形式化定義和討論來說的;它們應(yīng)當(dāng)盡量一般，這是就可完成的計(jì)算而言。圖靈給出的基本模型包括：一個(gè)有窮控制器，一條含有無窮多個(gè)帶方格的輸入帶，一個(gè)讀頭?；緢D靈機(jī)的物理模型：控制器一步操作：根據(jù)當(dāng)前狀態(tài)和讀寫頭當(dāng)前掃描的帶符號(hào)，控制器完成二種功能：改變有窮控制器的狀態(tài)；在當(dāng)前掃描的方格里寫一個(gè)符號(hào)替換該位置符號(hào)；或者把讀寫頭向右或者向左移動(dòng)一格。q0q1q3q2h

abaa讀寫頭（雙向移動(dòng)）有窮控制器定義4.1.1Turing機(jī)是五元組(K,∑,δ,s,H),其中K是狀態(tài)的有窮集；∑是字母表，包含空格符︺和左端符▽，但不含←和→；s∈K是初始狀態(tài)；HK是停機(jī)狀態(tài)的集合；δ是轉(zhuǎn)移函數(shù)，它是從(K-H)×∑到K×(∑∪{←,→})的函數(shù)，使得對(duì)所有q∈K-H，若δ(q,▽)=(p,b),則b=→；對(duì)所有q∈K-H和a∈∑，若δ(q,a)=(p,b),則b≠▽；

對(duì)δ的要求的注意：當(dāng)M看到帶左端▽時(shí)，它必須向右移動(dòng)；M永寫不出▽，▽是帶左端標(biāo)志，應(yīng)是唯一的；δ在H里的狀態(tài)上無定義，當(dāng)機(jī)器到達(dá)停機(jī)狀態(tài)就停止?！纠?.1.1】考慮Turing機(jī)M=(K,∑,δ,s,{h})其中：

K={}， ∑={a,∟,h}，s=;qδ(q,)a(,∟)∟(h,∟)(,→)a(,a)∟(,→)(,→)狀態(tài)變換如下（,）→（,→）→（,a）→（,∟）→（,→）→（,a）→（,∟）→（,→）→（,∟）→（h,∟）∟aa∟∟h注意：這臺(tái)Turing機(jī)完成把帶上非空格符改成空格，也稱刪除非空格符號(hào)?！纠?.1.2】考慮TMM=(K,∑,δ,s,H)，其中：

K={}， ∑={a,∟,}，

s=，

H={h}。 其中δ如下表所：

這臺(tái)機(jī)器向左掃描直到發(fā)現(xiàn) ∟為止，然后停機(jī)。如果從帶頭 位置向左到帶左端的每個(gè)方格都包含a，帶左端包含，那么M將移動(dòng)到帶左端，并從此就再帶左端和它右方的方格之間來回移動(dòng)。Turing機(jī)的操作可以永不停止。qδ(q,)a(,←)∟(h,∟)(,→)定義4.1.2Turing機(jī)M＝(K,∑,δ,s,H)的格局是

K×▽×((－{︺})∪{e})的成員。

注：狀態(tài)頭前串+頭處符號(hào)頭后串除非當(dāng)前正在掃描空格符，否則所有格局都用左端符開始且永遠(yuǎn)不用空格符結(jié)束。 因此： 是格局； 不是格局。 狀態(tài)分量屬于H的格局稱為停機(jī)格局。我們寫wau表示格局(q,wa,u)，即把(q,wa,u)記作(q,wau)。定義4.1.3

設(shè)M＝(K,∑,δ,s,H)是Turing機(jī)，考慮M的兩個(gè)格局 （）和（），其中。 那么 當(dāng)且僅當(dāng)對(duì)某個(gè)1.當(dāng)b∈∑時(shí)，并且；2.當(dāng)b=←時(shí)，而且(a)若≠∟或則，(b)若a1＝∟且則；3.當(dāng)b=→時(shí)，而且(a)，或者(b)，并且=∟?！纠?.1.3】設(shè) ，其中u不用∟結(jié)尾，a,b∈∑。

1.

例子：

2. 3.下面用例子說明上述定義的含義：也分3種情形定義4.1.4

對(duì)任意Turing機(jī)M，設(shè)是的自反傳遞閉包；若格局 ，則稱格局產(chǎn)生格局。M的計(jì)算是格局序列，其中n≥0，稱計(jì)算的長(zhǎng)度為n或它有n步，寫成。【例4.1.4】考慮例4.1.1中描述的Turing機(jī)M，計(jì)算如下：4.1.1Turing機(jī)的記號(hào)使用分層的記號(hào)，其中越來越復(fù)雜的機(jī)器被從更簡(jiǎn)單的材料中構(gòu)造出來?；緳C(jī)器：寫符號(hào)機(jī)和移帶頭機(jī)。寫符號(hào)機(jī)：固定字母表∑，對(duì)每個(gè)a∈∑∪{←，→}-{}，Turing機(jī)Ma=({s,h},∑,δ,s,{h}),其中對(duì)每個(gè)b∈∑-{}δ(s,b)=(h,a)，則這臺(tái)機(jī)器唯一操作就是完成動(dòng)作a——若a∈∑,則寫符號(hào)a，若a∈{←,→}，則按照a所指示的方向移動(dòng)——然后立即停機(jī)。寫符號(hào)機(jī)用的太多，用寫a來代替Ｍ。移帶頭機(jī)M←和M→縮寫稱L和R。組合機(jī)器的規(guī)則直到前一臺(tái)機(jī)器停機(jī)為止才應(yīng)用從前一臺(tái)機(jī)器到后一臺(tái)機(jī)器的連接；后一臺(tái)機(jī)器于是從初始狀態(tài)和前一臺(tái)機(jī)器留下的帶和帶頭位置上啟動(dòng)。所以，若M1，M2和M3都是Turing機(jī)，則下圖里顯示的機(jī)器操作如下：在M1的初始狀態(tài)啟動(dòng)，像M1那樣操作直到M1停機(jī)為止；然后若當(dāng)前掃描符號(hào)是a則啟動(dòng)M2并且像M2那樣操作；否則若當(dāng)前掃描符號(hào)是b則啟動(dòng)M3并且像M3那樣操作。M1M3M2ab用它的各部分給出組合成的Turing機(jī)的明確定義是直截了當(dāng)?shù)?。并可用上圖所示機(jī)器作示范。假設(shè)三臺(tái)Turing機(jī)M1

，M2和M3分別是：我們假定所有這些機(jī)器的狀態(tài)都不相交，因?yàn)樵诮M合機(jī)器的背景下這樣假定是最方便的。于是，上圖里所示的組合機(jī)器是： 其中： 對(duì)每個(gè)如下定義：

＞RRab∟圖4.4(a)兩臺(tái)R機(jī)組合＞RRab∟圖4.4(b)左機(jī)縮記圖4.5(a)右移到空格為止R∟＞R＞Ra≠∟圖4.5(b)左機(jī)R∟縮記＞RLa∟a≠∟圖4.6右移到非空格符，并在其左邊復(fù)制之＞RR∟∟a≠∟圖4.8復(fù)制機(jī)C即﹄W﹄=>﹄W﹄W﹄圖4.9左平移S←即▽?duì)隬﹄=>▽W(xué)﹄L∟∟a≠∟＞L∟R4.2用Turing機(jī)計(jì)算首先約定輸入，M在輸入上的初始格局是。定義4.2.1設(shè)M＝(K,∑,δ,s,H)是Turing機(jī),使得包含 兩個(gè)不同的停機(jī)狀態(tài)(y和n分別表示“是”和“否”)。狀 態(tài)分量是y的任何停機(jī)格局都稱為接受格局，而狀態(tài) 分量是n的停機(jī)格局稱為拒絕格局。 對(duì)輸入

，若

產(chǎn)生接受格局則我 們說M接受w；若

產(chǎn)生拒絕格局則我們說M拒 絕w。設(shè)是字母表，稱為M的輸入字母表；通過固定∑0是 的真子集，我們?cè)试STuring機(jī)在計(jì)算中使用除在輸入里出現(xiàn)符號(hào)外的額外符號(hào)。如果是語言，并且對(duì)任何字符串，下列關(guān)系為真：若則M接受w；若則M拒絕w，那門我們說M判定語言L。若存在Turing機(jī)判定語言L則稱L是遞歸的。即Turing機(jī)判定語言L的條件：當(dāng)在輸入w上啟動(dòng)時(shí)它總是停機(jī)，并且停機(jī)的狀態(tài)是對(duì)輸入的正確回答。接受w或拒絕wRdRdRdL∟yndab,c∟c,∟a,∟a,dbcb,d【例4.2.1】考慮語言

（之前的語言識(shí)別器都無法識(shí)別）4.2.1遞歸函數(shù)定義4.2.2

設(shè)M＝(K,∑,δ,s,{h})是Turing機(jī)，

是字母表，并設(shè)。假設(shè)M在輸入w上停機(jī)，而 且對(duì)某個(gè)，則y稱為M 在輸入w上的輸出，并表示成M(w)。注意僅當(dāng)M在輸 入w上停機(jī)時(shí)M(w)才有定義，而且事實(shí)上是在形如 的格局里停機(jī)，其中。現(xiàn)在設(shè)f是從到的任意函數(shù)，對(duì)于所有則我們說M計(jì)算函數(shù)f。若存在Turing機(jī)計(jì)算函數(shù)f，則稱f為遞歸的?！纠?.2.2】函數(shù)k(w)=ww可用機(jī)器CS←計(jì)算，即在復(fù)制機(jī)后面跟著左平移機(jī)。任何自然數(shù)可用唯一的方式表示成里的字符串。定義4.2.3

設(shè)M＝(K,∑,δ,s,{h})是Turing機(jī)使得0,1,;∈∑， 并設(shè)對(duì)某個(gè)k≥1，f是從到N的函數(shù)。若對(duì)所有的

（即對(duì)都是整數(shù)的二進(jìn)制編碼的 任意k個(gè)字符串），

則我們說M計(jì)算函數(shù)f。即若M在整數(shù)的二 進(jìn)制表示的輸入上啟動(dòng)則它最終停機(jī)，并且當(dāng)它確實(shí) 停機(jī)時(shí)帶上有表示數(shù)字的字符串——函 數(shù)值。若存在計(jì)算函數(shù)的Turing機(jī)M，則f稱為遞歸的。多變量數(shù)值函數(shù)：【例4.2.3】設(shè)計(jì)后繼函數(shù)succ(n)=n+1的機(jī)器;R∟L101SR10∟L∟4.2.2遞歸可枚舉語言定義4.2.4

設(shè)M＝(K,∑,δ,s,H)是Turing機(jī)，是 字母表，并設(shè)是語言。若對(duì)任意字符串 下列關(guān)系為真：w∈L當(dāng)且僅當(dāng)M在輸入w上停機(jī),則我 們說M半判定L。語言L是遞歸可枚舉的當(dāng)且僅當(dāng)存在 Turing機(jī)M半判定L。當(dāng)向M提供輸入w∈L時(shí)，要求它最終停機(jī)。只要它確實(shí)最終達(dá)到停機(jī)格局，我們就不深究他達(dá)到了何種停機(jī)格局。若，則M必然永不進(jìn)入停機(jī)狀態(tài)，因?yàn)槿魏畏峭C(jī)格局都產(chǎn)生某種其它格局，所以在這種情形里機(jī)器必然無限的繼續(xù)計(jì)算。我們將M在輸入w上不停機(jī)記作M(w)=↗。則Turing機(jī)M半判定語言的定義如下： 對(duì)所有，M(w)=↗當(dāng)且僅當(dāng)。例4.2.4設(shè)L={w∈{a,b}*:w至少包含一個(gè)a}

于是下圖所示Turing機(jī)半判定語言L。對(duì)于某個(gè)w∈{a,b}*，初始格局，只是向右掃描直到遇到a為止，然后停機(jī)。否則永不停機(jī)。Ra注意：1、圖靈機(jī)半判定性是確定性有窮自動(dòng)機(jī)接受概念的擴(kuò)充，但有窮自動(dòng)機(jī)讀完了所有輸入時(shí)它總是停機(jī)---這種計(jì)算裝置是一個(gè)算法。2、半判定語言L的圖靈機(jī)不能用來辨別字符串w是否屬于L，因?yàn)槿魒不屬于L時(shí)它永不停機(jī)（不知道等多久能得到答案）---半判定語言的圖靈機(jī)都不是算法。4.2.2遞歸可枚舉語言定理4.2.1

若語言是遞歸的，則它是遞歸可枚舉的。證明：給定判定L的任意Turing機(jī)M＝(K,∑,δ,s,{y,n})，可定義半判定L的Turing機(jī)如下：M’＝(K,∑,δ’,s,{y})，其中δ’只是δ增加下列關(guān)于n的轉(zhuǎn)移（n不再是停機(jī)狀態(tài)）：對(duì)于所有a∈∑,δ’(n,a)=δ(n,a)----即在n狀態(tài)“死循環(huán)”很顯然，若M判定L，則M’半判定L。定理4.2.2

若L是遞歸語言則它的補(bǔ)L

也是遞歸的。證明：很顯然只要互換y和n狀態(tài)即可。M’(w)=y當(dāng)且僅當(dāng)M(w)=n，因此M’判定L的補(bǔ)語言。注意：以上兩個(gè)命題的逆命題均不成立！4.3圖靈機(jī)的擴(kuò)充從多種方向上擴(kuò)充Turing機(jī)模型的效果。“新改進(jìn)型”的Turing機(jī)在每種情形里都是可用標(biāo)準(zhǔn)模型模擬，即說明Turing機(jī)是終極的計(jì)算裝置。4.3.1多帶Turing機(jī)定義4.3.1設(shè)k≥1是整數(shù)。k帶Turing機(jī)是(K,∑,δ,s,H)五元組，其中K，∑，s和H都是像在普通Turing機(jī)的定義里那樣，而轉(zhuǎn)移函數(shù)δ是從(K-H)×∑

k到K×(∑∪{←,→})

k的函數(shù)。即，對(duì)每種狀態(tài)以及帶符號(hào)的每個(gè)K元組（a1,…,ak），δ(q,(a1,…,ak))=(p,(b1,…,bk))其中p像前面那樣是新狀態(tài)，bj在直觀上是M在帶j上采取的動(dòng)作。自然，我們還堅(jiān)持，若對(duì)某個(gè)j≤K

，aj=?,

則bj=

→.定理4.3.1

對(duì)某個(gè)k≥1，設(shè)M=(K,∑,δ,s,H)是k帶Turing機(jī)。那么存在標(biāo)準(zhǔn)Turing機(jī)M’=(K’,∑’,δ’,s’,H)，其中∑?∑‘,使得下列關(guān)系成立：對(duì)任意輸入字符串x∈∑*，M在輸入x上停機(jī)并且在第一條帶上有輸出y當(dāng)且僅當(dāng)M’在輸入x上在同樣的停機(jī)狀態(tài)里停機(jī)，并且在帶上有同樣的輸出y。另外，如果M在輸入x上在t步之后停機(jī)，那么M‘在輸入x上O(t?（|x|+t）)步之后停機(jī)。推論：

k帶Turing機(jī)計(jì)算的任何函數(shù)或者判定、半判定的任何語言，也分別可用標(biāo)準(zhǔn)Turing機(jī)計(jì)算或判定、半判定。定義4.3.2設(shè)M=(K,∑,δ,s,H)是k帶Turing機(jī).M的格局是K×(?∑*×(∑*(∑-{⊥})∪{e}))k

的成員。即格局說明當(dāng)前狀態(tài)以及K條帶里每條的帶內(nèi)容和帶頭位置。4.3.2雙向無窮帶Turing機(jī)

顧名思義：帶是兩個(gè)方向上的且在兩個(gè)方向上是無窮的。

具體描述：Turing機(jī)的帶在左右兩個(gè)方向都是無窮的。除里面包含的輸入的那些方格外，所有其余帶方格起初都是空格。

關(guān)鍵點(diǎn)：標(biāo)準(zhǔn)Turing機(jī)中的?符號(hào)（左端符）在此類Turing機(jī)中是不必要和無意義的。

模擬實(shí)現(xiàn)：雙向無窮帶可用2帶機(jī)器模擬實(shí)現(xiàn)，其中，一條帶包含第一個(gè)輸入符號(hào)所在方格右邊的那部分帶，另一條帶用相反方向包含該方格左邊的那部分帶。這臺(tái)2帶機(jī)可用標(biāo)準(zhǔn)Turing機(jī)模擬（線性時(shí)間）。顯然。有多條雙向無窮帶的也可以用同樣的方式模擬。4.3.3多帶頭Turing機(jī)

顧名思義：一條帶上不止一個(gè)帶頭，而是有多個(gè)帶頭與有窮控制器聯(lián)接。

具體描述：允許在標(biāo)準(zhǔn)Turing機(jī)的一條帶上擴(kuò)充多只帶頭，每條帶頭都進(jìn)行移動(dòng)和寫。

關(guān)鍵點(diǎn)：是否會(huì)造成不同的帶頭間沖突？避免此沖突的機(jī)制：讓編號(hào)低的帶頭有較高的優(yōu)先權(quán)。

模擬實(shí)現(xiàn)：類似于模擬k帶機(jī)器那樣實(shí)現(xiàn)。基本想法：把帶劃分成軌道，除第一條軌道外，所有其余軌道都專門用來記錄多個(gè)帶頭位置。掃描2遍模擬多帶頭機(jī)一步計(jì)算：第一遍掃描發(fā)現(xiàn)所有帶頭位置上符號(hào)；第二遍掃描改變這些符號(hào)或適當(dāng)?shù)匾苿?dòng)帶頭。

4.3.4二維帶Turing機(jī)

推廣思路：另一種推廣是允許帶是無窮的二維網(wǎng)格。注意：綜上就是幾種主要的Turing機(jī)模型的擴(kuò)充方法。當(dāng)然，這些擴(kuò)充是可被組合起來的?？梢栽O(shè)想：Turing機(jī)有多條帶，所有的或是部分的帶都是雙向無窮的并且上面有多只帶頭，甚至可以是多維的。盡管如此，Turing機(jī)的根本能力還是保持原樣。定理4.3.2

有多帶、多帶頭、雙向無窮帶或多維帶的Turing機(jī)，它們判定或半判定的任何語言以及計(jì)算的任何函數(shù)，都分別可用標(biāo)準(zhǔn)Turing機(jī)判定、半判定或者計(jì)算。4.4隨機(jī)存取Turing機(jī)

4.4.1定義：隨機(jī)存取Turing機(jī)

是二元組M=(k，Π)，其中K>0是寄存器的個(gè)數(shù)，Π=(Π1,Π2,…,Πp,)，即程序，Π是指令的有窮序列，其中每條指令Πi是書中圖4-19所示類型之一。假設(shè)最后一條指令Πp總是halt指令。(程序也可包含其它的halt指令)

隨機(jī)存取Turing機(jī)（k,Π）的格局是k+2元組(x,R0,R1,…,Rk-1,T),其中x∈N是程序計(jì)數(shù)器(0≤x≤p的整數(shù))。若x是零，則格局是停機(jī)格局。對(duì)于每個(gè)j(0≤j＜k)，Rj∈N是寄存器j的值。T即帶內(nèi)容,是正整數(shù)有序?qū)Φ挠懈F集。(i,m)∈T意味著第i個(gè)帶方格當(dāng)前包含整數(shù)m；i＞0，m＞0。不在T中有序?qū)Φ谝环至繉?duì)應(yīng)帶方格都假定包含0。

參看書p137頁(yè)圖4-19

定義

(續(xù))

設(shè)M=(k,Π)是隨機(jī)存取機(jī)器。設(shè)C=(x,R0,R1,…,Rk-1,T)和C’==(x’,R’0,R’1,…,R’k-1,T’)是M的兩個(gè)格局。若在直觀上，x’與諸R’j和T’的值，正確的反映了把當(dāng)前指令Πx的“語義”應(yīng)用到x與諸Rj和T上的效果，則我們說格局C一步產(chǎn)生格局C’,表示成C├C’。注釋:參考圖4-19理解格局產(chǎn)生含義：若Πx形如readj，其中j<k,則這條指令的執(zhí)行有下列效果：寄存器0包含的變成等于編號(hào)為Rj的帶方格的值。即R’0=T[Rj]，其中若滿足(Rj,m)∈T,則T[Rj]=m，否則它是0。另外，指令計(jì)數(shù)器x=x+1。格局C’的所有其余分量都與C相同。

產(chǎn)生關(guān)系├*M是├M的自反傳遞閉包。隨機(jī)存取Turing機(jī)的判定工作上面講述了隨機(jī)存取Turing機(jī)的機(jī)制，下面將講述其對(duì)輸入的判定工作過程。定義4.4.2

字母表Σ滿足︺∈Σ并且Σ。另外，設(shè)E是Σ和{0，1，…，|Σ|-1}之間的固定雙射，這個(gè)雙射是編碼隨機(jī)存取Turing機(jī)的輸入和輸出地方式。假設(shè)E（︺）=0。隨機(jī)存取Turing機(jī)M=（k，Π）在輸入=…上的初始格局是（k，，…，，T），其中k=1，對(duì)所有j，=0，并且T={（1，E（）），（2，E（）），…，（n，E（））}。若在輸入字符串x∈∑*上的初始格局最后產(chǎn)生滿足R0=1的停機(jī)格局，則我們說M接受x。若在輸入x上的初始格局產(chǎn)生滿足R0=0的停機(jī)格局，則我們說M拒絕x。換句話說，一旦M停機(jī)，我們就在寄存器0中讀到判定結(jié)果：若這個(gè)值是1，則機(jī)器接受；若值是0，則它拒絕。設(shè)∑0∑-{︺}是字母表，并設(shè)L∑*0是語言。若每當(dāng)x∈L，M就接受x；每當(dāng)x∈L，M就拒絕x，則稱M判定L。若下列關(guān)系為真：x∈L當(dāng)且僅當(dāng)M在輸入x上產(chǎn)生某個(gè)停機(jī)格局，則稱M半判定L。設(shè)f:∑*0∑*0是函數(shù)。若對(duì)于所有x∈∑*0，機(jī)器M在輸入x上的初始格局產(chǎn)生停機(jī)格局，并且?guī)?nèi)容是{(1,E(a1)),(2,E(a2)),。。。,(n,E(an)),}，其中f(x)=a1a2…an，則稱M計(jì)算f。例4.4.2下面用縮寫形式描述隨機(jī)存取Turing機(jī)程序，他判定語言acount:=bcount:=ccount:=0,n:=1;WhileT[n]==1don:=n+1,acount:=acount+1;WhileT[n]==2don:=n+1,bcount:=bcount+1;WhileT[n]==3don:=n+1,ccount:=ccount+1;Ifacount==bcount==ccountandT[n]==0thenacceptelsereject;其中：假設(shè)E(a)=1,E(b)=2,E(c)=3,分別用變量acount,bcount和ccount表示迄今為止找到的a,b和c的個(gè)數(shù)。也用縮寫accept表示“l(fā)oad=1,halt”，reject表示“l(fā)oad=0,halt”。

隨機(jī)存取Turing機(jī)和基本Turing機(jī)等價(jià)的證明：

定理4.4.1

任何遞歸或遞歸可枚舉語言，以及任何遞歸函數(shù)，分別可用隨機(jī)存取Turing機(jī)判定、半可判定和計(jì)算。

（注：隨即存取Turing機(jī)→基本Turing機(jī)）定理4.4.2

隨機(jī)存取Turing機(jī)判定或半判定的任何語言，以及隨機(jī)存取Turing機(jī)計(jì)算的任何函數(shù)，分別可用標(biāo)準(zhǔn)Turing機(jī)判定、半判定和計(jì)算。另外，如果隨機(jī)存取機(jī)器在輸入上停機(jī)，那么標(biāo)準(zhǔn)Turing機(jī)所花費(fèi)的步數(shù)不超過隨機(jī)存取Turing機(jī)在同一個(gè)輸入上步數(shù)的多項(xiàng)式。（注：隨即存取Turing機(jī)←基本Turing機(jī)）4.5非確定性Turing機(jī)

（這里，├M產(chǎn)生不必是單值的，一個(gè)格局可以在一步里產(chǎn)生多個(gè)其它格局）定義4.5.1

設(shè)M=（K,∑,△,s,H）是非確定型Turing機(jī)。若對(duì)輸入ω∈(∑-{?，︺})*，對(duì)某個(gè)h∈H以及a∈∑,u,v∈∑*，(s,?︺ω)├*M（h,uav）,則我們說M接受ω。注意：即使非確定型Turing機(jī)在輸入上有許多非停機(jī)計(jì)算，只要存在一種停機(jī)格局即可。若對(duì)語言L∈（∑-{?

，︺}）*，對(duì)所有ω∈(∑-{?

，︺})*，下列關(guān)系成立：ω∈L當(dāng)且僅當(dāng)M接受ω，則我們說M半判定L。定義4.5.2：設(shè)M=（K,∑,△,s,{y,n}）是非確定型Turing機(jī)。設(shè)L(∑-{?，︺})*是語言，若對(duì)任意ω∈(∑-{?，︺})*，下列兩個(gè)條件成立：(a)存在自然數(shù)N，它依賴于M和ω，使得不存在任何格局C滿足(s,?

︺ω)├NMC。---最多N步就停機(jī)，即N步內(nèi)停機(jī)。

(b)ω∈L當(dāng)且僅當(dāng)對(duì)某個(gè)u,v∈∑*，a∈∑，(s,?︺ω)├*M（y,uav）。則我們說M判定L。設(shè)f:(∑-{?,︺})*→(∑-{?,︺})*是函數(shù)，若對(duì)所有ω∈(∑-{?,︺})*，下列兩個(gè)條件成立：

(a)存在N，依賴于M和ω，使得不存在任何格局C滿足(s,?︺ω)├NMC(b)(s,?︺ω)├*M（h,uav）當(dāng)且僅當(dāng)ua=?︺,并且v=f(ω)。則我們說M計(jì)算f。存在非確定型Turing機(jī)等價(jià)的確定型Turing機(jī)：定理4.5.1

如果非確定型Turing機(jī)M半判定或判定語言L，或者計(jì)算函數(shù)f,那么，存在標(biāo)準(zhǔn)型Turing機(jī)M’半判定或判定語言L，或者計(jì)算函數(shù)f。證明：用多帶Turing機(jī)可構(gòu)造性證明之。略。4.6文法定義4.6.1

文法（或無限制文法，或改寫系統(tǒng)）是四元組G=(V,∑,R,S）其中：V是字母表； ∑?

V是終結(jié)符集，V-∑稱為非終結(jié)符集；

S∈V-∑是起始符；并且

R，即規(guī)則集，是（V*（V-∑

）V*

）╳V*

的有窮子集。若(u,v)∈R，則可寫成uv；u=>Gv

當(dāng)且僅當(dāng)對(duì)于某些w1,w2∈V*以及某條規(guī)則u’v’∈R,u=w1u’w2并且v=w1v’w2。

=>*G是=>G的自反傳遞閉包。字符串w∈∑*是G生成的當(dāng)且僅當(dāng)S=>*Gw;G生成的語言L(G)是G生成的所有串的集合。

推導(dǎo)：形如w0=>Gw1=>G。。。

=>Gwn的序列。定理4.6.1

語言被文法生成當(dāng)且僅當(dāng)它是遞歸可枚舉的。

證明：僅當(dāng)---利用多帶機(jī)模仿文法推導(dǎo)；當(dāng)---用Turing機(jī)模仿歸約。定義4.6.2(函數(shù)f與文法G可計(jì)算)

設(shè)G=(V,∑,R,S)是文法，并設(shè)f:∑*|->∑*是函數(shù)。若對(duì)所有w,v∈∑*

，下列關(guān)系為真

SwS=>G*v當(dāng)且僅當(dāng)v=f(w)

即，包括輸入w和兩側(cè)的G的起始符的字符串恰好生成∑*里一個(gè)字符串：f(w)的正確值，則我們說G計(jì)算f

。函數(shù)f:∑*|->∑*稱為是文法可計(jì)算的當(dāng)且僅當(dāng)存在計(jì)算它的文法G定理4.6.2函數(shù)f:∑*|->∑*是遞歸的當(dāng)且僅當(dāng)它是文法可計(jì)算的。4.7數(shù)值函數(shù)（數(shù)值函數(shù)的構(gòu)造）原始遞歸函數(shù)

定義4.7.1

對(duì)任意k≥0，定義從Nk到N的基本函數(shù)如下：

a）對(duì)任意k≥0，k元零函數(shù)定義為:

對(duì)所有n1,…,nk∈N，zerok(n1,…,nk)=0;b）對(duì)任意k≥j>0，第j個(gè)k元恒等函數(shù)定義為:

對(duì)所有n1,…,nk∈N，idk,j(n1,…,nk)=nj;c）后繼函數(shù)定義為:

對(duì)所有n∈N，succ(n)=n+1兩個(gè)簡(jiǎn)單的組合方法：(把函數(shù)組合成稍微復(fù)雜的函數(shù))(1)設(shè)k,l≥0，g:Nk-->N是k元函數(shù)，h1,…,hl都是l元函數(shù)，則g與h1,…,hl的合成是由

f(n1,…,nl)=g(h1(n1,…,nl),…,hk(n