有限自動(dòng)機(jī)理論06章圖靈機(jī)-簡(jiǎn)化

第六章圖靈機(jī)圖靈機(jī)(即TuringM--TM)由A.Turing于1936年，在論文《可計(jì)算數(shù)字及其在判斷性問題中的應(yīng)用》里提出。

TM是可計(jì)算性的數(shù)學(xué)模型可計(jì)算的特點(diǎn)是:

有窮、離散、機(jī)械執(zhí)行、停機(jī)。為計(jì)算機(jī)的發(fā)展奠定了理論基礎(chǔ)。圖靈:計(jì)算機(jī)理論之父馮諾依曼:計(jì)算機(jī)體系結(jié)構(gòu)之父圖靈機(jī)可以模擬電子計(jì)算機(jī)的計(jì)算能力。使用圖靈機(jī)可以解決計(jì)算機(jī)程序的可計(jì)算問題。圖靈機(jī)的構(gòu)造技術(shù)類似于計(jì)算機(jī)的編程(設(shè)計(jì)指令)技術(shù)。6.1圖靈機(jī)的基本模型

6.1.1圖靈機(jī)的定義圖靈機(jī)的物理模型a1a2a3…aj…anan+1…FSC一個(gè)有限狀態(tài)控制器(FSC)一個(gè)外部的存儲(chǔ)設(shè)備可以向右擴(kuò)展的無限長(zhǎng)度帶帶上具有左端點(diǎn)，使用“┣”表示圖靈機(jī)直接掃描輸入帶上左端點(diǎn)右邊的第一個(gè)符號(hào)。帶分解為單元，每個(gè)單元可以為空或存放字母表上的字母符號(hào)帶的空白單元標(biāo)記為B有限狀態(tài)控制器通過一個(gè)讀/寫頭與帶進(jìn)行耦合。在某個(gè)時(shí)刻，有限狀態(tài)控制器處于某個(gè)狀態(tài)，讀/寫頭將掃描帶上的一個(gè)單元依照狀態(tài)和掃描到的帶上符號(hào)，圖靈機(jī)將有一個(gè)動(dòng)作如下：有限狀態(tài)控制器的狀態(tài)進(jìn)行改變；把剛剛掃描過的單元上符號(hào)擦除掉，并印刷上一個(gè)新的符號(hào)（有可能印刷上與原來符號(hào)相同的符號(hào)）；讀/寫頭向左或者向右移動(dòng)一個(gè)單元；或者讀/寫頭不移動(dòng)。五元式描述動(dòng)作<q，x，q′，W，{L，R，N}>其中：x，W∈∑′（∑的增廣集合）

圖靈機(jī)處于狀態(tài)q，掃描到符號(hào)x，則狀態(tài)變換為q′，印刷上新的符號(hào)W，讀/寫頭向左、或向右或不移動(dòng)。例6-1用TM接收

語言{a2n|n≥0}圖靈機(jī)帶上符號(hào)串為：┣aaa…aaaB圖靈機(jī)初始處于狀態(tài)even，將要掃描第一個(gè)a，則<even，a，odd，B(或a)，R><odd，a，even，B，R><odd，B，odd，B，R>

//可省略<even，B，accept，B，R(或N)>若帶上a的個(gè)數(shù)為偶數(shù)，則圖靈機(jī)經(jīng)過多個(gè)動(dòng)作后，處于接收狀態(tài)accept；若帶上a的個(gè)數(shù)為奇數(shù)，根據(jù)<oddBoddBR>，圖靈機(jī)將不會(huì)停機(jī)，可以永遠(yuǎn)繼續(xù)下去這與其它的自動(dòng)機(jī)不同，即圖靈機(jī)可能會(huì)導(dǎo)致永不停止的計(jì)算。例6-2語言為{a2n|n>0}<start，a，odd，B，R><odd，a，even，B，R><even，a，odd，B，R><odd，B，odd，B，R><even，B，accept，B，R>定義6-1圖靈機(jī)是一個(gè)五元式TM=(Q，∑，q0，qα，δ)Q是有限狀態(tài)集合；∑是字母表的有限集合∑′=∑∪{B}∪A；∑的增廣集合，即輸入帶上符號(hào)的集合q0∈Q，是唯一的開始狀態(tài)qα∈Q，是唯一的接收狀態(tài)δ:Q×∑′→Q×∑′×{L,R,N}對(duì)于任意的(q，x)∈Q×∑′δ(q，x)=(q′，W，{L，R，N})將δ記為一般形式：<q，x，q′，W，{L，R，N}>或圖靈機(jī)是一個(gè)七元組TM=(Q，，

，，q0，B，F(xiàn))

F

Q終止?fàn)顟B(tài)集合；

是帶符號(hào)集合；B

稱為空白符；:Q

Q{R,L,N}

定義6-2圖靈機(jī)的格局IDw1qw2∈w1是讀/寫頭左邊帶上的符號(hào)串q是圖靈機(jī)當(dāng)前所處的狀態(tài)w2是讀/寫頭右邊的帶上的符號(hào)串(∑′)*Q(∑′)*圖靈機(jī)在格局w1qw2時(shí)停機(jī)若w1qw2=w1qxw對(duì)于無定義。δ(q，x)?定義6-3格局的轉(zhuǎn)換若M在w1qw2上不停機(jī)，則如下定義格局的轉(zhuǎn)換：某個(gè)時(shí)刻，圖靈機(jī)處于格局w1qw2=r1yqxr2，其中：

r1y=w1，(若w1=ε，則y=B，r1=ε)

xr2=w2，(若w2=ε，則r2=ε，x=B)使用

=>

