演示文稿計(jì)算理論圖靈機(jī)

1（優(yōu)選）計(jì)算理論圖靈機(jī)ppt講解當(dāng)前1頁，總共64頁。Overview圖靈機(jī)（TuringMachine，TM），是計(jì)算機(jī)的一種簡單的數(shù)學(xué)模型。歷史上，馮?諾曼計(jì)算機(jī)的產(chǎn)生就是由圖靈機(jī)誘發(fā)的。丘奇—圖靈論題：一切合理的計(jì)算模型都等同于圖靈機(jī).當(dāng)前2頁，總共64頁。類型文法結(jié)構(gòu)產(chǎn)生式形式限制條件

0短語結(jié)構(gòu)文法α→βα∈Ｖ+,β∈Ｖ*

PhraseStructure

上下文有關(guān)文法α1Aα2→α1βα2|α1βα2|≥|α1Aα2|1ContextSensitiveα1，α2∈Ｖ*（CSG）A∈ＶＮ

,β∈Ｖ+

上下文無關(guān)文法A→αA∈ＶＮ,α∈Ｖ*2ContextFree

（CFG）

正右線性文法A→xB，C→yA,B,C∈ＶＮ

3

規(guī)文左線性文法A→Bx，C→yx,y∈ＶT*

法當(dāng)前3頁，總共64頁。Overview 0型語言———圖靈機(jī)

1型語言(CSL)———線性界限自動(dòng)機(jī)

2型語言(CFL)———下推自動(dòng)機(jī)

3型語言(正規(guī)集)——有限自動(dòng)機(jī)當(dāng)前4頁，總共64頁。Overview圖靈機(jī)所定義的語言類---遞歸可枚舉集合圖靈機(jī)所計(jì)算的整數(shù)函數(shù)類---部分遞歸函數(shù)以圖靈機(jī)為模型,研究問題的可計(jì)算性，即確定該問題是可計(jì)算的、部分可計(jì)算的，還是不可計(jì)算的。

當(dāng)前5頁，總共64頁。Overview4.1圖靈機(jī)模型4.2圖靈機(jī)的變化和組合4.3通用圖靈機(jī)4.4圖靈機(jī)可計(jì)算性當(dāng)前6頁，總共64頁。4.1圖靈機(jī)模型當(dāng)前7頁，總共64頁。4.1圖靈機(jī)模型定義4-1

圖靈機(jī)M=(K,Σ,Γ,δ,q0,B,F)，其中

K是有窮的狀態(tài)集合；

Γ是所允許的帶符號集合；

B∈Γ，是空白符；ΣΓ，B∈Σ，是輸入字符集合；

FK，是終止?fàn)顟B(tài)集合。

q0∈K,是初始狀態(tài)；

﹨當(dāng)前8頁，總共64頁。4.1圖靈機(jī)模型δ：K×ΓK×?！羬L,R,S}是圖靈機(jī)的動(dòng)作(狀態(tài)轉(zhuǎn)移)函數(shù)，這里

L表示讀頭左移一格；

R表示讀頭右移一格；

S表示讀頭不動(dòng)；

δ(q,a)=(p,b,z)

表示狀態(tài)q下讀頭所讀符號為a時(shí)，狀態(tài)轉(zhuǎn)移為p,讀頭符號變?yōu)閎，同時(shí)讀頭變化為z. 當(dāng)前9頁，總共64頁。4.1圖靈機(jī)模型定義4-2

設(shè)當(dāng)前帶上字符串為x1x2…xn，當(dāng)前狀態(tài)為q，讀頭正在讀xi

，圖靈機(jī)的瞬時(shí)描述ID

為

x1x2…xi-1qxi…xn當(dāng)前10頁，總共64頁。4.1圖靈機(jī)模型定義4-3

設(shè)當(dāng)前的瞬時(shí)描述

ID1=x1x2…xi-1qxi…xn若有δ(q,xi)=(p,y,L)，則圖靈機(jī)瞬時(shí)描述變?yōu)?/p>

ID2=x1x2…xi-2pxi-1yxi+1…xn；若有δ(q,xi)=(p,y,R)，則圖靈機(jī)瞬時(shí)描述變?yōu)?/p>

