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

一种图灵机识别语言算法的进一步描述 　　摘 要：图灵机是作为一种可计算性的数学模型提出的，为计算机的发展奠定了理论基础。该文针对计算理论导引教材中一个图灵机算法实例的描述中不够完善的地方加以改进，从而保证了该图灵机描述的严谨性与可靠性。 　　关键词：图灵机 语言 描述 改进 　　中图分类号： 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中的句子