一种图灵机识别语言算法的进一步描述

石桂娟　朱平

摘 要：图灵机是作为一种可计算性的数学模型提出的，为计算机的发展奠定了理论基础。该文针对计算理论导引教材中一个图灵机算法实例的描述中不够完善的地方加以改进，从而保证了该图灵机描述的严谨性与可靠性。

关键词：图灵机 语言 描述 改进

中图分类号： 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