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

1、 第六章第六章 圖靈機(jī)圖靈機(jī) 圖靈機(jī)圖靈機(jī)(即即TuringM-TM) 由由A.Turing于于1936年，在論文年，在論文可計(jì)算數(shù)字及其在判斷性問題可計(jì)算數(shù)字及其在判斷性問題中的應(yīng)用中的應(yīng)用里提出。里提出。 TM是可計(jì)算性的數(shù)學(xué)模型是可計(jì)算性的數(shù)學(xué)模型 可計(jì)算的特點(diǎn)是可計(jì)算的特點(diǎn)是: 有窮、離散、有窮、離散、機(jī)械執(zhí)行、停機(jī)機(jī)械執(zhí)行、停機(jī)。 為計(jì)算機(jī)的發(fā)展奠定了為計(jì)算機(jī)的發(fā)展奠定了理論基礎(chǔ)理論基礎(chǔ)。圖靈圖靈:計(jì)算機(jī)理論之父計(jì)算機(jī)理論之父馮諾依曼馮諾依曼:計(jì)算機(jī)體系結(jié)構(gòu)之父計(jì)算機(jī)體系結(jié)構(gòu)之父 圖靈機(jī)可以模擬電子計(jì)算機(jī)的圖靈機(jī)可以模擬電子計(jì)算機(jī)的計(jì)計(jì)算能力算能力。 使用圖靈機(jī)可以解決計(jì)算機(jī)程序使用

2、圖靈機(jī)可以解決計(jì)算機(jī)程序的的可計(jì)算問題可計(jì)算問題。 圖靈機(jī)的圖靈機(jī)的構(gòu)造技術(shù)構(gòu)造技術(shù)類似于計(jì)算機(jī)類似于計(jì)算機(jī)的的編程編程(設(shè)計(jì)指令設(shè)計(jì)指令)技術(shù)技術(shù)。6.1 圖靈機(jī)的基本模型圖靈機(jī)的基本模型 6.1.1 圖靈機(jī)的定義圖靈機(jī)的定義 圖靈機(jī)的圖靈機(jī)的物理模型物理模型a1a2a3 aj anan+1FSC一個(gè)有限狀態(tài)控制器一個(gè)有限狀態(tài)控制器(FSC)一個(gè)外部的存儲(chǔ)設(shè)備一個(gè)外部的存儲(chǔ)設(shè)備 可以向右擴(kuò)展的無限長度帶可以向右擴(kuò)展的無限長度帶 帶上具有帶上具有左端點(diǎn)左端點(diǎn)，使用，使用“”表示表示l圖靈機(jī)直接掃描輸入帶上左端點(diǎn)右邊圖靈機(jī)直接掃描輸入帶上左端點(diǎn)右邊的的第一個(gè)符號(hào)第一個(gè)符號(hào)。 帶分解為單元，每個(gè)單

3、元可以為帶分解為單元，每個(gè)單元可以為空或存放字母表上的字母符號(hào)空或存放字母表上的字母符號(hào) 帶的空白單元標(biāo)記為帶的空白單元標(biāo)記為B 有限狀態(tài)控制器通過一個(gè)有限狀態(tài)控制器通過一個(gè)讀讀/寫頭寫頭與帶進(jìn)行耦合。與帶進(jìn)行耦合。 在某個(gè)時(shí)刻，有限狀態(tài)控制器處在某個(gè)時(shí)刻，有限狀態(tài)控制器處于某個(gè)狀態(tài)，讀于某個(gè)狀態(tài)，讀/寫頭將掃描帶上的寫頭將掃描帶上的一個(gè)單元一個(gè)單元 依照依照狀態(tài)狀態(tài)和掃描到的帶上和掃描到的帶上符號(hào)符號(hào)，圖靈機(jī)將有一個(gè)圖靈機(jī)將有一個(gè)動(dòng)作動(dòng)作如下：如下： 有限狀態(tài)控制器的有限狀態(tài)控制器的狀態(tài)狀態(tài)進(jìn)行進(jìn)行改變改變； 把剛剛掃描過的單元上符號(hào)擦除掉，把剛剛掃描過的單元上符號(hào)擦除掉，并并印刷上一個(gè)新的

4、符號(hào)印刷上一個(gè)新的符號(hào)（有可能印刷上（有可能印刷上與原來符號(hào)相同的符號(hào)）；與原來符號(hào)相同的符號(hào)）； 讀讀/寫頭向左或者向右寫頭向左或者向右移動(dòng)移動(dòng)一個(gè)單元；一個(gè)單元；或者讀或者讀/寫頭寫頭不移動(dòng)不移動(dòng)。五元式描述動(dòng)作 其中：其中：x，W （ 的的增廣集合增廣集合） 圖靈機(jī)處于狀態(tài)圖靈機(jī)處于狀態(tài)q，掃描到符號(hào)，掃描到符號(hào)x，則則狀態(tài)變換為狀態(tài)變換為q，印刷上新的符號(hào)，印刷上新的符號(hào)W，讀讀/寫頭寫頭向左向左、或、或向右向右 或或不移動(dòng)不移動(dòng)。例例6-1 用用TM接收接收 語言語言a2n |n0 圖靈機(jī)帶上符號(hào)串為：圖靈機(jī)帶上符號(hào)串為： aaaaaaB 圖靈機(jī)初始處于狀態(tài)圖靈機(jī)初始處于狀態(tài)even

5、，將要掃描，將要掃描第一個(gè)第一個(gè)a，則，則 /可省略可省略l若帶上若帶上a的個(gè)數(shù)為偶數(shù)，的個(gè)數(shù)為偶數(shù)， 則圖靈機(jī)經(jīng)過多個(gè)動(dòng)作后，處于則圖靈機(jī)經(jīng)過多個(gè)動(dòng)作后，處于接收狀態(tài)接收狀態(tài)accept；l若帶上若帶上a的個(gè)數(shù)為奇數(shù)的個(gè)數(shù)為奇數(shù)， 根據(jù)根據(jù) ，圖靈機(jī)，圖靈機(jī)將不會(huì)停機(jī)，可以永遠(yuǎn)繼續(xù)下去將不會(huì)停機(jī)，可以永遠(yuǎn)繼續(xù)下去 這與其它的自動(dòng)機(jī)不同，即圖靈這與其它的自動(dòng)機(jī)不同，即圖靈機(jī)機(jī)可能會(huì)可能會(huì)導(dǎo)致導(dǎo)致永不停止永不停止的計(jì)算。的計(jì)算。例例6-2 語言為語言為a2n|n0定義定義6-1 圖靈機(jī)是一個(gè)五元式圖靈機(jī)是一個(gè)五元式lTM=(Q， q0， q，) Q是有限狀態(tài)集合；是有限狀態(tài)集合； 是字母表的有限

