一種圖靈機識別語言算法的進一步描述

石桂娟　朱平

摘 要：圖靈機是作為一種可計算性的數學模型提出的，為計算機的發展奠定了理論基礎。該文針對計算理論導引教材中一個圖靈機算法實例的描述中不夠完善的地方加以改進，從而保證了該圖靈機描述的嚴謹性與可靠性。

關鍵詞：圖靈機 語言 描述 改進

中圖分類號： TP301 文獻標識碼：A 文章編號：1674-098X（2014）04（c）-0038-02

形式語言是用數學思想和數學方法來研究自然語言和人工語言語法的理論，自動機理論則是論述計算的數學模型的定義和性質的，兩者為理論計算機科學的重要組成部分[1-2]。圖靈機是一種精確得多的通用計算機模型，它能識別更多的語言，如果像對待有窮自動機和下推自動機那樣，形式的描述一個特定圖靈機，這種細節層次的描述對于大多數圖靈機來說是繁瑣的。因而，在多數情況下，僅僅給出較高層次的描述，每個較高層次的描述實際上只是它的形式描述的一個速寫，并且較高層次的描述已經足夠精確而且容易理解。

在計算理論導引教材[3]中圖靈論題一章，圖靈機識別語言算法描述舉例一節中，筆者發現一個圖靈機識別語言算法描述（較高層次描述）實例存在不夠完善之處，經查閱原版教科書[4]確定不是翻譯問題。于是，該文針對這一不完善之處做了改進。

1 基本概念

定義1[5]圖靈機（Turing machine，TM）M是一個七元組：

其中，

——狀態的有窮集合，，為的一個狀態。

——是的開始狀態。對于一個給定的輸入串，從狀態啟動，讀頭注視著輸入帶的最左端的符號。

——是的終止狀態集合。，為的一個終止狀態。與FA和PDA不同，一般地，一旦進入終止狀態，它就停止運行。

——帶符號表（tape symbol）。，為的一個帶符號，表示在的運行過程中，可以在某一時刻出現在輸入帶上。

——稱為空白符（blank symbol）.含有空白符的帶方格被認為是空的。

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

——為的移動函數。

表示在狀態讀入符號，將狀態改為，并在這個所在的帶方格中印刷符號，然后將讀頭向右移動一格。

表示在狀態讀入符號，將狀態改為，并在這個所在的帶方格中印刷符號，然后將讀頭向左移動一格。

定義2[6] 圖靈機計算時，當前狀態、當前帶內容和讀寫頭當前位置構成的整體叫做圖靈機的格局。

定義3[7] 如果有圖靈機識別一個語言，則稱該語言是圖靈可識別的。

定義4 稱一個語言是圖靈可判定的，如果有圖靈機判定它。

2 原問題

在學習計算理論導引課程中，發現一個有關圖靈機識別語言的算法描述存在不夠完善之處，現將原問題展示如下，并通過舉例說明其不完善之處。

2.1 原問題展示

算法描述存在不完善之處的實例原文敘述如下：

現在描述TM M2，它識別的語言是所有由0組成、長度為2的方冪的字符串，即它判定語言。

對于此問題，教材中給出的較高層次的描述為：

=“對于輸入字符串：

（1）從左往右掃描整個帶子，隔一個消去一個0.

（2）如果在第一步之后，帶子上只剩下唯一的一個0，則接受。

（3）如果在第一步之后，帶子上包含不止一個0，并且0的個數是奇數，則拒絕。

（4）讓讀頭返回帶子的最左端。

（5）轉到第一步。”

該算法描述的思想是，每重復一次第一步，就消去了一半個數的0。由于在第一步中，機器掃描了整個帶子，故它能夠知道它看到的0的個數是奇數還是偶數，如果是大于1的奇數，則輸入中所含的0的個數不可能是2的方冪，此時機器就拒絕。但是，如果看到的0的個數是1，則輸入中所含的0的個數肯定是2的方冪，此時機器就接受。

2.2 不完善之處

下面舉例說明算法描述的不完善之處。

（1）對于串0，在第一步之后帶子上只剩下一個0，根據描述第二條，唯一個0是接受的。而0 是A中的句子，該算法描述對于此串沒有問題。

