劉練珍++張向陽



摘 要:眾所周知,概念的定義形式是理解、推導(dǎo)和掌握與之相關(guān)的性質(zhì)及結(jié)論的基礎(chǔ)。在教學(xué)中,如何更好闡述概念,幫助學(xué)生分析概念之間的聯(lián)系,從而更好理解和應(yīng)用此概念是課堂教學(xué)的主要任務(wù),是一種精確的通用計(jì)算機(jī)模型。通過對教科書上常見的三種不同圖靈機(jī)概念進(jìn)行分析,闡明了它們在計(jì)算能力上的等價(jià)性,使在教學(xué)中能幫助學(xué)生更深入理解該概念。
關(guān)鍵詞:圖靈機(jī) 轉(zhuǎn)移函數(shù) 讀寫頭 等價(jià)
中圖分類號:TP301 文獻(xiàn)標(biāo)識碼:A 文章編號:1674-098X(2016)10(b)-0162-03
圖靈機(jī)(Turing machine, TM)是由圖靈在1936年提出的,它是一種精確的通用計(jì)算機(jī)模型,能模擬實(shí)際計(jì)算機(jī)的所有計(jì)算行為[1-2]。近年來,很多學(xué)者對圖靈機(jī)進(jìn)行了研究,如在文獻(xiàn)[3]中,王強(qiáng)證明了四元圖靈機(jī)與五元圖靈機(jī)的等價(jià)性;文獻(xiàn)[4]研究了一種三狀態(tài)圖靈機(jī)的設(shè)計(jì);文獻(xiàn)[5]研究了圖靈機(jī)與Petri網(wǎng)。進(jìn)一步,文獻(xiàn)[6]提出了量子圖靈機(jī)的概念并研究了它的性質(zhì)。
眾所周知,概念的定義形式是理解、推導(dǎo)和掌握與之相關(guān)的性質(zhì)及結(jié)論的基礎(chǔ)。在教學(xué)中,如何更好闡述概念, 幫助學(xué)生分析概念之間的聯(lián)系,從而更好理解和應(yīng)用此概念是課堂教學(xué)的主要任務(wù)。圖靈機(jī)是《計(jì)算理論導(dǎo)引》課程里的一個(gè)基本概念,它在可計(jì)算性理論及計(jì)算復(fù)雜性理論研究中起著重要作用。近幾年來,筆者在從事《計(jì)算理論導(dǎo)引》課程的教學(xué)中,采用了幾種不同類型的教材[1-2,7-8],發(fā)現(xiàn)這些教材中對圖靈機(jī)概念的描述在形式上不盡相同,但教材上卻沒有明確指出這些不同定義形式之間的等價(jià)性。因此,深入剖析不同圖靈機(jī)概念之間的關(guān)系可以幫助學(xué)生在學(xué)習(xí)過程中更好理解和掌握圖靈機(jī),同時(shí)也為圖靈機(jī)的應(yīng)用奠定基礎(chǔ)。下面先給出教科書上常見的三種不同圖靈機(jī)概念的描述。
1 預(yù)備知識
定義1([7])圖靈機(jī)M是一個(gè)七元組:
其中:
Q為狀態(tài)的有窮集合,,q為M的一個(gè)狀態(tài);
q0為為M的開始狀態(tài)。對于一個(gè)給定的輸入串,M從狀態(tài)q0啟動(dòng),讀寫頭注視著輸入帶的最左端的符號;
F為是M的終止?fàn)顟B(tài)集合,為M的一個(gè)終止?fàn)顟B(tài)。一般地,一旦M進(jìn)入終止?fàn)顟B(tài),它就停止運(yùn)行;
為帶符號表(tape symbol)。為M的一個(gè)帶符號,表示在M的運(yùn)行過程中,X可以在某一時(shí)刻出現(xiàn)在輸入帶上。
為稱為空白符(blank symbol),含有空白符的帶方格被認(rèn)為是空的;
為為輸入字母表。為M的一個(gè)輸入符號。除了空白符號之外,只有中的符號才能在M啟動(dòng)時(shí)出現(xiàn)在輸入帶上;
δ為為M的轉(zhuǎn)移函數(shù)。
(i)表示M在狀態(tài)q讀入符號X,將狀態(tài)改為p,并在這個(gè)X所在的帶方格中印刷符號Y,然后將讀寫頭向右移動(dòng)一格。
(ii)表示M在狀態(tài)q讀入符號X,將狀態(tài)改為p,并在這個(gè)X所在的帶方格中印刷符號Y,然后將讀寫頭向左移動(dòng)一格。
定義2([1,2])圖靈機(jī)是一個(gè)七元組
,其中:,都是有窮集合。
(1)并且Q為狀態(tài)集;
(2)為輸入字母表,不包括特殊空白符號;
(3)為帶字母表,其中:;
(4)是轉(zhuǎn)移函數(shù)。
若機(jī)器處于狀態(tài)q,讀寫頭所在的帶方格內(nèi)包含符號,當(dāng)時(shí),機(jī)器在所在的帶方格內(nèi)寫下b以取代,然后將讀寫頭向右移動(dòng)一格,并進(jìn)入狀態(tài)p。
若機(jī)器處于狀態(tài)q,讀寫頭所在的帶方格內(nèi)包含符號,當(dāng)時(shí),機(jī)器在所在的帶方格內(nèi)寫下b以取代,然后將讀寫頭向左移動(dòng)一格,并進(jìn)入狀態(tài)p。
為起始狀態(tài);
為接受狀態(tài);
為拒絕狀態(tài),且。
定義3([8])圖靈機(jī)是一個(gè)五元組,其中
Q為狀態(tài)的有窮集。
為帶字母表,包括空白符號和左端點(diǎn)符號,但不包含符號←和→。
為起始狀態(tài);
為停止?fàn)顟B(tài)集合。
是轉(zhuǎn)移函數(shù),使得:
對所有的,如果,則。
對所有的且,如果,則。
2 分析
下面對上述三種定義進(jìn)行分析。
相同點(diǎn):上述三個(gè)定義都含有有窮狀態(tài)集、起始狀態(tài)、帶字母表、停止?fàn)顟B(tài)集、空白符號及轉(zhuǎn)移函數(shù)。
不同點(diǎn):
(1)帶字母表不同:定義3中的帶字母表除了包含字母表及空白符號外,還包含左端點(diǎn)符號,但定義1及定義2的帶字母表不包含左端點(diǎn)符號,只包含字母表及空白符號。
(2)停止?fàn)顟B(tài)集合不同:定義1的停止?fàn)顟B(tài)集合只包含接受狀態(tài),沒有拒絕狀態(tài)。定義2的停止?fàn)顟B(tài)集合只包含一個(gè)接受狀態(tài),一個(gè)拒絕狀態(tài)。定義3的停止?fàn)顟B(tài)集合既包含接受狀態(tài)又包含拒絕狀態(tài)。
(3)轉(zhuǎn)移函數(shù)不同:定義1和定義2所定義的轉(zhuǎn)移函數(shù)都是從集合到集合的一個(gè)映射,對中的任一個(gè)元素,圖靈機(jī)既要在讀寫頭所在的帶方格內(nèi)印刷一個(gè)字符,又要將讀寫頭向左或向右移動(dòng)一格。定義3的轉(zhuǎn)移函數(shù)是從到的一個(gè)映射,對中的任一元素,圖靈機(jī)或者在讀寫頭所在的帶方格內(nèi)印刷一個(gè)字符,或者將讀寫頭向左或向右移動(dòng)。
(4)左端點(diǎn)符號不同:定義3中明確給出了左端點(diǎn)符號, 并規(guī)定在任何狀態(tài)下,如果讀寫頭所在的帶方格是左端點(diǎn)符號,則圖靈機(jī)的讀寫頭必須向右移動(dòng)一個(gè)帶方格。定義1和定義2中沒有給出左端點(diǎn)符號,但在計(jì)算時(shí)要求若圖靈機(jī)讀寫頭處于帶的最左端方格,即使轉(zhuǎn)移函數(shù)指示的是←,此時(shí)讀寫頭也必須停在原地不動(dòng)。
上述三種定義雖然在形式上是不同的,但是它們在能力上卻是等價(jià)的,下面討論它們的等價(jià)性。
命題1:定義1與定義2是等價(jià)的,即:若M_1和M_2是由定義1和定義2所分別定義的圖靈機(jī),則L(M_1)=L(M_2)。
證明:顯然,由定義2所定義的圖靈機(jī)都是定義1所定義的圖靈機(jī),即:若M是滿足定義2的圖靈機(jī),那么M滿足定義1。
反過來,設(shè)是由定義1定義的圖靈機(jī),則構(gòu)造圖靈機(jī)如下:
,,,,其中轉(zhuǎn)移函數(shù)定義為,對任意的。
(1)如果,那么令;
(2)如果,那么令;
(3)如果,那么令;
(4)如果,那么令。
顯然,圖靈機(jī)N是定義2所定義的圖靈機(jī)。綜上可知,定義1與定義2是等價(jià)的。
文獻(xiàn)[3]討論了四元圖靈機(jī)與五元圖靈機(jī)的等價(jià)性問題,并給出了四元圖靈機(jī)和五元圖靈機(jī)的轉(zhuǎn)換算法。在下文中,將文獻(xiàn)[3]的算法應(yīng)用到定義2和定義3,得到了如下結(jié)論。
3 結(jié)語
雖然在不同的教材中圖靈機(jī)的概念在形式上不盡相同, 但由命題1和命題2可知,它們在能力上完全等價(jià)。形式上,三種不同定義各有側(cè)重,即定義1和定義2側(cè)重于描述圖靈機(jī)在每一個(gè)狀態(tài)下讀、寫及轉(zhuǎn)移。定義3則側(cè)重于圖靈機(jī)不僅可以讀、寫,而且其讀寫頭還可以左移、右移或保持不變。如果在教學(xué)中,適當(dāng)增加圖靈機(jī)等價(jià)模型的實(shí)際應(yīng)用內(nèi)容,不僅可以幫助學(xué)生更好理解圖靈機(jī)概念,還能激起學(xué)生對學(xué)習(xí)的興趣,培養(yǎng)學(xué)生自學(xué)和探索的能力。
參考文獻(xiàn)
[1] Michael Sipser,Introduction to the theory of computation (Second Edition)[M].北京:機(jī)械工業(yè)出版社,2006:140-142.
[2] Michael Sipser,著.計(jì)算理論導(dǎo)引[M].唐常杰,陳鵬,向勇,劉齊宏,譯.北京:機(jī)械工業(yè)出版社,2006:87-88.
[3] 王強(qiáng).四元圖靈機(jī)與五元圖靈機(jī)的等價(jià)性[J].計(jì)算機(jī)科學(xué),2003(31):192-193.
[4] 丁勤.一種三狀態(tài)圖靈機(jī)的設(shè)計(jì)[J].淮陰師范學(xué)院學(xué)報(bào):自然科學(xué)版,2006(5):158-161.
[5] 宋文,牟行軍.計(jì)算的模型:圖靈機(jī)與Petri網(wǎng)[J].西華大學(xué)學(xué)報(bào):自然科學(xué)版,2012(31):1-6.
[6] 李永明,李平.基于量子邏輯的圖靈機(jī)及其通用性[J].計(jì)算機(jī)學(xué)報(bào),2012(35):1407-1420.
[7] 蔣宗禮,姜守旭.形式語言與自動(dòng)機(jī)理論[M].2版.北京:清華大學(xué)出版社,2007:282-283.
[8] Harry R.Lewis,Christos H.Papadimitriou, Elements of the theory of Computation(Second Edition)[M].北京:清華大學(xué)出版社,1998:180-182.