6、集合是字母表的有限集合 =BA；的增廣集合，的增廣集合，即即輸入帶上符號(hào)的集合輸入帶上符號(hào)的集合q0Q，是唯一的開始狀態(tài)，是唯一的開始狀態(tài)qQ，是唯一的接收狀態(tài)，是唯一的接收狀態(tài):QQL,R,N對于任意的對于任意的(q，x)Q(q，x)=( q，W，L，R，N) 將將記為一般形式：記為一般形式：或或 圖靈機(jī)是一個(gè)七元組圖靈機(jī)是一個(gè)七元組 TM = (Q， ， ， ， q0，B， F) F Q 終止?fàn)顟B(tài)集合；終止?fàn)顟B(tài)集合； 是帶符號(hào)集合；是帶符號(hào)集合； B 稱為空白符；稱為空白符； : Q Q R, L,N 定義定義6-2 圖靈機(jī)的格局圖靈機(jī)的格局ID w1qw2w1是讀是讀/寫頭左邊帶上的符號(hào)

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

8、B )使用使用 = 表示圖靈機(jī)的格局轉(zhuǎn)換表示圖靈機(jī)的格局轉(zhuǎn)換l若若（q，x）=( q，x，L)，則，則 r1yqxr2=l若若（q，x）=( q，x，N)，則，則 r1yqxr2=l若若（q，x）=( q，x，R)，則，則 r1yqxr2= r1qyxr2r1yqxr2r1y xqr2使用使用=+ +代表格局的代表格局的多次多次變換變換使用使用=* *代表格局的代表格局的任意次任意次變換變換定義6-4l圖靈機(jī)圖靈機(jī)M=（Q， q0， q，）在字母表在字母表上接收的語言為上接收的語言為L(M)，則則 L(M)=w|存在存在w1，w2()* 有有 =* q0ww1qw2定義6-5 完全的圖靈機(jī) 如

9、果圖靈機(jī)對于如果圖靈機(jī)對于一切輸入串一切輸入串都能夠停都能夠停機(jī)機(jī)-完全的圖靈機(jī)。完全的圖靈機(jī)。 完全的圖靈機(jī)接收的語言完全的圖靈機(jī)接收的語言L稱為稱為遞歸遞歸語言語言(圖靈可判定語言圖靈可判定語言) 6.1.2 圖靈機(jī)的構(gòu)造圖靈機(jī)的構(gòu)造例例-接收僅有一個(gè)接收僅有一個(gè)1的的0、1串串TM=(q0，q1，q2,0，1, q0，q2,)=0，1，B例例6-4 構(gòu)造圖靈機(jī)構(gòu)造圖靈機(jī) 接收語言接收語言 anbn|n0思路思路1：l當(dāng)圖靈機(jī)遇到當(dāng)圖靈機(jī)遇到a時(shí)，將時(shí)，將a改寫為改寫為# 向右尋找向右尋找b，找到，找到b，將，將b改寫為改寫為# 再向左找再向左找a 直到所有直到所有a都找完。都找完。 (向

10、左找的向左找的a是整個(gè)是整個(gè)a串串最左邊的最左邊的a)指令為指令為讀到一個(gè)讀到一個(gè)a，用，用#代替它，向右找代替它，向右找b 處于狀態(tài)處于狀態(tài)del_b，掃描到，掃描到b，用，用#代替代替它，向左尋找它，向左尋找a，（從重復(fù)循環(huán)），（從重復(fù)循環(huán)） /最右的最右的a seek_a狀態(tài)時(shí)，沒有再發(fā)現(xiàn)狀態(tài)時(shí)，沒有再發(fā)現(xiàn)a(都已被都已被#所代替所代替)，還需要，還需要檢查檢查是否所有的是否所有的b都已經(jīng)被掃描過。都已經(jīng)被掃描過。問題問題l該圖靈機(jī)能接收該圖靈機(jī)能接收anbn的所有串的所有串 但該圖靈機(jī)也能接收但該圖靈機(jī)也能接收aababb 等等 原因：使用原因：使用#代表已掃描的代表已掃描的a和和b

11、沒有保證沒有保證a和和b的的順序順序。l為了區(qū)別原來的字母為了區(qū)別原來的字母a和和b 使用使用#和和$分別代替字母分別代替字母a和和b 當(dāng)當(dāng)a和和b都識(shí)別后，帶上的串為都識(shí)別后，帶上的串為 #$B例例6-5 修改上例：修改上例：讀到一個(gè)讀到一個(gè)a，用，用#代替它，向右尋找代替它，向右尋找b處于狀態(tài)處于狀態(tài)del_b，掃描到，掃描到b，用，用$代替代替它，向左尋找它，向左尋找a，（從重復(fù)，（從重復(fù)循環(huán)循環(huán)）在在seek_a狀態(tài)時(shí)，沒有再發(fā)現(xiàn)狀態(tài)時(shí)，沒有再發(fā)現(xiàn)a（都（都已經(jīng)被已經(jīng)被#所代替）所代替） 需檢查是否所有的需檢查是否所有的b都已經(jīng)被掃描過都已經(jīng)被掃描過 還還必須注意必須注意#與與$的順序

12、的順序。例例6-6 anbn|n0的第二種算法的第二種算法l當(dāng)圖靈機(jī)遇到當(dāng)圖靈機(jī)遇到a時(shí)，將時(shí)，將a改寫為改寫為#l向右尋找向右尋找b，找到，找到b，將，將b改寫為改寫為$ 再向左找再向左找a(此時(shí)的此時(shí)的a是整個(gè)是整個(gè)a串串最左邊的最左邊的a) ，直到所有，直到所有a都找完。都找完。指令指令讀到一個(gè)讀到一個(gè)a，用，用#代替它，向右尋找代替它，向右尋找b處于狀態(tài)處于狀態(tài)del_b，掃描到，掃描到b，用，用$代替，代替，向左尋找向左尋找a，（從重復(fù)循環(huán)），（從重復(fù)循環(huán)） /跳過跳過a串串 /最右最右# /最左最左a在在seek_a狀態(tài)時(shí)，沒有再發(fā)現(xiàn)狀態(tài)時(shí)，沒有再發(fā)現(xiàn)a，需，需檢查是否所有的檢查是

13、否所有的b都已經(jīng)被掃描過。都已經(jīng)被掃描過。 某些不需要定義的規(guī)則某些不需要定義的規(guī)則 /無無a /無無a 無無b /b少少 /無無b /不可能不可能 /b多多思考思考l能否給對圖靈機(jī)的能否給對圖靈機(jī)的性能性能進(jìn)行評價(jià)？進(jìn)行評價(jià)？l對于相同的輸入串，比較兩種算法的對于相同的輸入串，比較兩種算法的 圖靈機(jī)的圖靈機(jī)的指令數(shù)量指令數(shù)量 每條每條指令的執(zhí)行次數(shù)指令的執(zhí)行次數(shù)（總次數(shù)）（總次數(shù)） 新印刷符號(hào)的數(shù)量新印刷符號(hào)的數(shù)量； 讀讀/寫頭移動(dòng)的次數(shù)寫頭移動(dòng)的次數(shù)例例6-7 anbn|n0第三種算法第三種算法思路思路: 首先檢查輸入串是否為首先檢查輸入串是否為a+b+的格式；的格式； 如果不是，則拒絕該

