论文部分内容阅读
摘 要：众所周知，概念的定义形式是理解、推导和掌握与之相关的性质及结论的基础。在教学中，如何更好阐述概念，帮助学生分析概念之间的联系，从而更好理解和应用此概念是课堂教学的主要任务，是一种精确的通用计算机模型。通过对教科书上常见的三种不同图灵机概念进行分析，阐明了它们在计算能力上的等价性，使在教学中能帮助学生更深入理解该概念。
关键詞：图灵机 转移函数 读写头 等价
中图分类号：TP301 文献标识码：A 文章编号：1674-098X（2016）10（b）-0162-03
图灵机（Turing machine， TM）是由图灵在1936年提出的，它是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为[1-2]。近年来，很多学者对图灵机进行了研究，如在文献[3]中，王强证明了四元图灵机与五元图灵机的等价性；文献[4]研究了一种三状态图灵机的设计；文献[5]研究了图灵机与Petri网。进一步，文献[6]提出了量子图灵机的概念并研究了它的性质。
众所周知，概念的定义形式是理解、推导和掌握与之相关的性质及结论的基础。在教学中，如何更好阐述概念， 帮助学生分析概念之间的联系，从而更好理解和应用此概念是课堂教学的主要任务。图灵机是《计算理论导引》课程里的一个基本概念，它在可计算性理论及计算复杂性理论研究中起着重要作用。近几年来，笔者在从事《计算理论导引》课程的教学中，采用了几种不同类型的教材[1-2，7-8]，发现这些教材中对图灵机概念的描述在形式上不尽相同，但教材上却没有明确指出这些不同定义形式之间的等价性。因此，深入剖析不同图灵机概念之间的关系可以帮助学生在学习过程中更好理解和掌握图灵机，同时也为图灵机的应用奠定基础。下面先给出教科书上常见的三种不同图灵机概念的描述。
1 预备知识
定义1（[7]）图灵机M是一个七元组：
其中：
Q为状态的有穷集合，，q为M的一个状态；
q0为为M的开始状态。对于一个给定的输入串，M从状态q0启动，读写头注视着输入带的最左端的符号；
F为是M的终止状态集合，为M的一个终止状态。一般地，一旦M进入终止状态，它就停止运行；
为带符号表（tape symbol）。为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上。
为称为空白符（blank symbol），含有空白符的带方格被认为是空的；
为为输入字母表。为M的一个输入符号。除了空白符号之外，只有中的符号才能在M启动时出现在输入带上；
δ为为M的转移函数。
（i）表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读写头向右移动一格。
（ii）表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读写头向左移动一格。
定义2（[1，2]）图灵机是一个七元组
，其中：，都是有穷集合。
（1）并且Q为状态集；
（2）为输入字母表，不包括特殊空白符号；
（3）为带字母表，其中：；
（4）是转移函数。
若机器处于状态q，读写头所在的带方格内包含符号，当时，机器在所在的带方格内写下b以取代，然后将读写头向右移动一格，并进入状态p。
若机器处于状态q，读写头所在的带方格内包含符号，当时，机器在所在的带方格内写下b以取代，然后将读写头向左移动一格，并进入状态p。
为起始状态；
为接受状态；
为拒绝状态，且。
定义3（[8]）图灵机是一个五元组，其中
Q为状态的有穷集。
为带字母表，包括空白符号和左端点符号，但不包含符号←和→。
为起始状态；
为停止状态集合。
是转移函数，使得：
对所有的，如果，则。
对所有的且，如果，则。
2 分析
下面对上述三种定义进行分析。
相同点：上述三个定义都含有有穷状态集、起始状态、带字母表、停止状态集、空白符号及转移函数。
不同点：
（1）带字母表不同：定义3中的带字母表除了包含字母表及空白符号外，还包含左端点符号，但定义1及定义2的带字母表不包含左端点符号，只包含字母表及空白符号。
（2）停止状态集合不同：定义1的停止状态集合只包含接受状态，没有拒绝状态。定义2的停止状态集合只包含一个接受状态，一个拒绝状态。定义3的停止状态集合既包含接受状态又包含拒绝状态。
（3）转移函数不同：定义1和定义2所定义的转移函数都是从集合到集合的一个映射，对中的任一个元素，图灵机既要在读写头所在的带方格内印刷一个字符，又要将读写头向左或向右移动一格。定义3的转移函数是从到的一个映射，对中的任一元素，图灵机或者在读写头所在的带方格内印刷一个字符，或者将读写头向左或向右移动。
（4）左端点符号不同：定义3中明确给出了左端点符号， 并规定在任何状态下，如果读写头所在的带方格是左端点符号，则图灵机的读写头必须向右移动一个带方格。定义1和定义2中没有给出左端点符号，但在计算时要求若图灵机读写头处于带的最左端方格，即使转移函数指示的是←，此时读写头也必须停在原地不动。
上述三种定义虽然在形式上是不同的，但是它们在能力上却是等价的，下面讨论它们的等价性。
命题1：定义1与定义2是等价的，即：若M_1和M_2是由定义1和定义2所分别定义的图灵机，则L（M_1）=L（M_2）。 证明：显然，由定义2所定义的图灵机都是定义1所定义的图灵机，即：若M是满足定义2的图灵机，那么M满足定义1。
反过来，设是由定义1定义的图灵机，则构造图灵机如下：
，，，，其中转移函数定义为，对任意的。
（1）如果，那么令；
（2）如果，那么令；
（3）如果，那么令；
（4）如果，那么令。
显然，图灵机N是定义2所定义的图灵机。综上可知，定义1与定义2是等价的。
文献[3]讨论了四元图灵机与五元图灵机的等价性问题，并给出了四元图灵机和五元图灵机的转换算法。在下文中，将文献[3]的算法应用到定义2和定义3，得到了如下结论。
3 结语
虽然在不同的教材中图灵机的概念在形式上不尽相同， 但由命题1和命题2可知，它们在能力上完全等价。形式上，三种不同定义各有侧重，即定义1和定义2侧重于描述图灵机在每一个状态下读、写及转移。定义3则侧重于图灵机不仅可以读、写，而且其读写头还可以左移、右移或保持不变。如果在教学中，适当增加图灵机等价模型的实际应用内容，不仅可以帮助学生更好理解图灵机概念，还能激起学生对学习的兴趣，培养学生自学和探索的能力。
参考文献
[1] Michael Sipser，Introduction to the theory of computation （Second Edition）[M].北京：机械工业出版社，2006：140-142.
[2] Michael Sipser，著.计算理论导引[M].唐常杰，陈鹏，向勇，刘齐宏，译.北京：机械工业出版社，2006：87-88.
[3] 王强.四元图灵机与五元图灵机的等价性[J].计算机科学，2003（31）：192-193.
[4] 丁勤.一种三状态图灵机的设计[J].淮阴师范学院学报：自然科学版，2006（5）：158-161.
[5] 宋文，牟行军.计算的模型：图灵机与Petri网[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.
关键詞：图灵机 转移函数 读写头 等价
中图分类号：TP301 文献标识码：A 文章编号：1674-098X（2016）10（b）-0162-03
图灵机（Turing machine， TM）是由图灵在1936年提出的，它是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为[1-2]。近年来，很多学者对图灵机进行了研究，如在文献[3]中，王强证明了四元图灵机与五元图灵机的等价性；文献[4]研究了一种三状态图灵机的设计；文献[5]研究了图灵机与Petri网。进一步，文献[6]提出了量子图灵机的概念并研究了它的性质。
众所周知，概念的定义形式是理解、推导和掌握与之相关的性质及结论的基础。在教学中，如何更好阐述概念， 帮助学生分析概念之间的联系，从而更好理解和应用此概念是课堂教学的主要任务。图灵机是《计算理论导引》课程里的一个基本概念，它在可计算性理论及计算复杂性理论研究中起着重要作用。近几年来，笔者在从事《计算理论导引》课程的教学中，采用了几种不同类型的教材[1-2，7-8]，发现这些教材中对图灵机概念的描述在形式上不尽相同，但教材上却没有明确指出这些不同定义形式之间的等价性。因此，深入剖析不同图灵机概念之间的关系可以帮助学生在学习过程中更好理解和掌握图灵机，同时也为图灵机的应用奠定基础。下面先给出教科书上常见的三种不同图灵机概念的描述。
1 预备知识
定义1（[7]）图灵机M是一个七元组：
其中：
Q为状态的有穷集合，，q为M的一个状态；
q0为为M的开始状态。对于一个给定的输入串，M从状态q0启动，读写头注视着输入带的最左端的符号；
F为是M的终止状态集合，为M的一个终止状态。一般地，一旦M进入终止状态，它就停止运行；
为带符号表（tape symbol）。为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上。
为称为空白符（blank symbol），含有空白符的带方格被认为是空的；
为为输入字母表。为M的一个输入符号。除了空白符号之外，只有中的符号才能在M启动时出现在输入带上；
δ为为M的转移函数。
（i）表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读写头向右移动一格。
（ii）表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读写头向左移动一格。
定义2（[1，2]）图灵机是一个七元组
，其中：，都是有穷集合。
（1）并且Q为状态集；
（2）为输入字母表，不包括特殊空白符号；
（3）为带字母表，其中：；
（4）是转移函数。
若机器处于状态q，读写头所在的带方格内包含符号，当时，机器在所在的带方格内写下b以取代，然后将读写头向右移动一格，并进入状态p。
若机器处于状态q，读写头所在的带方格内包含符号，当时，机器在所在的带方格内写下b以取代，然后将读写头向左移动一格，并进入状态p。
为起始状态；
为接受状态；
为拒绝状态，且。
定义3（[8]）图灵机是一个五元组，其中
Q为状态的有穷集。
为带字母表，包括空白符号和左端点符号，但不包含符号←和→。
为起始状态；
为停止状态集合。
是转移函数，使得：
对所有的，如果，则。
对所有的且，如果，则。
2 分析
下面对上述三种定义进行分析。
相同点：上述三个定义都含有有穷状态集、起始状态、带字母表、停止状态集、空白符号及转移函数。
不同点：
（1）带字母表不同：定义3中的带字母表除了包含字母表及空白符号外，还包含左端点符号，但定义1及定义2的带字母表不包含左端点符号，只包含字母表及空白符号。
（2）停止状态集合不同：定义1的停止状态集合只包含接受状态，没有拒绝状态。定义2的停止状态集合只包含一个接受状态，一个拒绝状态。定义3的停止状态集合既包含接受状态又包含拒绝状态。
（3）转移函数不同：定义1和定义2所定义的转移函数都是从集合到集合的一个映射，对中的任一个元素，图灵机既要在读写头所在的带方格内印刷一个字符，又要将读写头向左或向右移动一格。定义3的转移函数是从到的一个映射，对中的任一元素，图灵机或者在读写头所在的带方格内印刷一个字符，或者将读写头向左或向右移动。
（4）左端点符号不同：定义3中明确给出了左端点符号， 并规定在任何状态下，如果读写头所在的带方格是左端点符号，则图灵机的读写头必须向右移动一个带方格。定义1和定义2中没有给出左端点符号，但在计算时要求若图灵机读写头处于带的最左端方格，即使转移函数指示的是←，此时读写头也必须停在原地不动。
上述三种定义虽然在形式上是不同的，但是它们在能力上却是等价的，下面讨论它们的等价性。
命题1：定义1与定义2是等价的，即：若M_1和M_2是由定义1和定义2所分别定义的图灵机，则L（M_1）=L（M_2）。 证明：显然，由定义2所定义的图灵机都是定义1所定义的图灵机，即：若M是满足定义2的图灵机，那么M满足定义1。
反过来，设是由定义1定义的图灵机，则构造图灵机如下：
，，，，其中转移函数定义为，对任意的。
（1）如果，那么令；
（2）如果，那么令；
（3）如果，那么令；
（4）如果，那么令。
显然，图灵机N是定义2所定义的图灵机。综上可知，定义1与定义2是等价的。
文献[3]讨论了四元图灵机与五元图灵机的等价性问题，并给出了四元图灵机和五元图灵机的转换算法。在下文中，将文献[3]的算法应用到定义2和定义3，得到了如下结论。
3 结语
虽然在不同的教材中图灵机的概念在形式上不尽相同， 但由命题1和命题2可知，它们在能力上完全等价。形式上，三种不同定义各有侧重，即定义1和定义2侧重于描述图灵机在每一个状态下读、写及转移。定义3则侧重于图灵机不仅可以读、写，而且其读写头还可以左移、右移或保持不变。如果在教学中，适当增加图灵机等价模型的实际应用内容，不仅可以帮助学生更好理解图灵机概念，还能激起学生对学习的兴趣，培养学生自学和探索的能力。
参考文献
[1] Michael Sipser，Introduction to the theory of computation （Second Edition）[M].北京：机械工业出版社，2006：140-142.
[2] Michael Sipser，著.计算理论导引[M].唐常杰，陈鹏，向勇，刘齐宏，译.北京：机械工业出版社，2006：87-88.
[3] 王强.四元图灵机与五元图灵机的等价性[J].计算机科学，2003（31）：192-193.
[4] 丁勤.一种三状态图灵机的设计[J].淮阴师范学院学报：自然科学版，2006（5）：158-161.
[5] 宋文，牟行军.计算的模型：图灵机与Petri网[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.