劉練珍++張向陽

摘 要：眾所周知，概念的定義形式是理解、推導和掌握與之相關的性質及結論的基礎。在教學中，如何更好闡述概念，幫助學生分析概念之間的聯(lián)系，從而更好理解和應用此概念是課堂教學的主要任務，是一種精確的通用計算機模型。通過對教科書上常見的三種不同圖靈機概念進行分析，闡明了它們在計算能力上的等價性，使在教學中能幫助學生更深入理解該概念。

關鍵詞：圖靈機 轉移函數(shù) 讀寫頭 等價

中圖分類號：TP301 文獻標識碼：A 文章編號：1674-098X（2016）10（b）-0162-03

圖靈機（Turing machine， TM）是由圖靈在1936年提出的，它是一種精確的通用計算機模型，能模擬實際計算機的所有計算行為[1-2]。近年來，很多學者對圖靈機進行了研究，如在文獻[3]中，王強證明了四元圖靈機與五元圖靈機的等價性；文獻[4]研究了一種三狀態(tài)圖靈機的設計；文獻[5]研究了圖靈機與Petri網(wǎng)。進一步，文獻[6]提出了量子圖靈機的概念并研究了它的性質。

眾所周知，概念的定義形式是理解、推導和掌握與之相關的性質及結論的基礎。在教學中，如何更好闡述概念， 幫助學生分析概念之間的聯(lián)系，從而更好理解和應用此概念是課堂教學的主要任務。圖靈機是《計算理論導引》課程里的一個基本概念，它在可計算性理論及計算復雜性理論研究中起著重要作用。近幾年來，筆者在從事《計算理論導引》課程的教學中，采用了幾種不同類型的教材[1-2，7-8]，發(fā)現(xiàn)這些教材中對圖靈機概念的描述在形式上不盡相同，但教材上卻沒有明確指出這些不同定義形式之間的等價性。因此，深入剖析不同圖靈機概念之間的關系可以幫助學生在學習過程中更好理解和掌握圖靈機，同時也為圖靈機的應用奠定基礎。下面先給出教科書上常見的三種不同圖靈機概念的描述。

1 預備知識

定義1（[7]）圖靈機M是一個七元組：

其中：

Q為狀態(tài)的有窮集合，，q為M的一個狀態(tài)；

q0為為M的開始狀態(tài)。對于一個給定的輸入串，M從狀態(tài)q0啟動，讀寫頭注視著輸入帶的最左端的符號；

F為是M的終止狀態(tài)集合，為M的一個終止狀態(tài)。一般地，一旦M進入終止狀態(tài)，它就停止運行；

為帶符號表（tape symbol）。為M的一個帶符號，表示在M的運行過程中，X可以在某一時刻出現(xiàn)在輸入帶上。

為稱為空白符（blank symbol），含有空白符的帶方格被認為是空的；

為為輸入字母表。為M的一個輸入符號。除了空白符號之外，只有中的符號才能在M啟動時出現(xiàn)在輸入帶上；

δ為為M的轉移函數(shù)。

（i）表示M在狀態(tài)q讀入符號X，將狀態(tài)改為p，并在這個X所在的帶方格中印刷符號Y，然后將讀寫頭向右移動一格。

（ii）表示M在狀態(tài)q讀入符號X，將狀態(tài)改為p，并在這個X所在的帶方格中印刷符號Y，然后將讀寫頭向左移動一格。

定義2（[1，2]）圖靈機是一個七元組

，其中：，都是有窮集合。

（1）并且Q為狀態(tài)集；

（2）為輸入字母表，不包括特殊空白符號；

（3）為帶字母表，其中：；

（4）是轉移函數(shù)。

若機器處于狀態(tài)q，讀寫頭所在的帶方格內(nèi)包含符號，當時，機器在所在的帶方格內(nèi)寫下b以取代，然后將讀寫頭向右移動一格，并進入狀態(tài)p。

若機器處于狀態(tài)q，讀寫頭所在的帶方格內(nèi)包含符號，當時，機器在所在的帶方格內(nèi)寫下b以取代，然后將讀寫頭向左移動一格，并進入狀態(tài)p。

為起始狀態(tài)；

為接受狀態(tài)；

為拒絕狀態(tài)，且。

定義3（[8]）圖靈機是一個五元組，其中

Q為狀態(tài)的有窮集。

為帶字母表，包括空白符號和左端點符號，但不包含符號←和→。

為起始狀態(tài)；

為停止狀態(tài)集合。

是轉移函數(shù)，使得：

對所有的，如果，則。

對所有的且，如果，則。