14、串如果不是，則拒絕該串 如果是，檢查如果是，檢查a和和b的個(gè)數(shù)是否相等。的個(gè)數(shù)是否相等。指令指令 (掃描掃描a) (掃描掃描b) (開始檢查開始檢查a和和b的個(gè)數(shù)是否相等的個(gè)數(shù)是否相等) 已經(jīng)保證順序已經(jīng)保證順序 （檢查是否有多余的（檢查是否有多余的b）例6-8接收語言接收語言 anbncn|n0lTM=（Q， start， accept，）Q=start，del_b，del_c，seek_a，check1，check2，check3，accept=a，b，c=a，b，c，B，#，$，!指令指令讀到一個(gè)讀到一個(gè)a，用，用#代替它，向右尋找代替它，向右尋找b 處于狀態(tài)處于狀態(tài)del_b時(shí)時(shí),掃描

15、到掃描到b，用，用$代替代替它，向右尋找它，向右尋找c： 處于狀態(tài)處于狀態(tài)del_c時(shí)，掃描到時(shí)，掃描到c，用，用!代替代替它，向左找它，向左找a，(從開始又重復(fù)循環(huán)從開始又重復(fù)循環(huán)) 在在seek_a狀態(tài)時(shí)，沒有再發(fā)現(xiàn)狀態(tài)時(shí)，沒有再發(fā)現(xiàn)a（都（都已經(jīng)被已經(jīng)被#所代替）所代替） 還需要檢查是否所有的還需要檢查是否所有的b和和c都已經(jīng)被都已經(jīng)被掃描過掃描過 注意注意#、$和！的順序和！的順序 識(shí)別第一個(gè)識(shí)別第一個(gè)! 跳過剩余跳過剩余!l類 似 地 ， 圖 靈 機(jī) 接 收 語 言類 似 地 ， 圖 靈 機(jī) 接 收 語 言 anbncn|n0，也有多種方法。，也有多種方法。思考：構(gòu)造構(gòu)造TM接收語言

16、接收語言aibjci+j|i,j0構(gòu)造構(gòu)造TM接收語言接收語言aibjci*j|i，j0構(gòu)造構(gòu)造TM接收語言接收語言wcwT|w(a,b)* 6.2 圖靈機(jī)作為非負(fù)整數(shù)函數(shù)計(jì)算模型圖靈機(jī)作為非負(fù)整數(shù)函數(shù)計(jì)算模型l設(shè)有設(shè)有k元函數(shù)元函數(shù)f(n1，n2，nK)=m 如果如果TM接受輸入串接受輸入串 0n110n2110nk而而“輸出輸出”符號(hào)串符號(hào)串 0m則稱則稱TM計(jì)算計(jì)算k元函數(shù)元函數(shù)f； 或稱或稱f為為TM計(jì)算的函數(shù)。計(jì)算的函數(shù)。 也稱也稱f是圖靈可計(jì)算的是圖靈可計(jì)算的。l自動(dòng)機(jī)都具有識(shí)別語言的功能自動(dòng)機(jī)都具有識(shí)別語言的功能 圖靈機(jī)還具有圖靈機(jī)還具有“計(jì)算計(jì)算”功能功能 可以規(guī)定非負(fù)整數(shù)的可

17、以規(guī)定非負(fù)整數(shù)的表示方法表示方法,從而實(shí)現(xiàn)從而實(shí)現(xiàn)非負(fù)整數(shù)的函數(shù)求值非負(fù)整數(shù)的函數(shù)求值。K元函數(shù)可以轉(zhuǎn)換為多個(gè)二元函數(shù)元函數(shù)可以轉(zhuǎn)換為多個(gè)二元函數(shù)僅考慮二元函數(shù)僅考慮二元函數(shù)l使用使用“一進(jìn)制一進(jìn)制”方式表示一個(gè)非負(fù)整方式表示一個(gè)非負(fù)整數(shù)，即數(shù)，即 使用使用0m表示整數(shù)表示整數(shù)m。l若需要計(jì)算若需要計(jì)算f(m，n)，則可以在輸入，則可以在輸入帶上存放帶上存放0m10n形式的串形式的串l圖靈機(jī)將串改寫為圖靈機(jī)將串改寫為0f(m，n)的形式，即的形式，即表示出計(jì)算表示出計(jì)算f(m，n)的結(jié)果。的結(jié)果。加法圖靈機(jī)加法圖靈機(jī)l對于非負(fù)整數(shù)對于非負(fù)整數(shù)m、n，計(jì)算，計(jì)算m+n。分析分析 圖靈機(jī)輸入圖靈機(jī)

18、輸入0m10n 需要輸出需要輸出0m+n算法：算法：將將1改寫為改寫為0，最后一個(gè)，最后一個(gè)0改寫為改寫為B(可能是可能是1改寫成的改寫成的0)lTM=（Q，,start， accept，）Q=start，q1，q2，accept=0，1=0，1，Bstart 可以是一般狀態(tài)可以是一般狀態(tài)遇到遇到B，向左找，向左找0最后的最后的0改為改為Bstart 僅為開始狀態(tài)僅為開始狀態(tài) 串為串為1或或10n 第第1個(gè)個(gè)0 跳過剩余的跳過剩余的0 遇到遇到1，改為，改為0 遇到遇到B，向左找，向左找0最后的最后的0改為改為B注意注意l掃描掃描1左邊和右邊的左邊和右邊的0的工作都由的工作都由 完成。完成。

19、整個(gè)串整個(gè)串只允許一個(gè)只允許一個(gè)1。例例6-16 構(gòu)造構(gòu)造TMl實(shí)現(xiàn)非負(fù)減法實(shí)現(xiàn)非負(fù)減法(真減法真減法)m n = m-n mn = 0 mn (即全是即全是B)或或思路思路1帶上字符串的形式為帶上字符串的形式為0m10n尋找尋找1左邊的左邊的0，刪除，刪除1右邊的右邊的0 可能在尋找可能在尋找1左邊的左邊的0時(shí)結(jié)束時(shí)結(jié)束(mn) 或者在刪除或者在刪除1右邊的右邊的0時(shí)結(jié)束時(shí)結(jié)束(mn)(1)掃描第掃描第1個(gè)個(gè)0(2) /原標(biāo)記的原標(biāo)記的1 (3) /將將1后的第后的第1個(gè)個(gè)0變?yōu)樽優(yōu)? /后加的后加的 start,1 del_0,B (4) 向左找向左找B 讀寫頭位置讀寫頭位置 轉(zhuǎn)（轉(zhuǎn)（1）

