一種圖靈機識別語言算法的進(jìn)一步描述

石桂娟　朱平

摘 要：圖靈機是作為一種可計算性的數(shù)學(xué)模型提出的，為計算機的發(fā)展奠定了理論基礎(chǔ)。該文針對計算理論導(dǎo)引教材中一個圖靈機算法實例的描述中不夠完善的地方加以改進(jìn)，從而保證了該圖靈機描述的嚴(yán)謹(jǐn)性與可靠性。

關(guān)鍵詞：圖靈機 語言 描述 改進(jìn)

中圖分類號： TP301 文獻(xiàn)標(biāo)識碼：A 文章編號：1674-098X（2014）04（c）-0038-02

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

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

1 基本概念

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

其中，

——狀態(tài)的有窮集合，，為的一個狀態(tài)。

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

——是的終止?fàn)顟B(tài)集合。，為的一個終止?fàn)顟B(tài)。與FA和PDA不同，一般地，一旦進(jìn)入終止?fàn)顟B(tài)，它就停止運行。

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

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

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

——為的移動函數(shù)。

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

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

定義2[6] 圖靈機計算時，當(dāng)前狀態(tài)、當(dāng)前帶內(nèi)容和讀寫頭當(dāng)前位置構(gòu)成的整體叫做圖靈機的格局。

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

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

2 原問題

在學(xué)習(xí)計算理論導(dǎo)引課程中，發(fā)現(xiàn)一個有關(guān)圖靈機識別語言的算法描述存在不夠完善之處，現(xiàn)將原問題展示如下，并通過舉例說明其不完善之處。

2.1 原問題展示

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

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

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

=“對于輸入字符串：

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

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

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

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

（5）轉(zhuǎn)到第一步?！?/p>

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

2.2 不完善之處

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

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

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

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

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

3 改進(jìn)的算法描述

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

3.1 算法描述

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

=“對于輸入字符串：

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

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

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

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

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

（6）轉(zhuǎn)到第一步?！?/p>

3.2 分析討論

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

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

3.3 舉例

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

[1] 邱麗萍，朱平.關(guān)于自動機和形式語言結(jié)構(gòu)理論的研究[J].江南大學(xué)學(xué)報自然科學(xué)版，2003（5）.

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

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

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

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

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

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

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

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

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

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

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

（6）轉(zhuǎn)到第一步?！?/p>

3.2 分析討論

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

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

3.3 舉例

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

[1] 邱麗萍，朱平.關(guān)于自動機和形式語言結(jié)構(gòu)理論的研究[J].江南大學(xué)學(xué)報自然科學(xué)版，2003（5）.

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

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

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

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

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

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

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

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

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

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

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

（6）轉(zhuǎn)到第一步?！?/p>

3.2 分析討論

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

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

3.3 舉例

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

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

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

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

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

4 結(jié)語

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

參考文獻(xiàn)

[1] 邱麗萍，朱平.關(guān)于自動機和形式語言結(jié)構(gòu)理論的研究[J].江南大學(xué)學(xué)報自然科學(xué)版，2003（5）.

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

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

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

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

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

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

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

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