ID2=x1x2…xi-1ypxi+1…xn。當(dāng)前11頁，總共64頁。4.1圖靈機(jī)模型定義4-3瞬時(shí)描述ID1經(jīng)過一步變?yōu)樗矔r(shí)描述ID2，稱ID1與ID2具有一步變化關(guān)系，表示為

ID1├ID2

若ID1經(jīng)過n步變?yōu)镮D2(n≥0)，即有

ID1├ID├…├ID2稱ID1與ID2具有多步變化關(guān)系，簡記為

ID1

├*ID2當(dāng)前12頁，總共64頁。4.1圖靈機(jī)模型定義4-4

對于圖靈機(jī)M=(K,Σ,Γ,δ,q0,B,F)，定義圖靈機(jī)接受的語言集L(M)為

L(M)={w|w∈Σ*∧u0uvqqf(u0∈Σ*∧u∈Σ*∧v∈Σ*∧q∈K∧qf∈F∧q0w├*u0qB├*uqfv)}當(dāng)前13頁，總共64頁。4.1圖靈機(jī)模型【例4-1】設(shè)計(jì)一個(gè)圖靈機(jī)，使得

L(M)={0n1n|n≥1}。設(shè)計(jì)思路:在帶上每當(dāng)將一個(gè)0變?yōu)閄，就把一個(gè)1變?yōu)閅。當(dāng)將所有的0變?yōu)閄時(shí)，恰將所有的1變?yōu)閅，這個(gè)串就是合法的，最后將X、Y分別還原為0、1。當(dāng)前14頁，總共64頁。4.1圖靈機(jī)模型當(dāng)前15頁，總共64頁。4.1圖靈機(jī)模型【例4-2】設(shè)計(jì)一個(gè)圖靈機(jī)，使之接受

L(M)={wcw|w∈{a,b}*}設(shè)計(jì)思路：在c左側(cè)，從左至右逐一字符，用狀態(tài)記下它并標(biāo)志該符號為已處理符號，移至c右側(cè)對應(yīng)位置后，判斷是否是相同符號。若相同，再返回c左側(cè)循環(huán)，直至所有符號比較完畢。最后將標(biāo)志符號修改回原符號。在設(shè)計(jì)時(shí)，特別注意用狀態(tài)存貯符號的方法，這是圖靈機(jī)設(shè)計(jì)的重要方法之一。當(dāng)前16頁，總共64頁。4.1圖靈機(jī)模型當(dāng)前17頁，總共64頁。4.1圖靈機(jī)模型【例4-3】設(shè)計(jì)一個(gè)圖靈機(jī)，計(jì)算自然數(shù)n的以2為底的對數(shù)。用一進(jìn)制表示輸入和輸出值。an表示輸入n,bm表示輸出m.設(shè)計(jì)思路：從左到右掃描帶，把所碰到的a劃掉一個(gè)，留一個(gè)，并將計(jì)數(shù)器加1。重復(fù)此過程，直至a不復(fù)存在。這里，用字符c表示劃掉的字符。當(dāng)前18頁，總共64頁。4.1圖靈機(jī)模型當(dāng)前19頁，總共64頁。4.1圖靈機(jī)模型【例4-4】設(shè)計(jì)一個(gè)圖靈機(jī)，計(jì)算二個(gè)自然數(shù)m、n的減法：

設(shè)計(jì)時(shí)，整數(shù)n用0n表示。開始時(shí)，帶上符號為0m10n，結(jié)束時(shí)，帶上符號為0。每當(dāng)在1的左邊將一個(gè)0改變?yōu)锽，就在1的右邊將一個(gè)0改為1，若1的右邊無0時(shí)，再將左邊改為B的0恢復(fù)回來。