20、 重復(fù)上述動(dòng)作重復(fù)上述動(dòng)作?mn(5)n，B，L /遇到最右邊的遇到最右邊的B，表示，表示1右邊已沒有右邊已沒有0 n，1，mn ，B，L 將將1改寫為改寫為B n ，0， mn ，0，L n ，B，accept，0，N 補(bǔ)寫補(bǔ)寫1個(gè)個(gè)0，結(jié)束，結(jié)束 m n(6) start將遇到第一個(gè)將遇到第一個(gè)1 此時(shí)，輸入帶上全為，表示此時(shí)，輸入帶上全為，表示mnl在第在第(5)步開始時(shí)，輸入帶上的字符串步開始時(shí)，輸入帶上的字符串形式為：形式為： BBBBB000011 11B m-n-1 n 左邊左邊B有有n+1個(gè)個(gè)mn根據(jù)根據(jù)TM的動(dòng)作，的動(dòng)作， 在左邊消除一個(gè)在左邊消除一個(gè)0，再去，再去1的右邊找

21、的右邊找0 當(dāng)發(fā)現(xiàn)當(dāng)發(fā)現(xiàn)1的右邊已經(jīng)沒有的右邊已經(jīng)沒有0時(shí)，此時(shí)減時(shí)，此時(shí)減法工作應(yīng)該結(jié)束法工作應(yīng)該結(jié)束mn 但但左邊多消除了一個(gè)左邊多消除了一個(gè)0 因此，第（因此，第（5）步，在）步，在mn的的控制下的的控制下除了將除了將1改寫為改寫為B外外 還應(yīng)該將一個(gè)還應(yīng)該將一個(gè)0補(bǔ)寫補(bǔ)寫回來，才能結(jié)束減回來，才能結(jié)束減法工作。法工作。mnl此時(shí)，輸入帶上的字符串形式為：此時(shí)，輸入帶上的字符串形式為： BBBB0000 B m-n個(gè)個(gè) lm=n時(shí)，整個(gè)減法的結(jié)果應(yīng)該為時(shí)，整個(gè)減法的結(jié)果應(yīng)該為0l輸入帶全為輸入帶全為Bl特殊：特殊：m=n=0，則串為，則串為1BB 結(jié)束結(jié)束思路思路2 自學(xué)自學(xué)l圖靈機(jī)反復(fù)

22、進(jìn)行下面的工作：圖靈機(jī)反復(fù)進(jìn)行下面的工作： 先用先用B替換替換1左邊領(lǐng)頭的左邊領(lǐng)頭的0 向右搜尋向右搜尋1右邊的第一個(gè)右邊的第一個(gè)0，并將這個(gè)，并將這個(gè)0替換為替換為X， 然后左移到然后左移到B。重新開始循環(huán)。重新開始循環(huán)。l退出循環(huán)的條件有兩種：退出循環(huán)的條件有兩種： 1)1的左邊找不到的左邊找不到0，說明，說明mn 輸出輸出0，應(yīng)將所有非，應(yīng)將所有非B符號(hào)改寫為符號(hào)改寫為B； 2)1的右邊找不到的右邊找不到0，說明，說明mn 輸出輸出0m-n，應(yīng)將應(yīng)將1換為換為0，將，將X換為換為B。狀態(tài)轉(zhuǎn)換函數(shù)為：狀態(tài)轉(zhuǎn)換函數(shù)為：(1)開始循環(huán)，用開始循環(huán)，用B替換替換1左邊領(lǐng)頭的左邊領(lǐng)頭的0(2)向右

23、搜尋向右搜尋1。(3)向右尋向右尋1右邊的第一個(gè)右邊的第一個(gè)0,并將這個(gè)并將這個(gè)0替替換為換為X(4)左移到左移到B，重新開始循環(huán)。，重新開始循環(huán)。(5) 符合退出條件符合退出條件1)，即，即1的左邊找不到的左邊找不到0，用狀態(tài)，用狀態(tài)q4向右掃描將所有非向右掃描將所有非B符號(hào)符號(hào)改寫為改寫為B，并進(jìn)入終止?fàn)顟B(tài)，并進(jìn)入終止?fàn)顟B(tài)q6(6) 符合退出條件符合退出條件2)，即，即1的右邊找不到的右邊找不到0，用狀態(tài)，用狀態(tài)q5向左掃描將所有向左掃描將所有X改寫為改寫為B，將，將1替換為替換為0，并進(jìn)入終態(tài)，并進(jìn)入終態(tài)q6 /1換為換為0 6.3 圖靈機(jī)的構(gòu)造技術(shù)圖靈機(jī)的構(gòu)造技術(shù) 構(gòu)造構(gòu)造TM，就相當(dāng)

24、于，就相當(dāng)于編寫一個(gè)程序編寫一個(gè)程序 (指令或規(guī)則的組合指令或規(guī)則的組合)。 本節(jié)介紹的圖靈機(jī)的一些構(gòu)造技術(shù)，本節(jié)介紹的圖靈機(jī)的一些構(gòu)造技術(shù)， 這些技術(shù)具有一般性，對于圖靈機(jī)的這些技術(shù)具有一般性，對于圖靈機(jī)的構(gòu)造構(gòu)造(程序設(shè)計(jì)程序設(shè)計(jì))具有較大的意義。具有較大的意義。6.3.1 圖靈機(jī)的圖靈機(jī)的存儲(chǔ)技術(shù)存儲(chǔ)技術(shù)例例6-12 構(gòu)造構(gòu)造TM ，識(shí)別字母表，識(shí)別字母表 a,b,c上上的語言的語言L： 每個(gè)字符串的每個(gè)字符串的第一個(gè)符號(hào)第一個(gè)符號(hào)在該串中在該串中僅僅僅出現(xiàn)一次僅出現(xiàn)一次。思路： 要求：第一個(gè)符號(hào)僅僅出現(xiàn)一次要求：第一個(gè)符號(hào)僅僅出現(xiàn)一次 圖靈機(jī)可以圖靈機(jī)可以“記住記住”輸入帶上的輸入帶上

25、的第一第一個(gè)符號(hào)個(gè)符號(hào)（a或或b或者或者c）。）。使用使用二元式二元式表示表示狀態(tài)狀態(tài) 第一個(gè)分量仍然表示原來的狀態(tài)；第一個(gè)分量仍然表示原來的狀態(tài)； 第二個(gè)分量存儲(chǔ)帶上的第一個(gè)符號(hào)。第二個(gè)分量存儲(chǔ)帶上的第一個(gè)符號(hào)。 q，a、q，b和和q，c分別代表輸入分別代表輸入串的第一個(gè)符號(hào)為串的第一個(gè)符號(hào)為a、b和和c的情況。的情況。(1)掃描第一個(gè)符號(hào)，并存儲(chǔ)掃描第一個(gè)符號(hào)，并存儲(chǔ) (2) 第一個(gè)符號(hào)是第一個(gè)符號(hào)是a (3)第一個(gè)符號(hào)是第一個(gè)符號(hào)是b (4)第一個(gè)符號(hào)是第一個(gè)符號(hào)是c 結(jié)束結(jié)束(5)遇到最右的遇到最右的B，接收該串，接收該串 注意注意 直接運(yùn)用規(guī)則（直接運(yùn)用規(guī)則（1）和（）和（5）可以接