（2）對于串000，根據算法描述，從左往右掃描整個帶子，隔一個消去一個0，經第一步之后，帶子上剩下兩個0，剩下0的個數不止一個，并且也不是奇數個，因而會跳過第三步直接到第四步，讀頭返回帶子的最左端，轉到第一步；再從左往右掃描整個帶子，隔一個消去一個0，經第一步之后，帶子上只剩下唯一的一個0，根據描述第二條，我們最終走到了接收狀態。但是實際上，000并不是A中的句子，根據算法描述，圖靈機卻接受了000，此時，算法描述對于000這個句子的判斷是存在問題的。

（3）繼續進行判斷，不難發現，7個0組成的串、15個0組成的串……都被圖靈機M2所接受。但是，這些都不是A中的句子，這就說明這一算法描述不夠完善。

由歸納法，不難得到，根據此算法描述進行判斷，圖靈機M2識別的語言除了A之外，還有，違背了圖靈機識別語言的唯一性，該算法描述存在問題。

3 改進的算法描述

圖靈機M2識別2個語言：和A。如果找到某一機制[8]，將語言C中的串拒絕掉，那么，這個算法描述就會得到完善。

3.1 算法描述

針對這一不完善之處，在不違反原算法思想的基礎上，我們將原算法描述改進為如下形式：

=“對于輸入字符串：

（1）從左往右掃描整個帶子上的字符0，每隔一個0用字符X替換一個0。

（2）如果在第一步之后，帶子上只剩下唯一的一個0，則接受。endprint

（3）如果在第一步之后，帶子上包含不止一個0，并且最后一個非空格字符不是X，則拒絕。

（4）如果在第一步之后，帶子上包含不止一個0，且最后一個非空格字符是X，若字符0的個數為奇數個，則拒絕。

（5）讓讀頭返回至帶子的最左端。

（6）轉到第一步。”

3.2 分析討論

語言C中的串都含有奇數個0，如果增加某一機制，該機制直接拒絕接受含奇數個0的串，那么，TM M2自然會拒絕語言C。而語言A中除一個0的串是奇數個0外，其他串都是偶數個0，因而，增加的機制不會使得該圖靈機接受另外的語言。那么，對于一個0的串如何走到接收狀態呢，顯然在原算法描述中已經給出了答案，最后只有唯一一個0的狀態為接收狀態，因而，我們不用考慮語言A中一個0的串的問題。

在改進算法描述中，第一步不是將0消去，而是用叉號，即字符X來替換字符0，該做法保證了第三步和第四步的進行。第二步為接受狀態的判別條件，與原算法描述相同。第三步是增加一個新機制，目的是使M2拒絕接受含奇數個0的串，因為字符X是圖靈機可以識別的字符，因而，圖靈機可以根據最后一個非空格字符來判斷字符串是否含有奇數個0，若含有，則拒絕，反之，進行下一步。第四步則是在第三步基礎上判斷，如果最后一個非空格字符是X，那么該串含有偶數個0，則它有可能走向接受狀態，需要繼續判斷剩下的0的個數是不是奇數，是奇數則拒絕，否則繼續進行下一步。最后兩步沒有做任何修改，保證了圖靈機的可以持續不斷的運行，直至判斷出接受或拒絕為止。

3.3 舉例

下面舉三個不同的例子來檢驗改進的算法描述。

（1）對于串00000，經過第一步得到0X0X0，此時，帶子上包含不止一個0，且最后一個非空格字符不是X，拒絕。

（2）對于串000000，經過第一步得到0X0X0X，此時，帶子上包含不止一個0，且最后一個非空格字符是X，數一下剩下0的個數為奇數，拒絕。

（3）對于串0000，經過第一步之后得到0X0X，此時帶子上包含不止一個0，且最后一個非空格字符為X，剩余0的個數為偶數，因而讀頭返回至帶子最左端繼續從第一步進行，進而得到0XXX，這時帶子上只剩下唯一一個0，接受。

綜上所述，改進的算法描述具有可靠性和可操作性。

4 結語

無論是自動機還是作為計算理論模型的圖靈機，其識別的語言都是唯一的。圖靈機較高層次的算法描述是描述該圖靈機識別語言的一個形式描述的速寫，該形式描述已經足夠精確而且容易理解，算法描述不完善會對問題造成一定的困擾[9]。該文的進一步算法描述使得圖靈機的唯一性得以保證。

參考文獻

[1] 邱麗萍，朱平.關于自動機和形式語言結構理論的研究[J].江南大學學報自然科學版，2003（5）.