表示圖靈機(jī)的格局轉(zhuǎn)換若δ（q，x）=(q′，x′，L)，則r1yqxr2=>若δ（q，x）=(q′，x′，N)，則r1yqxr2=>若δ（q，x）=(q′，x′，R)，則r1yqxr2=>r1q′yx′r2r1yq′x′r2r1yx′q′r2使用=>+代表格局的多次變換使用=>*代表格局的任意次變換定義6-4圖靈機(jī)M=（Q，∑，q0，qα，δ）在字母表∑上接收的語言為L(zhǎng)(M)，則L(M)={w|存在w1，w2∈(∑′)*有

=>*

}q0ww1qαw2定義6-5完全的圖靈機(jī)如果圖靈機(jī)對(duì)于一切輸入串都能夠停機(jī)----完全的圖靈機(jī)。完全的圖靈機(jī)接收的語言L稱為遞歸語言(圖靈可判定語言)

6.1.2圖靈機(jī)的構(gòu)造例６-３接收僅有一個(gè)1的0、1串TM=({q0，q1，q2},{0，1},q0，q2,δ)∑′={0，1，B}<q0，0，q0，0，R><q0，1，q1，1，R><q1，0，q1，0，R><q1，B，q2，B，N>例6-4構(gòu)造圖靈機(jī)

接收語言{anbn|n>0}思路1：當(dāng)圖靈機(jī)遇到a時(shí)，將a改寫為#向右尋找b，找到b，將b改寫為#再向左找a…直到所有a都找完。(向左找的a是整個(gè)a串最左邊的a)指令為①讀到一個(gè)a，用#代替它，向右找b<start，a，del_b，#，R><del_b，a，del_b，a，R><del_b，#，del_b，#，R>②處于狀態(tài)del_b，掃描到b，用#代替它，向左尋找a，（從①重復(fù)循環(huán)）<del_b，b，seek_a，#，L><seek_a，#，seek_a，#，L><seek_a，a，del_b，#，R>//最右的a