m-n若m≥nm－n= 0否則當(dāng)前20頁，總共64頁。4.1圖靈機(jī)模型R當(dāng)前21頁，總共64頁。4.1圖靈機(jī)模型【例4-5】設(shè)計(jì)圖靈機(jī)實(shí)現(xiàn)數(shù)字從一進(jìn)制表示到二進(jìn)制表示的轉(zhuǎn)換。這個(gè)圖靈機(jī)的設(shè)計(jì)可以仿例4-3，不同在于每次循環(huán)時(shí)，要保留除以2的余數(shù)作為當(dāng)前二進(jìn)制位的值。注意這里首先計(jì)算出的是二進(jìn)制的低位值，所以要將結(jié)果不斷右移以插入新生成的位，生成的結(jié)果是低位在右端。初始時(shí)，整數(shù)n用an表示，結(jié)束時(shí)，帶上是0、1構(gòu)成的二進(jìn)制數(shù)。當(dāng)前22頁，總共64頁。4.1圖靈機(jī)模型R當(dāng)前23頁，總共64頁。4.2圖靈機(jī)的變化和組合4.2.1雙向無窮帶圖靈機(jī)4.2.2多帶圖靈機(jī)4.2.3非確定圖靈機(jī)4.2.4多頭圖靈機(jī)4.2.5多維圖靈機(jī)4.2.6離線圖靈機(jī)4.2.7圖靈機(jī)的組合4.2.8枚舉器當(dāng)前24頁，總共64頁。雙向無窮帶圖靈機(jī)定理4-1L被一個(gè)具有雙向無窮帶的圖靈機(jī)識別，當(dāng)且僅當(dāng)它被一個(gè)單向無限帶的圖靈機(jī)識別。證明：單向無限TM模擬雙向無限TM，采用多道技術(shù)。當(dāng)前25頁，總共64頁。4.2.2多帶圖靈機(jī)當(dāng)前26頁，總共64頁。4.2.2多帶圖靈機(jī)【例4-6】設(shè)計(jì)一個(gè)二帶圖靈機(jī)，使得T(M)={ωω|ω∈{0,1}*}。這個(gè)問題的關(guān)鍵是比較字符串前后兩個(gè)部分，為此，首先要對帶上字符串計(jì)數(shù)：每二元素計(jì)數(shù)加1，按計(jì)數(shù)值將字符串分為前后兩個(gè)部分，并將它們分別存放于不同帶上，然后進(jìn)行比較。當(dāng)前27頁，總共64頁。4.2.2多帶圖靈機(jī)當(dāng)前28頁，總共64頁。4.2.2多帶圖靈機(jī)【例4-7】

設(shè)計(jì)二帶圖靈機(jī)，實(shí)現(xiàn)二進(jìn)制到一進(jìn)制的轉(zhuǎn)換。設(shè)這個(gè)圖靈機(jī)為M7，其第一帶用作輸入帶，第二帶用作輸出帶。設(shè)計(jì)思路是從左到右掃描輸入帶上的二進(jìn)制字符，并使用公式r*2+b生成輸出帶上一進(jìn)制數(shù)，其中r是當(dāng)前輸出帶上的一進(jìn)制數(shù)，b是當(dāng)前輸入帶上掃描的字符，這里的r*2就是將原輸出帶上的一進(jìn)制數(shù)r復(fù)制一遍。例如：1001的一進(jìn)制數(shù)計(jì)算過程。當(dāng)前29頁，總共64頁。4.2.2多帶圖靈機(jī)當(dāng)前30頁，總共64頁。4.2.2多帶圖靈機(jī)定理4-2

如果一個(gè)語言L被一個(gè)多帶圖靈機(jī)接受，它就能被一個(gè)單帶圖靈機(jī)接受。當(dāng)前31頁，總共64頁。4.2.3非確定圖靈機(jī)【例4-8】下面的圖靈機(jī)就是不確定圖靈機(jī)。無向圖G中，從a出發(fā)合法路徑判定的不確定型圖靈機(jī)。當(dāng)前32頁，總共64頁。4.2.3非確定圖靈機(jī)非確定圖靈機(jī)由一個(gè)有窮控制器、一條帶和一個(gè)讀頭組成。對于一個(gè)給定的狀態(tài)和被讀頭掃描的帶符號，機(jī)器的下一個(gè)動(dòng)作將有有窮個(gè)選擇。設(shè)一個(gè)非確定圖靈機(jī)M1=(K,Σ,Γ,δ,q0,B,F)，除轉(zhuǎn)移函數(shù)δ外，其它同一般圖靈機(jī)的定義。轉(zhuǎn)移函數(shù)δ仍是從K×Γ到K×?！羬L,R,S}上的映射，但它可能有多個(gè)映射的像,即存在q∈K,a∈Σ, δ(q,a)=(p1,b1,c1) δ(q,a)=(p2,b2,c2) …… δ(q,a)=(pr,br,cr)當(dāng)前33頁，總共64頁。4.2.3非確定圖靈機(jī)定理4-3

