圖靈機(jī)概念的教學(xué)思考

劉練珍++張向陽

摘 要：眾所周知，概念的定義形式是理解、推導(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.