③seek_a狀態(tài)時(shí)，沒有再發(fā)現(xiàn)a(都已被#所代替)，還需要檢查是否所有的b都已經(jīng)被掃描過。<seek_a，├，check，├

，R><check，#，check，#，R><check，B，accept，B，N>問題該圖靈機(jī)能接收anbn的所有串但該圖靈機(jī)也能接收aababb等原因：使用#代表已掃描的a和b

沒有保證a和b的順序。為了區(qū)別原來的字母a和b使用#和$分別代替字母a和b當(dāng)a和b都識(shí)別后，帶上的串為

├###…##$$$…$$B例6-5修改上例：①讀到一個(gè)a，用#代替它，向右尋找b<start，a，del_b，#，R><del_b，a，del_b，a，R><del_b，#，del_b，#，R><del_b，$，del_b，$，R>②處于狀態(tài)del_b，掃描到b，用$代替它，向左尋找a，（從①重復(fù)循環(huán)）<del_b，b，seek_a，$，L><seek_a，$，seek_a，$，L><seek_a，#，seek_a，#，L><seek_a，a，del_b，#，R>③在seek_a狀態(tài)時(shí)，沒有再發(fā)現(xiàn)a（都已經(jīng)被#所代替）需檢查是否所有的b都已經(jīng)被掃描過還必須注意#與$的順序。<seek_a，┣，check1，┣，R><check1，#，check1，#，R><check1，$，check2，$，R><check2，$，check2，$，R><check2，B，accept，B，N>例6-6{anbn|n>0}的第二種算法當(dāng)圖靈機(jī)遇到a時(shí)，將a改寫為#向右尋找b，找到b，將b改寫為$再向左找a(此時(shí)的a是整個(gè)a串最左邊的a)…，直到所有a都找完。指令①讀到一個(gè)a，用#代替它，向右尋找b<start，a，del_b，#，R><del_b，a，del_b，a，R><del_b，$，del_b，$，R>②處于狀態(tài)del_b，掃描到b，用$代替，向左尋找a，（從①重復(fù)循環(huán)）<del_b，b，seek_#，$，L><seek_#，$，seek_#，$，L>

<seek_#，a，seek_#，a，L>//跳過a串<seek_#，#，seek_a，#，R>//最右#<seek_a，a，del_b，#，R>//最左a③在seek_a狀態(tài)時(shí)，沒有再發(fā)現(xiàn)a，需檢查是否所有的b都已經(jīng)被掃描過。<seek_a，$，check，$，R><check，$，check，$，R><check，B，accept，B，N>某些不需要定義的規(guī)則<start，b，?>//無a<start，B，?>//無a無b<del_b，B，?>//b少<seek_a，B，?>

//無b<seek_a，b，?>

//不可能<check，b，?>//b多思考能否給對(duì)圖靈機(jī)的性能進(jìn)行評(píng)價(jià)？對(duì)于相同的輸入串，比較兩種算法的圖靈機(jī)的指令數(shù)量每條指令的執(zhí)行次數(shù)（總次數(shù)）新印刷符號(hào)的數(shù)量；讀/寫頭移動(dòng)的次數(shù)例6-7{anbn|n>0}第三種算法思路:首先檢查輸入串是否為a+b+的格式；如果不是，則拒絕該串如果是，檢查a和b的個(gè)數(shù)是否相等。指令<start，a，s_a，a，R><s_a，a，s_a，a，R>(掃描a)<s_a，b，s_b，b，R><s_b，b，s_b，b，R>(掃描b)<s_b，B，first，B，L><first，b，first，b，L><first，a，first，a，L><first，┣，new_start，┣，R>

(開始檢查a和b的個(gè)數(shù)是否相等)<new_start，a，del_b，#，R><del_b，a，del_b，a，R><del_b，#，del_b，#，R><del_b，b，seek_a，#，L>已經(jīng)保證順序<seek_a，#，seek_a，#，L><seek_a，a，del_b，#，R><seek_a，┣，check，┣R>（檢查是否有多余的b）<check，#，check，#，R><check，B，accept，B，N>例6-8接收語言{anbncn|n>0｝TM=（Q，∑，start，accept，δ）Q={start，del_b，del_c，seek_a，check1，check2，check3，accept}∑={a，b，c}∑′={a，b，c，B，#，$，!}指令①讀到一個(gè)a，用#代替它，向右尋找b<start,a,del_b,#,R><del_b,a,del_b,a,R><del_b,#,del_b,#,R><del_b,$,del_b,$,R>②處于狀態(tài)del_b時(shí),掃描到b，用$代替它，向右尋找c：<del_b,b,del_c,$,R><del_c,b,del_c,b,R><del_c,$,del_c,$,R><del_c,!,del_c,!,R>③處于狀態(tài)del_c時(shí)，掃描到c，用!代替它，向左找a，(從①開始又重復(fù)循環(huán))<del_c，c,seek_a，!，L><seek_a，!，seek_a，!，L><seek_a，b，seek_a,b,L><seek_a，$，seek_a,$,L><seek_a，#，seek_a,#,L><seek_a，a，del_b,#,R>④在seek_a狀態(tài)時(shí)，沒有再發(fā)現(xiàn)a（都已經(jīng)被#所代替）還需要檢查是否所有的b和c都已經(jīng)被掃描過注意#、$和！的順序<seek_a,┣,check1,┣,R><check1,#,check1,#,R><check1,$,check2,$,R><check2,$,check2,$,R><check2，!，check3,!,R>識(shí)別第一個(gè)!<check3，!,check3,!,R>跳過剩余!<check3,B,accept,B,N>類似地，圖靈機(jī)接收語言{anbncn|n>0}，也有多種方法。思考：構(gòu)造TM接收語言{aibjci+j|i,j>0}構(gòu)造TM接收語言{aibjci*j|i，j>0}構(gòu)造TM接收語言{wcwT|w∈(a,b)*}

6.2圖靈機(jī)作為非負(fù)整數(shù)函數(shù)計(jì)算模型設(shè)有k元函數(shù)f(n1，n2，…，nK)=m

如果TM接受輸入串

0n110n21…10nk而“輸出”符號(hào)串0m則稱TM計(jì)算k元函數(shù)f；或稱f為TM計(jì)算的函數(shù)。也稱f是圖靈可計(jì)算的。自動(dòng)機(jī)都具有識(shí)別語言的功能圖靈機(jī)還具有“計(jì)算”功能可以規(guī)定非負(fù)整數(shù)的表示方法,從而實(shí)現(xiàn)非負(fù)整數(shù)的函數(shù)求值。K元函數(shù)可以轉(zhuǎn)換為多個(gè)二元函數(shù)

僅考慮二元函數(shù)使用“一進(jìn)制”方式表示一個(gè)非負(fù)整數(shù)，即使用0m表示整數(shù)m。若需要計(jì)算f(m，n)，則可以在輸入帶上存放0m10n形式的串圖靈機(jī)將串改寫為0f(m，n)的形式，即表示出計(jì)算f(m，n)的結(jié)果。加法圖靈機(jī)對(duì)于非負(fù)整數(shù)m、n，計(jì)算m+n。分析圖靈機(jī)輸入0m10n需要輸出0m+n算法：將1改寫為0，最后一個(gè)0改寫為B(可能是1改寫成的0)TM=（Q，∑,start，accept，δ）Q={start，q1，q2，accept}∑={0，1}∑′={0，1，B}start可以是一般狀態(tài)<start，0，start，0，R><start，1,q1，0，R><q1，0，q1，0，R><q1，B，q2，B，L>遇到B，向左找0<q2，0，accept，B，N>最后的0改為Bstart僅為開始狀態(tài)<start，1,q1，0，R>串為1或10n<start，0，q1，0，R>第1個(gè)0<q1，0，q1，0，R>

跳過剩余的0<q1，1，q1，0，R>遇到1，改為0<q1，B，q2，B，L>遇到B，向左找0<q2，0，accept，B，N>最后的0改為B注意掃描1左邊和右邊的0的工作都由<q1，0，q1，0，R>完成。整個(gè)串只允許一個(gè)1。例6-16構(gòu)造TM實(shí)現(xiàn)非負(fù)減法(真減法)m·n=

m-nm>n=0m≤n(即全是B)或思路1帶上字符串的形式為0m10n尋找1左邊的0，刪除1右邊的0可能在尋找1左邊的0時(shí)結(jié)束(m≤n)或者在刪除1右邊的0時(shí)結(jié)束(m>n)(1)<start,0,seek_1,B,R>掃描第1個(gè)0(2)<seek_1,0,seek_1,0,R><seek_1,1,del_0,1,R>//原標(biāo)記的1

(3)<del_0，0，seek_B，1，L>//將1后的第1個(gè)0變?yōu)?

<del_0，1，del_0，1，R>//后加的<start,1<del_0,B(4)<seek_B，1，seek_B，1，L>

向左找B<seek_B，0，seek_B，0，L><seek_B，B，start，B，R>讀寫頭位置轉(zhuǎn)（1）重復(fù)上述動(dòng)作?m>n(5)<del_0，B，m>n，B，L>//遇到最右邊的B，表示1右邊已沒有0<m>n，1，m>n，B，L>將1改寫為B<m>n，0，m>n，0，L><m>n，B，accept，0，N>

補(bǔ)寫1個(gè)0，結(jié)束m≤n(6)<start，1，m≤n，B，R>start將遇到第一個(gè)1<m≤n，1，m≤n，B，R><m≤n，0，m≤n，B，R><m≤n，B，accept，B，N>此時(shí)，輸入帶上全為Ｂ，表示０m>n在第(5)步開始時(shí)，輸入帶上的字符串形式為：

BBB…BB000…011…11B

m-n-1

n

左邊B有n+1個(gè)m>n根據(jù)TM的動(dòng)作，在左邊消除一個(gè)0，再去1的右邊找0當(dāng)發(fā)現(xiàn)1的右邊已經(jīng)沒有0時(shí)，此時(shí)減法工作應(yīng)該結(jié)束m>n但左邊多消除了一個(gè)0因此，第（5）步，在m>n的的控制下除了將1改寫為B外還應(yīng)該將一個(gè)0補(bǔ)寫回來，才能結(jié)束減法工作。m>n此時(shí)，輸入帶上的字符串形式為：

BBB…B000…0Bm-n個(gè)m<=n時(shí)，整個(gè)減法的結(jié)果應(yīng)該為0輸入帶全為B特殊：m=n=0，則串為1BB…<start，1，m≤n，B，R><m≤n，B，accept，B，N>結(jié)束思路2自學(xué)圖靈機(jī)反復(fù)進(jìn)行下面的工作：先用B替換1左邊領(lǐng)頭的0向右搜尋1右邊的第一個(gè)0，并將這個(gè)0替換為X，然后左移到B。重新開始循環(huán)。退出循環(huán)的條件有兩種：

1)1的左邊找不到0，說明m≤n輸出0，應(yīng)將所有非B符號(hào)改寫為B；2)1的右邊找不到0，說明m>n輸出0m-n，應(yīng)將1換為0，將X換為B。狀態(tài)轉(zhuǎn)換函數(shù)為：(1)開始循環(huán)，用B替換1左邊領(lǐng)頭的0<q0，0，q1，B，R>(2)向右搜尋1。<q1，0，q1，0，R><q1，1，q2，1，R>(3)向右尋1右邊的第一個(gè)0,并將這個(gè)0替換為X<q2，X，q2，X，R><q2，0，q3，X，L>(4)左移到B，重新開始循環(huán)。<q3，X，q3，X，L><q3，1，q3，1，L><q3，0，q3，0，L><q3，B，q0，B，R>(5)符合退出條件1)，即1的左邊找不到0，用狀態(tài)q4向右掃描將所有非B符號(hào)改寫為B，并進(jìn)入終止?fàn)顟B(tài)q6<q0，1，q4，B，R><q4，X，q4，B，R><q4，0，q4，B，R><q4，B，q6，B，R>(6)符合退出條件2)，即1的右邊找不到0，用狀態(tài)q5向左掃描將所有X改寫為B，將1替換為0，并進(jìn)入終態(tài)q6<q2，B，q5，B，L><q5，X，q4，B，L><q5，1，q5，0，L>//1換為0