26、收）可以接收 僅僅僅僅只有一個(gè)符號(hào)只有一個(gè)符號(hào)的輸入串。的輸入串。例6-13 構(gòu)造TM，識(shí)別 a，b，c上的語言上的語言L： 每個(gè)句子的最后一個(gè)符號(hào)在該串中僅每個(gè)句子的最后一個(gè)符號(hào)在該串中僅僅出現(xiàn)一次。僅出現(xiàn)一次。思路 ： 最后個(gè)符號(hào)僅僅出現(xiàn)一次最后個(gè)符號(hào)僅僅出現(xiàn)一次 TM先將讀先將讀/寫頭移動(dòng)到帶的最后寫頭移動(dòng)到帶的最后 “記住記住”輸入帶上的輸入帶上的最后一個(gè)符號(hào)最后一個(gè)符號(hào) 向左掃描輸入帶上的其他符號(hào)向左掃描輸入帶上的其他符號(hào) 與最后一個(gè)符號(hào)進(jìn)行比較與最后一個(gè)符號(hào)進(jìn)行比較x= a,b,c (1)將讀將讀/寫頭移動(dòng)到帶的最后寫頭移動(dòng)到帶的最后start,B ?(2)存儲(chǔ)最后的符號(hào)存儲(chǔ)最后的

27、符號(hào) 向向左左掃描輸入帶上的其他符號(hào)掃描輸入帶上的其他符號(hào)遇到遇到結(jié)束結(jié)束思考：構(gòu)造TM 識(shí)別語言 1）該語言每個(gè)句子的）該語言每個(gè)句子的(倒數(shù)倒數(shù))第第n個(gè)符號(hào)個(gè)符號(hào) 在該句子中僅僅出現(xiàn)在該句子中僅僅出現(xiàn)K次。次。n=1，2，3，m；K=1，2，3，L2）該語言每個(gè)句子的）該語言每個(gè)句子的(倒數(shù)倒數(shù))第第n個(gè)符號(hào)個(gè)符號(hào) 在該句子中出現(xiàn)次數(shù)在該句子中出現(xiàn)次數(shù)不多于不多于(不少于不少于)K次。次。n=1，2，3， ，m ；K=1，2，3，L6.3.2圖靈機(jī)的移動(dòng)技術(shù)圖靈機(jī)的移動(dòng)技術(shù)在解決比較復(fù)雜的問題時(shí)在解決比較復(fù)雜的問題時(shí) TM可能需要將輸入帶上一組連續(xù)的可能需要將輸入帶上一組連續(xù)的非空符號(hào)非

28、空符號(hào)左移左移或者或者右移右移若干個(gè)單元。若干個(gè)單元。 使用使用n元式元式存儲(chǔ)存儲(chǔ)多個(gè)符號(hào)多個(gè)符號(hào) 合適的時(shí)候合適的時(shí)候再將這些符號(hào)印刷到需要再將這些符號(hào)印刷到需要的位置上。的位置上。例6-14構(gòu)造TM=a,b,c，將輸入串，將輸入串右右移兩個(gè)單元移兩個(gè)單元 使用三元組使用三元組q，a1，a2表示狀態(tài)表示狀態(tài) q表示原來的狀態(tài)；表示原來的狀態(tài)； a1、a2可以代表可以代表a、b、c設(shè)串長度設(shè)串長度=2(1)掃描第一個(gè)符號(hào)，并存儲(chǔ)掃描第一個(gè)符號(hào)，并存儲(chǔ) (2)掃描第二個(gè)符號(hào)，并存儲(chǔ)掃描第二個(gè)符號(hào)，并存儲(chǔ) (3)將將a1放在放在a3位置位置,將將a3存儲(chǔ)存儲(chǔ) (4) 將倒數(shù)第二個(gè)符號(hào)放在右邊空白單

29、元，將倒數(shù)第二個(gè)符號(hào)放在右邊空白單元，將最后一個(gè)符號(hào)存儲(chǔ)在狀態(tài)中將最后一個(gè)符號(hào)存儲(chǔ)在狀態(tài)中(5) 將最后一個(gè)符號(hào)放在帶上將最后一個(gè)符號(hào)放在帶上其中規(guī)則其中規(guī)則(3) 需要需要重復(fù)多次使用。重復(fù)多次使用。思考：思考：l當(dāng)串當(dāng)串 長度為長度為0 時(shí)時(shí)l當(dāng)串當(dāng)串 長度為長度為1 時(shí)時(shí) 本例使用三元組表示特殊狀態(tài)本例使用三元組表示特殊狀態(tài) 也可以使用二元組表示特殊狀態(tài)也可以使用二元組表示特殊狀態(tài) 如如q，a1，a2可以記為可以記為q，a1a2 （n元組也可以表示為二元組）元組也可以表示為二元組）對帶上符號(hào)進(jìn)行移動(dòng) 一般只是比較復(fù)雜的一般只是比較復(fù)雜的TM的識(shí)別任務(wù)的識(shí)別任務(wù)中的一部分工作中的一部分工作

30、 移動(dòng)本身移動(dòng)本身不會(huì)涉及不會(huì)涉及到串的接收或拒絕到串的接收或拒絕問題問題 復(fù)雜的復(fù)雜的TM可以繼續(xù)從可以繼續(xù)從end_move狀態(tài)狀態(tài)開始其他的工作開始其他的工作思考：構(gòu)造TM 將整個(gè)輸入串前兩個(gè)符號(hào)將整個(gè)輸入串前兩個(gè)符號(hào)刪除刪除。思路思路將帶上符號(hào)將帶上符號(hào)從右向左從右向左移動(dòng)兩個(gè)單元。移動(dòng)兩個(gè)單元。例6-15構(gòu)造構(gòu)造TM 輸入字母表為輸入字母表為0，1 在輸入串的開始處添加子串在輸入串的開始處添加子串10。略。略。例6 -16構(gòu)造構(gòu)造TM =a，b，c 將輸入串包含的第一個(gè)將輸入串包含的第一個(gè)abc子串子串刪除刪除。思路思路 存儲(chǔ)技術(shù)尋找到第存儲(chǔ)技術(shù)尋找到第1個(gè)個(gè)abc子串的位置子串的位