如果語言L被一個(gè)非確定圖靈機(jī)M1接受，則L將被某個(gè)確定圖靈機(jī)M2接受。當(dāng)前34頁，總共64頁。4.2.4多頭圖靈機(jī)一個(gè)k頭圖靈機(jī)有k個(gè)讀頭，一個(gè)控制器和一條帶，讀頭由1到k編號，圖靈機(jī)的一個(gè)動(dòng)作由當(dāng)前狀態(tài)和被每個(gè)讀頭所掃描的符號。在一個(gè)動(dòng)作中，每個(gè)讀頭獨(dú)立地左移、右移或不動(dòng)。定理4-4

如果L被某個(gè)k個(gè)讀頭的圖靈機(jī)接受，則它能被一個(gè)單頭圖靈機(jī)接受。當(dāng)前35頁，總共64頁。4.2.5多維圖靈機(jī)多維圖靈機(jī)具有通常的有限控制器，但帶卻由k維單元陣列組成。這里，在所有2k個(gè)方向上（k個(gè)軸，每軸正、負(fù)兩個(gè)方向），都是無限的，根據(jù)狀態(tài)和掃視的符號，該裝置改變狀態(tài)，打印一個(gè)新的符號，在2k個(gè)方向上移動(dòng)它的讀頭，開始時(shí)，輸入沿著一個(gè)軸排列，讀頭在輸入的左端。當(dāng)前36頁，總共64頁。4.2.6離線圖靈機(jī)定理4-5

如果L被一個(gè)二維圖靈機(jī)M1接受，那么L將被一個(gè)一維圖靈機(jī)M2接受。當(dāng)前37頁，總共64頁。4.2.7圖靈機(jī)的組合當(dāng)前38頁，總共64頁。4.2.7圖靈機(jī)的組合【例4-9】

設(shè)計(jì)一個(gè)TM，完成乘法運(yùn)算m×n。開始時(shí)帶上符號為：0m10n1，結(jié)束時(shí)帶上符號為0mn，用子程序調(diào)用的方式完成。設(shè)計(jì)思想是：每當(dāng)抹去左邊一個(gè)０，就在第二個(gè)１后面拷貝n個(gè)０。當(dāng)?shù)谝粋€(gè)１的左邊全變?yōu)锽時(shí)，帶上就為10n10mn，再抹去10n1，帶上就剩0mn，即為所求。設(shè)計(jì)Copy子程序這個(gè)子程序完成在第二個(gè)１拷貝n個(gè)０的操作。 第1次被調(diào)用 開始ID：B０m-11q10n1

結(jié)束ID：B０m-11q50n10n

第i次被調(diào)用 開始ID：Bi０m-i1q10n10(i-1)n

結(jié)束ID：Bi０m-i1q50n10in在拷貝時(shí)，每當(dāng)將一個(gè)０變成２，就在末尾寫個(gè)０。當(dāng)0n變?yōu)?n時(shí)，就已在右邊加了0n。再將2變?yōu)?n。當(dāng)前39頁，總共64頁。4.2.7圖靈機(jī)的組合設(shè)計(jì)主ＴＭM M={q0,q6,q7,q8,q9,q10,q11,q12,q13},{0,1},{0,1,2,B},δ,q0,B,{q13})開始ID為q00m10n1，進(jìn)入Copy入口ID為B0m-11q10n1，為此，

δ(q0,0)=(q6,B,R) δ(q6,0)=(q6,0,R) δ(q6,1)=(q1,1,R)從Copy結(jié)束時(shí)的ID，進(jìn)入主TM的開始ID (B0m-11q50n10n├Bq00m-110n10n) δ(q5,0)=(q7,0,L) δ(q7,1)=(q8,1,L) δ(q8,0)=(q9,0,L) δ(q9,0)=(q9,0,L)