<q5，B，q6，B，N>6.3圖靈機(jī)的構(gòu)造技術(shù)構(gòu)造TM，就相當(dāng)于編寫一個(gè)程序(指令或規(guī)則的組合)。本節(jié)介紹的圖靈機(jī)的一些構(gòu)造技術(shù)，這些技術(shù)具有一般性，對(duì)于圖靈機(jī)的構(gòu)造(程序設(shè)計(jì))具有較大的意義。6.3.1圖靈機(jī)的存儲(chǔ)技術(shù)例6-12構(gòu)造TM，識(shí)別字母表{a,b,c}上的語言L：每個(gè)字符串的第一個(gè)符號(hào)在該串中僅僅出現(xiàn)一次。思路：要求：第一個(gè)符號(hào)僅僅出現(xiàn)一次圖靈機(jī)可以“記住”輸入帶上的第一個(gè)符號(hào)（a或b或者c）。使用二元式表示狀態(tài)第一個(gè)分量仍然表示原來的狀態(tài)；第二個(gè)分量存儲(chǔ)帶上的第一個(gè)符號(hào)。[q，a]、[q，b]和[q，c]分別代表輸入串的第一個(gè)符號(hào)為a、b和c的情況。(1)掃描第一個(gè)符號(hào)，并存儲(chǔ)<start，a，[q，a]，a，R><start，b，[q，b]，b，R><start，c，[q，c]，c，R>(2)第一個(gè)符號(hào)是a<[q，a]，b，[q，a]，b，R><[q，a]，c，[q，a]，c，R>(3)第一個(gè)符號(hào)是b<[q，b]，a，[q，b]，a，R><[q，b]，c，[q，b]，c，R>(4)第一個(gè)符號(hào)是c<[q，c]，a，[q，c]，a，R><[q，c]，b，[q，c]，b，R>結(jié)束(5)遇到最右的B，接收該串<[q，a]，B，accept，B，N><[q，b]，B，accept，B，N><[q，c]，B，accept，B，N>注意直接運(yùn)用規(guī)則（1）和（5）可以接收僅僅只有一個(gè)符號(hào)的輸入串。例6-13構(gòu)造TM，識(shí)別

{a，b，c}上的語言L：每個(gè)句子的最后一個(gè)符號(hào)在該串中僅僅出現(xiàn)一次。思路

：最后個(gè)符號(hào)僅僅出現(xiàn)一次

TM先將讀/寫頭移動(dòng)到帶的最后“記住”輸入帶上的最后一個(gè)符號(hào)向左掃描輸入帶上的其他符號(hào)與最后一個(gè)符號(hào)進(jìn)行比較x={a,b,c}