[2] 朱金祥，朱平.關于一類非正則語言的證明[J].江南大學學報自然科學版，2006（5）.

[3] [美] Michael Sipser.計算理論導引[M].張立昂，譯.北京：機械工業出版社，2000.

[4] [美] Michael Sipser.計算理論導論（英文版）Introduction to the Theory of Computation[M].北京： 機械工業出版社，中信出版社，2002.

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

[6] 李康，駱傳文.淺談可計算性與圖靈機[J]. 教學與管理，1989（6）：14-17.

[7] 圖靈機[J].電子計算機參考資料，1977（Z2）：47-59.

[8] 湯承林.圖靈機設計問題解法的優化[J].淮陰師范學院學報（自然科學版），2003（4）：326-329.

[9] 魯強，李效戀，王智廣.程序算法識別研究綜述[J].計算機應用，2012（10）：2863 -2868.endprint

（3）如果在第一步之后，帶子上包含不止一個0，并且最后一個非空格字符不是X，則拒絕。

（4）如果在第一步之后，帶子上包含不止一個0，且最后一個非空格字符是X，若字符0的個數為奇數個，則拒絕。

（5）讓讀頭返回至帶子的最左端。

（6）轉到第一步。”

3.2 分析討論

語言C中的串都含有奇數個0，如果增加某一機制，該機制直接拒絕接受含奇數個0的串，那么，TM M2自然會拒絕語言C。而語言A中除一個0的串是奇數個0外，其他串都是偶數個0，因而，增加的機制不會使得該圖靈機接受另外的語言。那么，對于一個0的串如何走到接收狀態呢，顯然在原算法描述中已經給出了答案，最后只有唯一一個0的狀態為接收狀態，因而，我們不用考慮語言A中一個0的串的問題。

在改進算法描述中，第一步不是將0消去，而是用叉號，即字符X來替換字符0，該做法保證了第三步和第四步的進行。第二步為接受狀態的判別條件，與原算法描述相同。第三步是增加一個新機制，目的是使M2拒絕接受含奇數個0的串，因為字符X是圖靈機可以識別的字符，因而，圖靈機可以根據最后一個非空格字符來判斷字符串是否含有奇數個0，若含有，則拒絕，反之，進行下一步。第四步則是在第三步基礎上判斷，如果最后一個非空格字符是X，那么該串含有偶數個0，則它有可能走向接受狀態，需要繼續判斷剩下的0的個數是不是奇數，是奇數則拒絕，否則繼續進行下一步。最后兩步沒有做任何修改，保證了圖靈機的可以持續不斷的運行，直至判斷出接受或拒絕為止。

3.3 舉例

下面舉三個不同的例子來檢驗改進的算法描述。

（1）對于串00000，經過第一步得到0X0X0，此時，帶子上包含不止一個0，且最后一個非空格字符不是X，拒絕。

（2）對于串000000，經過第一步得到0X0X0X，此時，帶子上包含不止一個0，且最后一個非空格字符是X，數一下剩下0的個數為奇數，拒絕。

（3）對于串0000，經過第一步之后得到0X0X，此時帶子上包含不止一個0，且最后一個非空格字符為X，剩余0的個數為偶數，因而讀頭返回至帶子最左端繼續從第一步進行，進而得到0XXX，這時帶子上只剩下唯一一個0，接受。

綜上所述，改進的算法描述具有可靠性和可操作性。

4 結語

無論是自動機還是作為計算理論模型的圖靈機，其識別的語言都是唯一的。圖靈機較高層次的算法描述是描述該圖靈機識別語言的一個形式描述的速寫，該形式描述已經足夠精確而且容易理解，算法描述不完善會對問題造成一定的困擾[9]。該文的進一步算法描述使得圖靈機的唯一性得以保證。

參考文獻

[1] 邱麗萍，朱平.關于自動機和形式語言結構理論的研究[J].江南大學學報自然科學版，2003（5）.

[2] 朱金祥，朱平.關于一類非正則語言的證明[J].江南大學學報自然科學版，2006（5）.

[3] [美] Michael Sipser.計算理論導引[M].張立昂，譯.北京：機械工業出版社，2000.

[4] [美] Michael Sipser.計算理論導論（英文版）Introduction to the Theory of Computation[M].北京： 機械工業出版社，中信出版社，2002.

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