δ(q9,B)=(q0,B,R)善后處理：Bm1q50n10mn當(dāng)前40頁，總共64頁。4.2.8枚舉器當(dāng)前41頁，總共64頁。4.2.8枚舉器定理4-6

一個(gè)語言是圖靈可識別的，當(dāng)且僅當(dāng)有枚舉器枚舉它。證明：首先證明如果有枚舉器E枚舉語言L，則存在圖靈機(jī)M識別L。構(gòu)造M如下：對于任意輸入串w，運(yùn)行E。每當(dāng)E輸出一個(gè)串時(shí)，與w比較，若相等，接受w，并停機(jī)。顯然，M接受在E輸出序列中出現(xiàn)過的那些串?，F(xiàn)在證明若有圖靈機(jī)M識別語言L，則有枚舉器E枚舉L。設(shè)L={w1，w2，w3，…}，構(gòu)造E如下：對i=1,2,3,…執(zhí)行如下步驟（1）對w1，w2，w3，…,wi中的每一串，讓M以其作為輸入運(yùn)行i步。（2）若在這個(gè)計(jì)算中，M接受wj，則打印wj，M接受w，它最終將出現(xiàn)在E的枚舉打印中。事實(shí)上，它可能在E的列表在出現(xiàn)無限多次，因?yàn)槊恳淮沃貜?fù)運(yùn)行，M在每一個(gè)串上都從頭開始運(yùn)行。當(dāng)前42頁，總共64頁。4.3通用圖靈機(jī)(１)緩沖域帶的最左面是標(biāo)記符Ａ，Ａ的右邊是|K|+|Γ|+2個(gè)單元構(gòu)成的緩沖（|K|、|Γ|分別是狀態(tài)集和字母集的元素?cái)?shù)目）。(２)Ｍ的描述字域緩沖區(qū)域右邊緊接的是Ｍ的描述字dM，以Ｂ為開始標(biāo)志，以３個(gè)０結(jié)束。對于轉(zhuǎn)移函數(shù)

δ(q,a)=(q,a,d)，我們用五元組表示為(q,a,q,a,d)，將順序調(diào)整為(q,a,a,d,q)。

dM就是由這樣的五元組組成的序列。對于每個(gè)五元組中的狀態(tài)和字符，我們用其序號的一進(jìn)表示，其間用０分隔，五元組間用２個(gè)０分隔。例如：若有δ(q２,０)=(q３,２,Ｌ)，表示成上面定義的五元組是(q２,０，２,Ｌ，q３)，再用其序號表示為(2,0,2,0,3)，在U2的帶上表示為

(３)Ｍ的輸入描述域Ｍ的描述字域的右邊存放的是輸入串的編碼：用字母的序號表示該字母，并用０分隔。該域以Ｃ為起始標(biāo)志。如輸入為111，則該串表示為：

110110110當(dāng)前43頁，總共64頁。4.3通用圖靈機(jī)UTMU2模擬ＴＭＭ具體步驟如下：步0將讀頭置于描述字區(qū)域的開始符號Ｂ上。此時(shí)緩沖區(qū)域是０；步1

U2復(fù)寫標(biāo)記Ｂ或Ｅ后面的狀態(tài)到緩沖域的初始位置，然后在其后面加一個(gè)輔助符號Ｄ，讀寫頭右移到符號Ｃ；步2U2復(fù)寫Ｃ后面的初始帶模式到緩沖區(qū)部分，即在Ｄ之后；步3U2將Ｄ改為0，現(xiàn)緩沖區(qū)中包含當(dāng)前狀態(tài)和掃描的字母；步4對描述字域進(jìn)行搜索，查看前兩項(xiàng)匹配的元組。若所有的五元組都不匹配，則表明Ｍ停機(jī)，U2也停機(jī)。若找到一個(gè)匹配的五元組，標(biāo)記Ｄ、Ｅ表示正在比較的狀態(tài)或符號；當(dāng)前44頁，總共64頁。4.3通用圖靈機(jī)步5