(1)將讀/寫頭移動(dòng)到帶的最后<start，x，seek，x，R><seek，x，seek，x，R><seek，B，seek_last，B，L><start,B?(2)存儲(chǔ)最后的符號(hào)<seek_last，a，[q，a]，a，L><seek_last，b，[q，b]，b，L><seek_last，c，[q，c]，c，L>向左掃描輸入帶上的其他符號(hào)遇到├結(jié)束…思考：構(gòu)造TM識(shí)別語言

1）該語言每個(gè)句子的(倒數(shù))第n個(gè)符號(hào)在該句子中僅僅出現(xiàn)K次。n=1，2，3，…，m；K=1，2，3，…，L2）該語言每個(gè)句子的(倒數(shù))第n個(gè)符號(hào)在該句子中出現(xiàn)次數(shù)不多于(不少于)K次。n=1，2，3，…，m

；K=1，2，3，…，L6.3.2圖靈機(jī)的移動(dòng)技術(shù)在解決比較復(fù)雜的問題時(shí)TM可能需要將輸入帶上一組連續(xù)的非空符號(hào)左移或者右移若干個(gè)單元。使用n元式存儲(chǔ)多個(gè)符號(hào)

合適的時(shí)候再將這些符號(hào)印刷到需要的位置上。例6-14構(gòu)造TMΣ={a,b,c}，將輸入串右移兩個(gè)單元使用三元組[q，a1，a2]表示狀態(tài)q表示原來的狀態(tài)；a1、、a2可以代表a、b、c設(shè)串長(zhǎng)度>=2(1)掃描第一個(gè)符號(hào)，并存儲(chǔ)<start，a1，[q，a1]，B，R>(2)掃描第二個(gè)符號(hào)，并存儲(chǔ)<[q，a1],a2，[q，a1，a2]，B，R>(3)將a1放在a3位置,將a3存儲(chǔ)<[q，a1，a2],a3，[q，a2，a3],a1，R>(4)<[q，a1，a2]，B，[q，a2]，a1，R>將倒數(shù)第二個(gè)符號(hào)放在右邊空白單元，將最后一個(gè)符號(hào)存儲(chǔ)在狀態(tài)中(5)<[q，a2]，B，end_move，a2，R>將最后一個(gè)符號(hào)放在帶上其中規(guī)則(3)需要重復(fù)多次使用。思考：當(dāng)串長(zhǎng)度為0時(shí)當(dāng)串長(zhǎng)度為1時(shí)本例使用三元組表示特殊狀態(tài)也可以使用二元組表示特殊狀態(tài)如[q，a1，a2]可以記為[q，a1a2]

（n元組也可以表示為二元組）對(duì)帶上符號(hào)進(jìn)行移動(dòng)一般只是比較復(fù)雜的TM的識(shí)別任務(wù)中的一部分工作移動(dòng)本身不會(huì)涉及到串的接收或拒絕問題復(fù)雜的TM可以繼續(xù)從end_move狀態(tài)開始其他的工作思考：構(gòu)造TM將整個(gè)輸入串前兩個(gè)符號(hào)刪除。思路將帶上符號(hào)從右向左移動(dòng)兩個(gè)單元。例6-15構(gòu)造TM輸入字母表為{0，1}在輸入串的開始處添加子串10。略。例6-16構(gòu)造TM