31、置 將后面的符號(hào)將后面的符號(hào)向左向左移動(dòng)三個(gè)單元。移動(dòng)三個(gè)單元。 略。略。例6-18 構(gòu)造構(gòu)造TM ，輸入字母表為，輸入字母表為0，1，要，要求求M接收語言接收語言L：該語言的每個(gè)字符串該語言的每個(gè)字符串包含包含且且僅只能包含僅只能包含一個(gè)一個(gè)101子串子串(有有且且僅有僅有一一個(gè)個(gè)101，不可不可以沒有以沒有101子串）子串） 思路思路當(dāng)識(shí)別出第一個(gè)當(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

32、，refuse，accept=0，1=0，1，B(1)掃描第一符號(hào)掃描第一符號(hào) 空串空串(2)期待期待1的出現(xiàn)的出現(xiàn) (3)已經(jīng)掃描到已經(jīng)掃描到“1”，等待可能的，等待可能的“0” (4)已經(jīng)掃描到已經(jīng)掃描到“10”，等待可能的，等待可能的“1” (5)已掃描到已掃描到101，檢查串的剩余部分，檢查串的剩余部分 (6) (7) （8）的第）的第2條指令與（條指令與（9）可以省略）可以省略(8) (9)整個(gè)輸入串中沒有整個(gè)輸入串中沒有101 結(jié)束結(jié)束(10)整個(gè)輸入串只有一個(gè)整個(gè)輸入串只有一個(gè)101 思考思考 構(gòu)造構(gòu)造TM ，接收語言，接收語言L： 該語言的每個(gè)句子必須包含該語言的每個(gè)句子必須包

33、含兩個(gè)兩個(gè)101例6-19 構(gòu)造構(gòu)造TM ，接收語言，接收語言L： 該語言的每個(gè)句子該語言的每個(gè)句子最多只能包含一個(gè)最多只能包含一個(gè)100子串（子串（可以沒有可以沒有100子串子串）。）。思路思路 接收接收1個(gè)個(gè)100子串的所有串；子串的所有串； 接收沒有接收沒有100子串的所有串。子串的所有串。例例6-23 構(gòu)造構(gòu)造TM接收語言接收語言L： 該語言的每個(gè)句子該語言的每個(gè)句子不包含不包含子串子串100。思路思路當(dāng)識(shí)別出第一個(gè)當(dāng)識(shí)別出第一個(gè)100后，就拒絕。后，就拒絕。6.3.4圖靈機(jī)的多道技術(shù)圖靈機(jī)的多道技術(shù) 為了能夠保存和處理更復(fù)雜的數(shù)據(jù)，為了能夠保存和處理更復(fù)雜的數(shù)據(jù)，可以將可以將TM的輸

34、入帶劃分為若干道的輸入帶劃分為若干道在各道上可以存放不同的符號(hào)。在各道上可以存放不同的符號(hào)。 沒有改變圖靈機(jī)的基本模型，沒有改變圖靈機(jī)的基本模型，只是將帶上符號(hào)當(dāng)做一個(gè)向量的組合只是將帶上符號(hào)當(dāng)做一個(gè)向量的組合每個(gè)符號(hào)可以是一個(gè)每個(gè)符號(hào)可以是一個(gè)K維向量（將輸入維向量（將輸入帶劃分為帶劃分為K道）。道）。單帶單帶K道的圖靈機(jī)模型道的圖靈機(jī)模型 a11 a21 ai1 an1 B a12 a22 ai2 an2 B a1k a2k aik ank B FSC狀態(tài)轉(zhuǎn)換函數(shù)狀態(tài)轉(zhuǎn)換函數(shù)一般形式為一般形式為 對于對于K道圖靈機(jī)道圖靈機(jī)一次需要掃描一個(gè)單元的多道一次需要掃描一個(gè)單元的多道3道道TM進(jìn)行二

35、進(jìn)制數(shù)加法運(yùn)算進(jìn)行二進(jìn)制數(shù)加法運(yùn)算l考慮考慮 3個(gè)基本加法規(guī)則個(gè)基本加法規(guī)則 ： 0+0 0+1 ( 1+0 ) 1+1 l還需要考慮還需要考慮進(jìn)位進(jìn)位情況情況(全加器）全加器）l第一、二道存放兩個(gè)操作數(shù)第一、二道存放兩個(gè)操作數(shù)l第三道存放計(jì)算結(jié)果第三道存放計(jì)算結(jié)果l第第2個(gè)單元存放個(gè)單元存放B（避免溢出）（避免溢出）l讀寫頭已經(jīng)在最低位讀寫頭已經(jīng)在最低位(最右端最右端)單元單元 沒有進(jìn)位沒有進(jìn)位 0+0 0+1 1+0 1+1進(jìn)位進(jìn)位 兩個(gè)數(shù)長度不一致兩個(gè)數(shù)長度不一致(左端補(bǔ)充左端補(bǔ)充B) 結(jié)束結(jié)束 思考思考l兩個(gè)數(shù)長度不一致兩個(gè)數(shù)長度不一致(左端補(bǔ)充左端補(bǔ)充0) l十進(jìn)制的加法十進(jìn)制的加法

36、l二進(jìn)制的減法二進(jìn)制的減法l十進(jìn)制的減法十進(jìn)制的減法l乘法與除法乘法與除法l軟件計(jì)算機(jī)軟件計(jì)算機(jī)例例6-24:構(gòu)造圖靈機(jī)構(gòu)造圖靈機(jī) 字母表為字母表為a，接收語言，接收語言L： an|n=0，且，且n為完全平方數(shù)為完全平方數(shù)基本數(shù)學(xué)公式：基本數(shù)學(xué)公式： (n+1)2=n2+2n+1思路使用三道的圖靈機(jī)使用三道的圖靈機(jī) 第一道存放輸入串；第一道存放輸入串； 第二、三兩道作為第二、三兩道作為“運(yùn)算器運(yùn)算器”使用：使用： 第二道存放第二道存放i2個(gè)個(gè)a 第三道存放第三道存放2*i+1個(gè)個(gè)a初始時(shí)初始時(shí) a a a a B B B B B B B B B B B 原始算法原始算法從從i=0開始開始 在第

37、二道上放在第二道上放i2個(gè)個(gè)a 比較第一道與第二道上比較第一道與第二道上a的個(gè)數(shù)的個(gè)數(shù) 如果相等，就接收；如果相等，就接收；不相等，則在第三道上設(shè)置不相等，則在第三道上設(shè)置 2*i+1個(gè)個(gè)a， 將第三道上的將第三道上的a加入到第二道上去，加入到第二道上去， 從而，在第二道上形成從而，在第二道上形成(i+1)2個(gè)個(gè)a 再與第一道上再與第一道上a的個(gè)數(shù)進(jìn)行比較。的個(gè)數(shù)進(jìn)行比較。 初始初始 i=0 第第2道道a個(gè)數(shù)為個(gè)數(shù)為02 aaa aB n個(gè)個(gè)aBBBBB 02=0BBBBB 比較第一、二道上比較第一、二道上a的個(gè)數(shù)的個(gè)數(shù)如果相等，就接收；如果相等，就接收； 第第3道設(shè)置為道設(shè)置為2*0+1aa

38、a aBBBBBB 02aBB BB 2*0+1第第2道設(shè)置為道設(shè)置為12 i=1(3道道a加入加入2道道) aaa aBaBBBB 12aBBBB比較第一、二道上比較第一、二道上a的個(gè)數(shù)的個(gè)數(shù)如果相等，就接收；如果相等，就接收；二道二道a多，拒絕；多，拒絕；第第3道設(shè)置為道設(shè)置為2*1+1aaa aB naBBBB 12aaaBBB 2*1+1第第2道設(shè)置為道設(shè)置為22 i=2aaa aB naaaaB BB 22aaaBBB比較第一、二道上比較第一、二道上a的個(gè)數(shù)的個(gè)數(shù)如果相等，就接收；如果相等，就接收；二道二道a多，拒絕；多，拒絕；第第3道設(shè)置為道設(shè)置為2*2+1aaa aB naaaa

39、B.BB 22aaaaaBBB 2*2+1第第2道設(shè)置為道設(shè)置為32 i=3aaa aB naaaaaaaaaB.BB 32aaaaaBBB比較第一、二道上比較第一、二道上a的個(gè)數(shù)的個(gè)數(shù)如果相等，就接收；如果相等，就接收；二道二道a多，拒絕；多，拒絕；第第3道設(shè)置為道設(shè)置為2*3+1aaa aB naaaaaaaaaBBB 32aaaaaaaBBB 2*3+1第第2道設(shè)置為道設(shè)置為42 i=4aaa. aB naaaaaaaaaaaaaaaaBBB 42aaaaaaaB. BB比較第一、二道上比較第一、二道上a的個(gè)數(shù)的個(gè)數(shù)如果相等，就接收；如果相等，就接收；二道二道a多，拒絕；多，拒絕； 上述

40、動(dòng)作一直重復(fù)，直到第一、二道上述動(dòng)作一直重復(fù)，直到第一、二道上上a的個(gè)數(shù)相等，則接收；的個(gè)數(shù)相等，則接收； 或者第一道的或者第一道的a的個(gè)數(shù)小于第二道上的個(gè)數(shù)小于第二道上a的個(gè)數(shù)，則拒絕該輸入串。的個(gè)數(shù)，則拒絕該輸入串。從從i=2過渡過渡i=3到時(shí)，圖靈機(jī)輸入帶為：到時(shí)，圖靈機(jī)輸入帶為： a a a a a a a a a B a a a a B B a a a a a B B 改進(jìn)算法改進(jìn)算法準(zhǔn)備工作：準(zhǔn)備工作： 特殊情況：特殊情況： n=0或或n=1 進(jìn)行處理進(jìn)行處理； 二道存放二道存放aaaa；三道存放；三道存放aaa (1) 二道與一道的二道與一道的 a比較比較： 相等，接收；相等，接

41、收； 二道二道a多，拒絕；多，拒絕； 一道一道a多，轉(zhuǎn)多，轉(zhuǎn)(2) (2)三道三道增加增加aa (3) 三道的三道的a復(fù)制復(fù)制到二道；轉(zhuǎn)到二道；轉(zhuǎn)(1) 準(zhǔn)備工作準(zhǔn)備工作 n=0 二、三道存放二、三道存放a n=1 二、三道存放二、三道存放aa 二、三道存放二、三道存放aaa 二道再存二道再存a 此時(shí)，此時(shí)， 二道存放二道存放aaaa；三道；三道存放存放aaa（1）一道和二道進(jìn)行比較）一道和二道進(jìn)行比較 左移到左端點(diǎn)左移到左端點(diǎn) 開始比較開始比較 二道二道a多，拒絕多，拒絕 接收接收 二道二道a少少（2）三道增加）三道增加2個(gè)個(gè)a 左移找到第三道最后的左移找到第三道最后的a 增加增加1個(gè)個(gè)a

42、再增加再增加1個(gè)個(gè)a，三道，三道a準(zhǔn)備復(fù)制到二道準(zhǔn)備復(fù)制到二道(3)三道三道a復(fù)制到二道末尾復(fù)制到二道末尾 左移到左移到左端點(diǎn)左端點(diǎn) 開始復(fù)制開始復(fù)制 三道三道a改為改為b，向右尋找二道末尾，向右尋找二道末尾 復(fù)制復(fù)制1個(gè)個(gè)a，向左尋找三道，向左尋找三道b 跳過跳過3-B 跳過跳過3-a 將將b還原為還原為a 向右尋找三道是否還有向右尋找三道是否還有a需要復(fù)制需要復(fù)制 三道還有三道還有a，繼續(xù)復(fù)制，繼續(xù)復(fù)制 復(fù)制結(jié)束，繼續(xù)比較一道和二道復(fù)制結(jié)束，繼續(xù)比較一道和二道思考：一、二道比較的的第思考：一、二道比較的的第2種算法種算法l讀寫頭在第二道的最后一個(gè)讀寫頭在第二道的最后一個(gè)a處處 第一次第一次

43、 二道二道a少少 拒絕拒絕 接收接收思考：思考：三道三道a復(fù)制到二道復(fù)制到二道的第的第2種算法：種算法：從三道從三道最后的最后的a開始復(fù)開始復(fù)制制需要注意第一次復(fù)制的特殊性需要注意第一次復(fù)制的特殊性aaaaB aaaa.aBaaaaaB aaaaaB6.3.5圖靈機(jī)的圖靈機(jī)的查訖查訖技術(shù)技術(shù) 在在TM的工作中，有時(shí)需要對已經(jīng)掃的工作中，有時(shí)需要對已經(jīng)掃描過的符號(hào)進(jìn)行檢查。描過的符號(hào)進(jìn)行檢查。 為了區(qū)分帶上的某個(gè)符號(hào)是否已檢查為了區(qū)分帶上的某個(gè)符號(hào)是否已檢查過，可以使用查訖符號(hào)過，可以使用查訖符號(hào)“”進(jìn)行標(biāo)記進(jìn)行標(biāo)記 需要使用多道技術(shù)存儲(chǔ)查訖符號(hào)需要使用多道技術(shù)存儲(chǔ)查訖符號(hào) 初始時(shí)，所有帶上符號(hào)

44、的查訖標(biāo)記初始時(shí)，所有帶上符號(hào)的查訖標(biāo)記都標(biāo)記為都標(biāo)記為“B”。例6-25 構(gòu)造構(gòu)造TM L(M)=w2w|w0，1+分析分析依次比較依次比較2前后的符號(hào)前后的符號(hào) 將帶分成兩條道將帶分成兩條道 第一條道上存放輸入符號(hào)串第一條道上存放輸入符號(hào)串 第二條道上存放檢查標(biāo)記第二條道上存放檢查標(biāo)記。初始初始輸入帶上的符號(hào)情況為：輸入帶上的符號(hào)情況為： a1a2 an 2 b1 b2 bm B B B B B B B B B 比較時(shí)，使用存儲(chǔ)技術(shù)，比較時(shí)，使用存儲(chǔ)技術(shù)， 將將2前面的待比較符號(hào)前面的待比較符號(hào)存儲(chǔ)存儲(chǔ)， 再與再與2后面后面相應(yīng)位置相應(yīng)位置的符號(hào)進(jìn)行比較。的符號(hào)進(jìn)行比較。某個(gè)時(shí)刻，輸入帶上

45、的符號(hào)情況某個(gè)時(shí)刻，輸入帶上的符號(hào)情況 a1a2 an 2 b1 b2 bm B B B B B B M的初始狀態(tài)為的初始狀態(tài)為start令令a=0或或1， b=0或或1 記錄待比較符號(hào)：記錄待比較符號(hào)：讀頭右移到讀頭右移到2的后面：的后面： 找到要比較的位置：找到要比較的位置： 比較后相同則繼續(xù)：比較后相同則繼續(xù)：2個(gè)個(gè)a必須同為必須同為0或或1讀頭左移到讀頭左移到2前：前：讀頭左移過讀頭左移過2后有兩種情況后有兩種情況未比較完未比較完 已比較完已比較完未比較完時(shí)讀頭左移到待比較符號(hào)：未比較完時(shí)讀頭左移到待比較符號(hào)： 已比較完則看右邊是否處理完：已比較完則看右邊是否處理完： 6.3.5圖靈機(jī)

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

47、機(jī)為完成某個(gè)特定功能的子圖靈機(jī)為M（子程序）（子程序）子圖靈機(jī)子圖靈機(jī)M 從狀態(tài)從狀態(tài)q開始開始 到一個(gè)狀態(tài)到一個(gè)狀態(tài)f結(jié)束結(jié)束狀態(tài)狀態(tài)q、f是圖靈機(jī)是圖靈機(jī)M的兩個(gè)的兩個(gè)一般狀態(tài)一般狀態(tài) 當(dāng)圖靈機(jī)當(dāng)圖靈機(jī)M進(jìn)入狀態(tài)進(jìn)入狀態(tài)q時(shí)，就啟動(dòng)時(shí)，就啟動(dòng)M（相當(dāng)于（相當(dāng)于調(diào)用調(diào)用子程序）；子程序）； 當(dāng)當(dāng)M進(jìn)入狀態(tài)進(jìn)入狀態(tài)f時(shí)就時(shí)就返回返回到到M（相當(dāng)（相當(dāng)于子程序結(jié)束）。于子程序結(jié)束）。注意： 子圖靈機(jī)子圖靈機(jī)M中可以有多個(gè)狀態(tài)中可以有多個(gè)狀態(tài) 但僅有兩個(gè)狀態(tài)（即但僅有兩個(gè)狀態(tài)（即M的的開始狀態(tài)開始狀態(tài)q和和接收狀態(tài)接收狀態(tài)f）是與主程序的圖靈機(jī)）是與主程序的圖靈機(jī)M共用的共用的 子圖靈機(jī)子圖靈機(jī)M

48、的其他狀態(tài)是的其他狀態(tài)是私有的私有的，不，不能被主程序的圖靈機(jī)能被主程序的圖靈機(jī)M所使用。所使用。例6-26構(gòu)造構(gòu)造TM ，完成正整數(shù)的乘法運(yùn)算。，完成正整數(shù)的乘法運(yùn)算。正整數(shù)的乘法運(yùn)算的數(shù)學(xué)公式：正整數(shù)的乘法運(yùn)算的數(shù)學(xué)公式： mn=(1+1+1) n m個(gè)個(gè)1使用使用TM實(shí)現(xiàn)正整數(shù)的乘法運(yùn)算實(shí)現(xiàn)正整數(shù)的乘法運(yùn)算 TM的輸入帶上存放串的輸入帶上存放串0m10n， 處理后，使得帶上的串變?yōu)樘幚砗?，使得帶上的串變?yōu)?m*n形式形式處理該問題的一般的方法為：處理該問題的一般的方法為： 當(dāng)從當(dāng)從1的左邊消去一個(gè)的左邊消去一個(gè)0后，在后，在0n的后的后面增加面增加n個(gè)個(gè)0(補(bǔ)補(bǔ)1作為分隔標(biāo)記作為分隔標(biāo)記

49、)； 當(dāng)當(dāng)1左邊的所有的左邊的所有的0（共有（共有m個(gè)）消完個(gè)）消完后，再消去后，再消去多余的符號(hào)多余的符號(hào)（兩個(gè)兩個(gè)1和原來和原來的的0n），就得到了），就得到了0m*n形式。形式。在在0n后面添加后面添加n個(gè)個(gè)0的過程是重復(fù)的，的過程是重復(fù)的， 可以使用子程序技術(shù)?？梢允褂米映绦蚣夹g(shù)。在某個(gè)時(shí)刻，在某個(gè)時(shí)刻，TM輸入帶上的輸入帶上的符號(hào)符號(hào)為：為： Bh0m-h10n10h*n已經(jīng)完成已經(jīng)完成(1+1+1+1)*n h個(gè)個(gè)M的狀態(tài)函數(shù)分為的狀態(tài)函數(shù)分為3部分：部分：l1)初始化：初始化： 將第一個(gè)將第一個(gè)0變?yōu)樽優(yōu)锽，并在最后一個(gè)，并在最后一個(gè)0后后面設(shè)置面設(shè)置標(biāo)記為標(biāo)記為1 該標(biāo)記表明了