[6] 李康，駱傳文.淺談可計算性與圖靈機[J]. 教學與管理，1989（6）：14-17.

[7] 圖靈機[J].電子計算機參考資料，1977（Z2）：47-59.

[8] 湯承林.圖靈機設計問題解法的優化[J].淮陰師范學院學報（自然科學版），2003（4）：326-329.

[9] 魯強，李效戀，王智廣.程序算法識別研究綜述[J].計算機應用，2012（10）：2863 -2868.endprint

（3）如果在第一步之后，帶子上包含不止一個0，并且最后一個非空格字符不是X，則拒絕。

（4）如果在第一步之后，帶子上包含不止一個0，且最后一個非空格字符是X，若字符0的個數為奇數個，則拒絕。

（5）讓讀頭返回至帶子的最左端。

（6）轉到第一步。”

3.2 分析討論

語言C中的串都含有奇數個0，如果增加某一機制，該機制直接拒絕接受含奇數個0的串，那么，TM M2自然會拒絕語言C。而語言A中除一個0的串是奇數個0外，其他串都是偶數個0，因而，增加的機制不會使得該圖靈機接受另外的語言。那么，對于一個0的串如何走到接收狀態呢，顯然在原算法描述中已經給出了答案，最后只有唯一一個0的狀態為接收狀態，因而，我們不用考慮語言A中一個0的串的問題。

在改進算法描述中，第一步不是將0消去，而是用叉號，即字符X來替換字符0，該做法保證了第三步和第四步的進行。第二步為接受狀態的判別條件，與原算法描述相同。第三步是增加一個新機制，目的是使M2拒絕接受含奇數個0的串，因為字符X是圖靈機可以識別的字符，因而，圖靈機可以根據最后一個非空格字符來判斷字符串是否含有奇數個0，若含有，則拒絕，反之，進行下一步。第四步則是在第三步基礎上判斷，如果最后一個非空格字符是X，那么該串含有偶數個0，則它有可能走向接受狀態，需要繼續判斷剩下的0的個數是不是奇數，是奇數則拒絕，否則繼續進行下一步。最后兩步沒有做任何修改，保證了圖靈機的可以持續不斷的運行，直至判斷出接受或拒絕為止。

3.3 舉例

下面舉三個不同的例子來檢驗改進的算法描述。

（1）對于串00000，經過第一步得到0X0X0，此時，帶子上包含不止一個0，且最后一個非空格字符不是X，拒絕。

（2）對于串000000，經過第一步得到0X0X0X，此時，帶子上包含不止一個0，且最后一個非空格字符是X，數一下剩下0的個數為奇數，拒絕。

（3）對于串0000，經過第一步之后得到0X0X，此時帶子上包含不止一個0，且最后一個非空格字符為X，剩余0的個數為偶數，因而讀頭返回至帶子最左端繼續從第一步進行，進而得到0XXX，這時帶子上只剩下唯一一個0，接受。

綜上所述，改進的算法描述具有可靠性和可操作性。

4 結語

無論是自動機還是作為計算理論模型的圖靈機，其識別的語言都是唯一的。圖靈機較高層次的算法描述是描述該圖靈機識別語言的一個形式描述的速寫，該形式描述已經足夠精確而且容易理解，算法描述不完善會對問題造成一定的困擾[9]。該文的進一步算法描述使得圖靈機的唯一性得以保證。

參考文獻

[1] 邱麗萍，朱平.關于自動機和形式語言結構理論的研究[J].江南大學學報自然科學版，2003（5）.

[2] 朱金祥，朱平.關于一類非正則語言的證明[J].江南大學學報自然科學版，2006（5）.

[3] [美] Michael Sipser.計算理論導引[M].張立昂，譯.北京：機械工業出版社，2000.

[4] [美] Michael Sipser.計算理論導論（英文版）Introduction to the Theory of Computation[M].北京： 機械工業出版社，中信出版社，2002.

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

[6] 李康，駱傳文.淺談可計算性與圖靈機[J]. 教學與管理，1989（6）：14-17.

[7] 圖靈機[J].電子計算機參考資料，1977（Z2）：47-59.

[8] 湯承林.圖靈機設計問題解法的優化[J].淮陰師范學院學報（自然科學版），2003（4）：326-329.

[9] 魯強，李效戀，王智廣.程序算法識別研究綜述[J].計算機應用，2012（10）：2863 -2868.endprint