Σ={a，b，c}將輸入串包含的第一個(gè)abc子串刪除。思路存儲(chǔ)技術(shù)尋找到第1個(gè)abc子串的位置將后面的符號(hào)向左移動(dòng)三個(gè)單元。略。例6-18構(gòu)造TM，輸入字母表為{0，1}，要求M接收語言L：該語言的每個(gè)字符串包含且僅只能包含一個(gè)101子串(有且僅有一個(gè)101，不可以沒有101子串）思路當(dāng)識(shí)別出第一個(gè)101后，檢查輸入帶上剩余的串不能再包含101

TM=（Q，∑，start，accept，δ）

Q={start，[q，0]，[q，1]，[q，10]，check，[check，0]，[check，1]，[check，10]，refuse，accept}∑={0，1}∑′={0，1，B}(1)掃描第一符號(hào)<start，0，[q，0]，0，R><start，1，[q，1]，1，R><start，B，refuse，B，N>空串(2)期待1的出現(xiàn)

<[q，0]，0，[q，0]，0，R><[q，0]，1，[q，1]，1，R>(3)已經(jīng)掃描到“1”，等待可能的“0”<[q，1]，1，[q，1]，1，R><[q，1]，0，[q，10]，0，R>(4)已經(jīng)掃描到“10”，等待可能的“1”<[q，10]，0，[q，0]，0，R><[q,10]，1，check，1，R>(5)已掃描到101，檢查串的剩余部分<check，0，[check，0]，0，R><check，1，[check，1]，1，N>(6)<[check，0]，0，[check，0]，0，R><[check，0]，1，[check，1]，1，R>(7)<[check，1],0，[check，10]，0，R><[check，1]，1，[check，1]，1，R>（8）的第2條指令與（9）可以省略(8)<[check,10],0,[check，0],0,R><[check，10],1,refuse，1，N>(9)整個(gè)輸入串中沒有101<[q，0]，B，refuse，B，N><[q，1]，B，refuse，B，N><[q，10]，B，refuse，B，N>結(jié)束(10)整個(gè)輸入串只有一個(gè)101<check，B，accept，B，N><[check，0]，B，accept，B，N><[check，1]，B，accept，B，N><[check，10]，B，accept，B，N>思考構(gòu)造TM，接收語言L：該語言的每個(gè)句子必須包含兩個(gè)101例6-19構(gòu)造TM，接收語言L：該語言的每個(gè)句子最多只能包含一個(gè)100子串（可以沒有100子串）。思路

接收1個(gè)100子串的所有串；接收沒有100子串的所有串。例6-23構(gòu)造TM接收語言L：該語言的每個(gè)句子不包含子串100。思路當(dāng)識(shí)別出第一個(gè)100后，就拒絕。6.3.4圖靈機(jī)的多道技術(shù)為了能夠保存和處理更復(fù)雜的數(shù)據(jù)，可以將TM的輸入帶劃分為若干道在各道上可以存放不同的符號(hào)。沒有改變圖靈機(jī)的基本模型，只是將帶上符號(hào)當(dāng)做一個(gè)向量的組合每個(gè)符號(hào)可以是一個(gè)K維向量（將輸入帶劃分為K道）。單帶K道的圖靈機(jī)模型FSC狀態(tài)轉(zhuǎn)換函數(shù)一般形式為<q，x，q′，W，{L，R，N}>對(duì)于K道圖靈機(jī)<q,[ai1,ai2,…,aik],q′,[bi1,bi2,…,bik],{L,R,N}>一次需要掃描一個(gè)單元的多道3道TM進(jìn)行二進(jìn)制數(shù)加法運(yùn)算考慮3個(gè)基本加法規(guī)則

：0+00+1(1+0)1+1

還需要考慮進(jìn)位情況(全加器）第一、二道存放兩個(gè)操作數(shù)第三道存放計(jì)算結(jié)果第2個(gè)單元存放B（避免溢出）讀寫頭已經(jīng)在最低位(最右端)單元沒有進(jìn)位<[q,0],[0,0,B],[q,0],[0,0,0],L>0+0<[q,0],[0,1,B],[q,0],[0,1,1],L>0+1<[q,0],[1,0,B],[q,0],[1,0,1],L>1+0<[q,0],[1,1,B],[q,1],[1,1,0],L>1+1進(jìn)位<[q,1],[0,0,B],[q,0],[0,0,1],L>

<[q,1],[0,1,B],[q,1],[0,1,0],L>

<[q,1],[1,0,B],[q,1],[1,0,0],L><[q,1],[1,1,B],[q,1],[1,1,1],L>兩個(gè)數(shù)長(zhǎng)度不一致(左端補(bǔ)充B)

<[q,0],[0,B,B],[q,0],[0,B,0],L><[q,0],[1,B,B],[q,0],[1,B,1],L><[q,0],[B,0,B],[q,0],[B,0,0],L><[q,0],[B,1,B],[q,0],[B,1,1],L><[q,1],[0,B,B],[q,0],[0,B,1],L><[q,1],[1,B,B],[q,1],[1,B,0],L><[q,1],[B,0,B],[q,0],[B,0,1],L><[q,1],[B,1,B],[q,1],[B,1,0],L>結(jié)束<[q,0],[B,B,B],END,[B,B,0],N>

<[q,1],[B,B,B],END,[B,B,1],N>

思考兩個(gè)數(shù)長(zhǎng)度不一致(左端補(bǔ)充0)

十進(jìn)制的加法二進(jìn)制的減法十進(jìn)制的減法乘法與除法軟件計(jì)算機(jī)例6-24:構(gòu)造圖靈機(jī)

字母表為{a}，接收語言L：{an|n>=0，且n為完全平方數(shù)}基本數(shù)學(xué)公式：(n+1)2=n2+2n+1思路使用三道的圖靈機(jī)第一道存放輸入串；第二、三兩道作為“運(yùn)算器”使用：

第二道存放i2個(gè)a第三道存放2*i+1個(gè)a初始時(shí)原始算法從i=0開始在第二道上放i2個(gè)a比較第一道與第二道上a的個(gè)數(shù)如果相等，就接收；不相等，則在第三道上設(shè)置2*i+1個(gè)a，將第三道上的a加入到第二道上去，從而，在第二道上形成(i+1)2個(gè)a再與第一道上a的個(gè)數(shù)進(jìn)行比較。

初始i=0第2道a個(gè)數(shù)為02aaa…………aBn個(gè)aBBB…………BB02=0BBB…………BB比較第一、二道上a的個(gè)數(shù)如果相等，就接收；

第3道設(shè)置為2*0+1aaa…………aBBBB…………BB02aBB…………BB2*0+1第2道設(shè)置為12i=1(3道a加入2道)aaa…………aBaBB…………BB12aBB…………BB比較第一、二道上a的個(gè)數(shù)如果相等，就接收；二道a多，拒絕；第3道設(shè)置為2*1+1aaa…………aBnaBB…………BB12aaaB…………BB2*1+1第2道設(shè)置為22i=2aaa…………aBnaaaaB………BB22aaaB…………BB比較第一、二道上a的個(gè)數(shù)如果相等，就接收；二道a多，拒絕；第3道設(shè)置為2*2+1aaa……………aBnaaaaB……….…BB22aaaaaB…………BB2*2+1第2道設(shè)置為32i=3aaa…………aBnaaaaaaaaaB….BB32aaaaaB………BB比較第一、二道上a的個(gè)數(shù)如果相等，就接收；二道a多，拒絕；第3道設(shè)置為2*3+1aaa…………aBnaaaaaaaaaB…BB32aaaaaaaB……BB2*3+1第2道設(shè)置為42i=4aaa………………..…aBnaaaaaaaaaaaaaaaaB…BB42aaaaaaaB………….…BB比較第一、二道上a的個(gè)數(shù)如果相等，就接收；二道a多，拒絕；上述動(dòng)作一直重復(fù)，直到第一、二道上a的個(gè)數(shù)相等，則接收；或者第一道的a的個(gè)數(shù)小于第二道上a的個(gè)數(shù)，則拒絕該輸入串。從i=2過渡i=3到時(shí)，圖靈機(jī)輸入帶為：改進(jìn)算法準(zhǔn)備工作：

特殊情況：n=0或n=1進(jìn)行處理；

二道存放aaaa；三道存放aaa(1)二道與一道的a比較：

相等，接收；

二道a多，拒絕；

一道a多，轉(zhuǎn)(2)(2)三道增加aa(3)三道的a復(fù)制到二道；轉(zhuǎn)(1)

準(zhǔn)備工作<start,[B,B,B],accept,[B,B,B]，N>n=0<start,[a,B,B],aGE1,[a,a,a],R>二、三道存放a<aGE1,[B,B,B],accept,[B,B,B],N>n=1<aGE1,[a,B,B],aGT1,[a,a,a],R>二、三道存放aa<aGT1,[x,B,B],a_3,[x,a,a],R>二、三道存放aaa<a_3,[x,B,B],1_m_2_ready,[x,a,B],L>二道再存a

此時(shí)，

二道存放aaaa；三道存放aaa（1）一道和二道進(jìn)行比較<1_m_2_ready,[x,a,z],1_m_2_ready,[x,a,x],L>

左移到左端點(diǎn)<1_m_2_ready,┣,1_m_2,┣,R>開始比較<1_m_2,[a,a,x],1_m_2,[a,a,x],R><1_m_2,[B,a,x],refuse,[B,a,x],N>二道a多，拒絕<1_m_2,[B,B,x],accept,[B,B,x],N>接收<1_m_2,[a,B,x],3_add_2a_ready,[a,B,x],L>二道a少（2）三道增加2個(gè)a<3_add_a_ready,[x,y,B],3_add_a_ready,[x,y,B],L>左移找到第三道最后的a<3_add_a_ready,[x,y,a],3_add_1a,[x,y,a],R><3_add_1a,[x,y,B],3_add_2a,[x,y,a],R>增加1個(gè)a<3_add_2a,[x,y,B],3_copy_2_ready,[x,y,a],L>

再增加1個(gè)a，三道a準(zhǔn)備復(fù)制到二道(3)三道a復(fù)制到二道末尾<3_copy_2_ready,[x,y,z],3_copy_2_ready,[x,y,z],L>

左移到左端點(diǎn)<3_copy_2_ready,┣,3_copy_2,┣,R>開始復(fù)制<3_copy_2,[x,a,a],seek_2_B,[x,a,b],R>

三道a改為b，向右尋找二道末尾<seek_2_B,[x,a,z],seek_2_B,[x,a,z],R><seek_2_B,[x,B,z],seek_3_b,[x,a,z],L>

復(fù)制1個(gè)a，向左尋找三道b<seek_3_b,[x,a,B],seek_3_b,[x,a,B],L>跳過3-B<seek_3_b,[x,a,a],seek_3_b,[x,a,a],L>

跳過3-a<seek_3_b,[x,a,b],seek_3_a,[x,a,a],R>

將b還原為a

向右尋找三道是否還有a需要復(fù)制<seek_3_a,[x,a,a],seek_2_B,[x,a,b],R>

三道還有a，繼續(xù)復(fù)制<seek_3_a,[x,a,B],1_m_2_ready,[x,a,B],L>

復(fù)制結(jié)束，繼續(xù)比較一道和二道思考：一、二道比較的的第2種算法讀寫頭在第二道的最后一個(gè)a處<a_3,[x,B,B],1_m_2,[x,a,B],R>第一次<seek_3_a,[x,a,B],1_m_2,[x,a,B],R><1_m_2,[a,B,x],3_add_2a_ready,[a,B,x],L>

二道a少<1_m_2,[B,B,x],LEFT,[B,B,x],L><LEFT,[B,a,x],LEFT,[B,B,x],L>拒絕<LEFT,[a,a,x],accept,[B,B,x],L>接收思考：三道a復(fù)制到二道的第2種算法：從三道最后的a開始復(fù)制需要注意第一次復(fù)制的特殊性aaaaBaaaa……..aBaaaaaBaaaa…aB6.3.5圖靈機(jī)的查訖技術(shù)在TM的工作中，有時(shí)需要對(duì)已經(jīng)掃描過的符號(hào)進(jìn)行檢查。為了區(qū)分帶上的某個(gè)符號(hào)是否已檢查過，可以使用查訖符號(hào)“√”進(jìn)行標(biāo)記需要使用多道技術(shù)存儲(chǔ)查訖符號(hào)初始時(shí)，所有帶上符號(hào)的查訖標(biāo)記都標(biāo)記為“B”。例6-25構(gòu)造TM

L(M)={w2w|w∈{0，1}+}分析依次比較2前后的符號(hào)將帶分成兩條道第一條道上存放輸入符號(hào)串

第二條道上存放檢查標(biāo)記。初始輸入帶上的符號(hào)情況為：┣a1a2…an2b1b2…bmB…┣BB…BBBB…BB…比較時(shí)，使用存儲(chǔ)技術(shù)，將2前面的待比較符號(hào)存儲(chǔ)，再與2后面相應(yīng)位置的符號(hào)進(jìn)行比較。某個(gè)時(shí)刻，輸入帶上的符號(hào)情況┣a1a2…an2b1b2…bmB…┣

…BB

B…BB…M的初始狀態(tài)為start令a=0或1，b=0或1<start，┣，[q1，B]，┣，R>記錄待比較符號(hào)：<[q1,B],[a,B]，[q2，a]，[a，√]，R>讀頭右移到2的后面：

<[q2，a]，[b，B]，[q2，a]，[b，B]，R><[q2，a]，[2，B]，[q3，a]，[2，B]，R>找到要比較的位置：<[q3，a],[b，√],[q3，a],[b，√],R>比較后相同則繼續(xù)：2個(gè)a必須同為0或1<[q3，a],[a，B],[q4，B],[a，√],L>讀頭左移到2前：<[q4，B]，[b，√]，[q4，B]，[b，√]，L><[q4，B]，[2，B]，[q5，B]，[2，B]，L>讀頭左移過2后有兩種情況未比較完<[q5，B]，[b，B]，[q6，B]，[b，B]，L>

已比較完<[q5，B]，[b，√]，[q7，B]，[b，√]，R>未比較完時(shí)讀頭左移到待比較符號(hào)：<[q6，B],[b，B],[q6，B],[b，B]，L><[q6,B],[b,√],[q1，B],[b，√],R>已比較完則看右邊是否處理完：<[q7，B],[2，B],[q8，B],[2，B]，R><[q8，B],[b,√],[q8，B],[b，√],R><[q8，B],[B，B],[q9，B],[B，B],N>6.3.5圖靈機(jī)的子程序技術(shù)

與通常的程序設(shè)計(jì)技術(shù)相似子程序的思想在TM的構(gòu)造中也十分重要。子程序技術(shù)的使用，可以將復(fù)雜的問題進(jìn)行分解（化簡(jiǎn)），同時(shí)，也可以將TM的構(gòu)造“模塊化”TM的子程序技術(shù)的基本思想是將TM中需要重復(fù)使用的功能分解出來，使用一個(gè)子TM實(shí)現(xiàn)該功能（子程序）完成整個(gè)功能的圖靈機(jī)為M（主程序）完成某個(gè)特定功能的子圖靈機(jī)為M’（子程序）子圖靈機(jī)M’

從狀態(tài)q開始到一個(gè)狀態(tài)f結(jié)束狀態(tài)q、f是圖靈機(jī)M的兩個(gè)一般狀態(tài)當(dāng)圖靈機(jī)M進(jìn)入狀態(tài)q時(shí)，就啟動(dòng)M’（相當(dāng)于調(diào)用子程序）；當(dāng)M’進(jìn)入狀態(tài)f時(shí)就返回到M（相當(dāng)于子程序結(jié)束）。注意：子圖靈機(jī)M’中可以有多個(gè)狀態(tài)但僅有兩個(gè)狀態(tài)（即M’的開始狀態(tài)q和接收狀態(tài)f）是與主程序的圖靈機(jī)M共用的子圖靈機(jī)M’的其他狀態(tài)是私有的，不能被主程序的圖靈機(jī)M所使用。例6-26構(gòu)造TM，完成正整數(shù)的乘法運(yùn)算。正整數(shù)的乘法運(yùn)算的數(shù)學(xué)公式：m×n=(1+1+…1)×nm個(gè)1使用TM實(shí)現(xiàn)正整數(shù)的乘法運(yùn)算TM的輸入帶上存放串0m10n，處理后，使得帶上的串變?yōu)?m*n形式處理該問題的一般的方法為：當(dāng)從1的左邊消去一個(gè)0后，在0n的后面增加n個(gè)0(補(bǔ)1作為分隔標(biāo)記)；當(dāng)1左邊的所有的0（共有m個(gè)）消完后，再消去多余的符號(hào)（兩個(gè)1和原來的0n），就得到了0m*n形式。在0n后面添加n個(gè)0的過程是重復(fù)的，可以使用子程序技術(shù)。在某個(gè)時(shí)刻，TM輸入帶上的符號(hào)為：Bh0m-h10n10h*n已經(jīng)完成(1+1+1+…+1)*n

h個(gè)ＴM的狀態(tài)函數(shù)分為3部分：1)初始化：將第一個(gè)0變?yōu)锽，并在最后一個(gè)0后面設(shè)置標(biāo)記為1該標(biāo)記表明了增加0的開始位置