50、該標(biāo)記表明了增加增加0的開始位置的開始位置 使得增加的使得增加的0在第二個(gè)在第二個(gè)1的后面；并將的后面；并將讀讀/寫頭移動(dòng)到寫頭移動(dòng)到n個(gè)個(gè)0中的第一個(gè)處。中的第一個(gè)處。則格局變換為：則格局變換為： q00m10n=* B0m-11sub_start0n1此時(shí)，只是消去了第一個(gè)此時(shí)，只是消去了第一個(gè)0 設(shè)置標(biāo)記設(shè)置標(biāo)記1； 但還沒有在后面增加但還沒有在后面增加0 即將掃描即將掃描0n的的第一個(gè)第一個(gè)0l2)主控程序：主控程序： 初始化初始化后，狀態(tài)變?yōu)楹螅瑺顟B(tài)變?yōu)閟ub_start。 sub_start是是子程序圖靈機(jī)的開始狀態(tài)，子程序圖靈機(jī)的開始狀態(tài)， 調(diào)用子程序，將調(diào)用子程序，將n個(gè)個(gè)0增加到第二個(gè)增加到第二個(gè)1的后面。的后面。 當(dāng)退出子程序時(shí)，狀態(tài)為當(dāng)退出子程序時(shí)，狀態(tài)為sub_end sub_end就是子程序圖靈機(jī)的結(jié)束狀態(tài)就是子程序圖靈機(jī)的結(jié)束狀態(tài) 然后將讀然后將讀/寫頭移動(dòng)到寫