(找到匹配的五元組)刪去緩沖區(qū)的內(nèi)容，并把標(biāo)記Ｅ右移一個(gè)符號，使Ｅ處于該五元組的新符號的前面；步6用新符號代替標(biāo)記Ｃ后面的符號(可能需擴(kuò)充或壓縮原輸入描述域)，U2將標(biāo)記Ｅ右移至五元組的方向分量前；步7

U2計(jì)數(shù)方向分量中１的個(gè)數(shù)，然后按要求向左或向右移動(dòng)標(biāo)記Ｃ。若Ｃ向左離開了輸入串，則U2停機(jī)；若Ｃ向右離開了輸入串，U2必須添加一個(gè)表示下一個(gè)方格的新的“０”串。當(dāng)前U2描述字域標(biāo)記Ｅ后面不是結(jié)束狀態(tài)，則轉(zhuǎn)至步1；否則接受輸入串并停機(jī)。當(dāng)前45頁，總共64頁。4.3通用圖靈機(jī)當(dāng)前46頁，總共64頁。4.3通用圖靈機(jī)對于任何一個(gè)圖靈機(jī)M，都有一個(gè)確定的描述字dM，如在例4-10中 dM將它看作一個(gè)二進(jìn)制數(shù)，實(shí)質(zhì)上，它是一個(gè)整數(shù)，因此按這種表示，任何一個(gè)圖靈機(jī)都和一個(gè)整數(shù)相對應(yīng)，這個(gè)整數(shù)，稱為圖靈機(jī)的標(biāo)記。

當(dāng)前47頁，總共64頁。4.4圖靈可計(jì)算性4.4.1圖靈可計(jì)算性函數(shù)4.4.2圖靈機(jī)的枚舉定理4.4.3圖靈機(jī)的計(jì)算限界當(dāng)前48頁，總共64頁。4.4.1圖靈可計(jì)算性函數(shù)

定義4-5函數(shù)f(x1,x2,…,xn)是部分圖靈可計(jì)算的，若有一圖靈程序P，使得

ψP(x1,x2,…,xn)=f(x1,x2,…,xn)其中ψP(x1,x2,…,xn)是P對應(yīng)的函數(shù)，“=”表示若有定義，則值相等；否則，均無定義。當(dāng)前49頁，總共64頁。4.4.1圖靈可計(jì)算性函數(shù)定義4-6

函數(shù)f(x1,x2,…,xn)是全函數(shù)，若它對一切x1,x2,…,xn都有定義。定義4-7

函數(shù)f(x1,x2,…,xn)是圖靈可計(jì)算函數(shù)，若它是部分圖靈可計(jì)算的而且是全函數(shù)。當(dāng)前50頁，總共64頁。4.4.1圖靈可計(jì)算性函數(shù)當(dāng)前51頁，總共64頁。4.4.1圖靈可計(jì)算性函數(shù)定理4-7設(shè)g1,g2,…,gm是n元圖靈可計(jì)算函數(shù)，h是m元圖靈可計(jì)算函數(shù)，則復(fù)合函數(shù)

f=h·(g1,g2,…,gm)也是圖靈可計(jì)算的。當(dāng)前52頁，總共64頁。4.4.2圖靈機(jī)的枚舉定理1．圖靈機(jī)的標(biāo)記

2．圖靈可計(jì)算的重要定理定義4-8

若z是一個(gè)圖靈機(jī)M的標(biāo)記，并且M計(jì)算部分函數(shù)g(x1,x2,…xn)，則定義函數(shù)Φ(n)

為

Φ(n)(z,x1,x2,…,xn)=g(x1,x2,…xn)當(dāng)前53頁，總共64頁。4.4.2圖靈機(jī)的枚舉定理定理4-8[枚舉定理]

對于每個(gè)自然數(shù)z，部分函數(shù)Φ(n)(z,x1,x2,…,xn)是(部分)圖靈可計(jì)算函數(shù)。[證明]它能枚舉所有部分可計(jì)算函數(shù)。具體說就是，n+1元函數(shù)Φ