图灵机概念的教学思考

《图灵机概念的教学思考》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图灵机概念的教学思考　　摘要：众所周知，概念的定义形式是理解、推导和掌握与之相关的性质及结论的基础。在教学中，如何更好阐述概念，帮助学生分析概念之间的联系，从而更好理解和应用此概念是课堂教学的主要任务，是一种精确的通用计算机模型。通过对教科书上常见的三种不同图灵机概念进行分析，阐明了它们在计算能力上的等价性，使在教学中能帮助学生更深入理解该概念。　　关键?~：图灵机转移函数读写头等价　　中图分类号：TP301文献标识码：A文章编号：1674-098X（2016）10（b）-0162-03　　图灵机（Turingmachine，TM）是由图灵在1936

2、年提出的，它是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为[1-2]。近年来，很多学者对图灵机进行了研究，如在文献[3]中，王强证明了四元图灵机与五元图灵机的等价性；文献[4]研究了一种三状态图灵机的设计；文献[5]研究了图灵机与Petri网。进一步，文献[6]提出了量子图灵机的概念并研究了它的性质。　　众所周知，概念的定义形式是理解、推导和掌握与之相关的性质及结论的基础。在教学中，如何更好阐述概念，帮助学生分析概念之间的联系，从而更好理解和应用此概念是课堂教学的主要任务。图灵机是《计算理论导引》课程里的一个基本概念，它在可计算性理论及计

3、算复杂性理论研究中起着重要作用。近几年来，笔者在从事《计算理论导引》课程的教学中，采用了几种不同类型的教材[1-2，7-8]，发现这些教材中对图灵机概念的描述在形式上不尽相同，但教材上却没有明确指出这些不同定义形式之间的等价性。因此，深入剖析不同图灵机概念之间的关系可以帮助学生在学习过程中更好理解和掌握图灵机，同时也为图灵机的应用奠定基础。下面先给出教科书上常见的三种不同图灵机概念的描述。　　1预备知识　　定义1（[7]）图灵机M是一个七元组：　　其中：　　Q为状态的有穷集合，，q为M的一个状态；　　q0为为M的开始状态。对于一个给定的输入串，M从状

4、态q0启动，读写头注视着输入带的最左端的符号；　　F为是M的终止状态集合，为M的一个终止状态。一般地，一旦M进入终止状态，它就停止运行；　　为带符号表（tapesymbol）。为M的一个带符号，表示在M的运行过程中，X可以在某一时刻出现在输入带上。　　为称为空白符（blanksymbol），含有空白符的带方格被认为是空的；　　为为输入字母表。为M的一个输入符号。除了空白符号之外，只有中的符号才能在M启动时出现在输入带上；　　δ为为M的转移函数。　　（i）表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读写头向右移动一

5、格。　　（ii）表示M在状态q读入符号X，将状态改为p，并在这个X所在的带方格中印刷符号Y，然后将读写头向左移动一格。　　定义2（[1，2]）图灵机是一个七元组　　，其中：，都是有穷集合。　　（1）并且Q为状态集；　　（2）为输入字母表，不包括特殊空白符号；　　（3）为带字母表，其中：；　　（4）是转移函数。　　若机器处于状态q，读写头所在的带方格内包含符号，当时，机器在所在的带方格内写下b以取代，然后将读写头向右移动一格，并进入状态p。　　若机器处于状态q，读写头所在的带方格内包含符号，当时，机器在所在的带方格内写下b以取代，然后将读写头向左移动一

6、格，并进入状态p。　　为起始状态；　　为接受状态；　　为拒绝状态，且。　　定义3（[8]）图灵机是一个五元组，其中　　Q为状态的有穷集。　　为带字母表，包括空白符号和左端点符号，但不包含符号←和→。　　为起始状态；　　为停止状态集合。　　是转移函数，使得：　　对所有的，如果，则。　　对所有的且，如果，则。　　2分析　　下面对上述三种定义进行分析。　　相同点：上述三个定义都含有有穷状态集、起始状态、带字母表、停止状态集、空白符号及转移函数。　　不同点：　　（1）带字母表不同：定义3中的带字母表除了包含字母表及空白符号外，还包含左端点符号，但定义1及定义

7、2的带字母表不包含左端点符号，只包含字母表及空白符号。　　（2）停止状态集合不同：定义1的停止状态集合只包含接受状态，没有拒绝状态。定义2的停止状态集合只包含一个接受状态，一个拒绝状态。定义3的停止状态集合既包含接受状态又包含拒绝状态。　　（3）转移函数不同：定义1和定义2所定义的转移函数都是从集合到集合的一个映射，对中的任一个元素，图灵机既要在读写头所在的带方格内印刷一个字符，又要将读写头向左或向右移动一格。定义3的转移函数是从到的一个映射，对中的任一元素，图灵机或者在读写头所在的带方格内印刷一个字符，或者将读写头向左或向右移动。　　（4）左端点符

8、号不同：定义3中明确给出了左端点符号，并规定在任何状态下，如果读写头所在的带方格是左端点符号，则图灵机的读写