电子科技大学：《有限自动机理论 Finite Automata Theory》课程教学资源（课件讲稿）第06章 图灵机（TuringM - TM）

第六章图灵机 图灵机（即TuringM-TM) 由A.Turing于1936年，在论文 《可计算数字及其在判断性问题 中的应用》里提出

第六章 图灵机 图灵机(即TuringM--TM) 由A.Turing于1936年，在论文 《可计算数字及其在判断性问题 中的应用》里提出

TM是可计算性的数学模型 可计算的特点是：有穷、离散、 机械执行、停机。 为计算机的发展奠定了理论基础。 图灵：计算机理论、人工智能之父 冯诺依曼：计算机体系结构之父

TM是可计算性的数学模型 可计算的特点是: 有穷、离散、 机械执行、停机。 为计算机的发展奠定了理论基础。 图灵:计算机理论、人工智能之父 冯诺依曼:计算机体系结构之父

图灵机可以模拟电子计算机的计 算能力。 使用图灵机可以解决计算机程序 的可计算问题 图灵机的构造技术类似于计算机 的编程技术（汇编级）

图灵机可以模拟电子计算机的计 算能力。 使用图灵机可以解决计算机程序 的可计算问题。 图灵机的构造技术类似于计算机 的编程技术（汇编级）

6.1图灵机的基本模型 6.1.1 图灵机的定义

6.1 图灵机的基本模型 6.1.1 图灵机的定义

图灵机的物理模型 1 2 3 An FSC

图灵机的物理模型 a1 a2 a3 … aj … an an+1 … FSC

个有限状态控制器FSC) 一个外部的存储设备 可以向右扩展的无限长度带 带上具有左端点，使用“上”表示 图灵机直接扫描输入带上左端点右边 的第一个符号

一个有限状态控制器(FSC) 一个外部的存储设备 可以向右扩展的无限长度带 带上具有左端点，使用“┣”表示 l 图灵机直接扫描输入带上左端点右边 的第一个符号

带分解为单元，每个单元可以为 空或存放字母表上的字母符号 带的空白单元标记为B 有限状态控制器通过一个读/写头 可以读/写带上单元内容

带分解为单元，每个单元可以为 空或存放字母表上的字母符号 带的空白单元标记为B 有限状态控制器通过一个读/写头 可以读/写带上单元内容

在某个时刻，有限状态控制器处 于某个状态，读/写头将扫描带上的 个单元 依照状态和扫描到的带上符号， 图灵机将有一个动作如下：

在某个时刻，有限状态控制器处 于某个状态，读/写头将扫描带上的 一个单元 依照状态和扫描到的带上符号， 图灵机将有一个动作如下：

有限状态控制器的状态进行改变； 把刚刚扫描过的单元上符号擦除掉 并印刷上一个新的符号（有可能印刷上 与原来符号相同的符号)； 读/写头向左或者向右移动一个单元； 或者读/写头不移动

有限状态控制器的状态进行改变； 把刚刚扫描过的单元上符号擦除掉， 并印刷上一个新的符号（有可能印刷上 与原来符号相同的符号）； 读/写头向左或者向右移动一个单元； 或者读/写头不移动

五元式描述动作 其中：x,W∈∑'（∑的增广集合） 图灵机处于状态q,扫描到符号x, 则 状态变换为q',印刷上新的符号W, 读/写头向左、或向右或不移动

五元式描述动作 其中：x，W∈∑ ′（ ∑的增广集合） 图灵机处于状态q，扫描到符号x， 则 状态变换为q′ ，印刷上新的符号W， 读/写头向左、或向右 或不移动