刘练珍++张向阳

摘 要：众所周知，概念的定义形式是理解、推导和掌握与之相关的性质及结论的基础。在教学中，如何更好阐述概念，帮助学生分析概念之间的联系，从而更好理解和应用此概念是课堂教学的主要任务，是一种精确的通用计算机模型。通过对教科书上常见的三种不同图灵机概念进行分析，阐明了它们在计算能力上的等价性，使在教学中能帮助学生更深入理解该概念。

关键詞：图灵机 转移函数 读写头 等价

中图分类号：TP301 文献标识码：A 文章编号：1674-098X（2016）10（b）-0162-03

图灵机（Turing machine， TM）是由图灵在1936年提出的，它是一种精确的通用计算机模型，能模拟实际计算机的所有计算行为[1-2]。近年来，很多学者对图灵机进行了研究，如在文献[3]中，王强证明了四元图灵机与五元图灵机的等价性；文献[4]研究了一种三状态图灵机的设计；文献[5]研究了图灵机与Petri网。进一步，文献[6]提出了量子图灵机的概念并研究了它的性质。

众所周知，概念的定义形式是理解、推导和掌握与之相关的性质及结论的基础。在教学中，如何更好阐述概念， 帮助学生分析概念之间的联系，从而更好理解和应用此概念是课堂教学的主要任务。图灵机是《计算理论导引》课程里的一个基本概念，它在可计算性理论及计算复杂性理论研究中起着重要作用。近几年来，笔者在从事《计算理论导引》课程的教学中，采用了几种不同类型的教材[1-2，7-8]，发现这些教材中对图灵机概念的描述在形式上不尽相同，但教材上却没有明确指出这些不同定义形式之间的等价性。……