2 分析

下面對上述三種定義進行分析。

相同點：上述三個定義都含有有窮狀態(tài)集、起始狀態(tài)、帶字母表、停止狀態(tài)集、空白符號及轉移函數(shù)。

不同點：

（1）帶字母表不同：定義3中的帶字母表除了包含字母表及空白符號外，還包含左端點符號，但定義1及定義2的帶字母表不包含左端點符號，只包含字母表及空白符號。

（2）停止狀態(tài)集合不同：定義1的停止狀態(tài)集合只包含接受狀態(tài)，沒有拒絕狀態(tài)。定義2的停止狀態(tài)集合只包含一個接受狀態(tài)，一個拒絕狀態(tài)。定義3的停止狀態(tài)集合既包含接受狀態(tài)又包含拒絕狀態(tài)。

（3）轉移函數(shù)不同：定義1和定義2所定義的轉移函數(shù)都是從集合到集合的一個映射，對中的任一個元素，圖靈機既要在讀寫頭所在的帶方格內(nèi)印刷一個字符，又要將讀寫頭向左或向右移動一格。定義3的轉移函數(shù)是從到的一個映射，對中的任一元素，圖靈機或者在讀寫頭所在的帶方格內(nèi)印刷一個字符，或者將讀寫頭向左或向右移動。

（4）左端點符號不同：定義3中明確給出了左端點符號， 并規(guī)定在任何狀態(tài)下，如果讀寫頭所在的帶方格是左端點符號，則圖靈機的讀寫頭必須向右移動一個帶方格。定義1和定義2中沒有給出左端點符號，但在計算時要求若圖靈機讀寫頭處于帶的最左端方格，即使轉移函數(shù)指示的是←，此時讀寫頭也必須停在原地不動。

上述三種定義雖然在形式上是不同的，但是它們在能力上卻是等價的，下面討論它們的等價性。

命題1：定義1與定義2是等價的，即：若M_1和M_2是由定義1和定義2所分別定義的圖靈機，則L（M_1）=L（M_2）。

證明：顯然，由定義2所定義的圖靈機都是定義1所定義的圖靈機，即：若M是滿足定義2的圖靈機，那么M滿足定義1。

反過來，設是由定義1定義的圖靈機，則構造圖靈機如下：

，，，，其中轉移函數(shù)定義為，對任意的。

（1）如果，那么令；

（2）如果，那么令；

（3）如果，那么令；

（4）如果，那么令。

顯然，圖靈機N是定義2所定義的圖靈機。綜上可知，定義1與定義2是等價的。

文獻[3]討論了四元圖靈機與五元圖靈機的等價性問題，并給出了四元圖靈機和五元圖靈機的轉換算法。在下文中，將文獻[3]的算法應用到定義2和定義3，得到了如下結論。

3 結語

雖然在不同的教材中圖靈機的概念在形式上不盡相同， 但由命題1和命題2可知，它們在能力上完全等價。形式上，三種不同定義各有側重，即定義1和定義2側重于描述圖靈機在每一個狀態(tài)下讀、寫及轉移。定義3則側重于圖靈機不僅可以讀、寫，而且其讀寫頭還可以左移、右移或保持不變。如果在教學中，適當增加圖靈機等價模型的實際應用內(nèi)容，不僅可以幫助學生更好理解圖靈機概念，還能激起學生對學習的興趣，培養(yǎng)學生自學和探索的能力。

參考文獻

[1] Michael Sipser，Introduction to the theory of computation （Second Edition）[M].北京：機械工業(yè)出版社，2006：140-142.

[2] Michael Sipser，著.計算理論導引[M].唐常杰，陳鵬，向勇，劉齊宏，譯.北京：機械工業(yè)出版社，2006：87-88.

[3] 王強.四元圖靈機與五元圖靈機的等價性[J].計算機科學，2003（31）：192-193.

[4] 丁勤.一種三狀態(tài)圖靈機的設計[J].淮陰師范學院學報：自然科學版，2006（5）：158-161.

[5] 宋文，牟行軍.計算的模型：圖靈機與Petri網(wǎng)[J].西華大學學報：自然科學版，2012（31）：1-6.

[6] 李永明，李平.基于量子邏輯的圖靈機及其通用性[J].計算機學報，2012（35）：1407-1420.

[7] 蔣宗禮，姜守旭.形式語言與自動機理論[M].2版.北京：清華大學出版社，2007：282-283.

[8] Harry R.Lewis，Christos H.Papadimitriou， Elements of the theory of Computation（Second Edition）[M].北京：清華大學出版社，1998：180-182.