使得增加的0在第二個(gè)1的后面；并將讀/寫頭移動(dòng)到n個(gè)0中的第一個(gè)處。則格局變換為：q00m10n=>*B0m-11sub_start0n1此時(shí)，只是消去了第一個(gè)0設(shè)置標(biāo)記1；但還沒有在后面增加0即將掃描0n的第一個(gè)02)主控程序：初始化后，狀態(tài)變?yōu)閟ub_start。

sub_start是子程序圖靈機(jī)的開始狀態(tài)，調(diào)用子程序，將n個(gè)0增加到第二個(gè)1的后面。當(dāng)退出子程序時(shí)，狀態(tài)為sub_endsub_end就是子程序圖靈機(jī)的結(jié)束狀態(tài)然后將讀/寫頭移動(dòng)到前面m個(gè)0中剩余0左邊第一個(gè)0處并將這個(gè)0改為B，準(zhǔn)備進(jìn)入下次循環(huán)對(duì)應(yīng)的格局轉(zhuǎn)換為：Bhq00m-h10n10(h-1)×n=>*Bh0m-h1sub_start0n10(h-1)×n…進(jìn)入子程序

復(fù)制n個(gè)0Bh0m-h1sub_end0n10h×n=>*Bh+1q00m-h-110n10h×n當(dāng)找不到前面m個(gè)0中剩余的0時(shí)，表示乘法計(jì)算工作已經(jīng)結(jié)束，需要消去多余的符號(hào)（兩個(gè)1和原來的0n），得到最后的結(jié)果串