当前课程知识点：软件理论基础 > 第十三章 图灵机的扩展 > 13.2 图灵机带的扩展 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍第二节
图灵机带的扩展
标准图灵机有一条带
可以两端无限延长
标准图灵机
也可以用多道图灵机表示
这是两个通道的图灵机
把(b,d)两个字符
看作一个符号
就是一个向量
状态 q1 读（b,a）
把（b,a）要换成（c,d）
左移到状态 q2
实现这个操作之后
(b,a) 变为 (c,d)，左移到状态 q2
这是多道图灵机
是标准图灵机中的一种
双带图灵机，有两条带
第一条带，两端无限
第二条带两端也是无限的
都有输入串
读头
这个控制单元
它在读带1
它在读带2
不同的是
读、写、移动，是独立的
开始时，一个读头
在第一条带最左端
其它的读头
在带的任何位置
每一步移动
都是读一个符号、写一个符号
然后独立的左、右移动
这就是多带图灵机
跟标准图灵机不一样
多带图灵机，看看它的实现
在 q1 状态，带1 正在读 b
带2 正在读 f
也就是，在状态 q1 读 b 和 f
b 换成 g
f 写成 d
第一条带左移
第二条带右移
完成这些动作之后
转移到新的状态 q2
这样的操作
得到多带图灵机的移动
结论
多带图灵机可以模拟标准图灵机
这个事实显然
仅用一条带就可以
得到标准图灵机
所有的结论
标准图灵机
也能模拟多带图灵机
采用多通道的标准图灵机
每一条带用两个通道模拟
k 条带用 2k 个通道
图灵机模拟
例子
这是两条带
第一条带，读的是 b
第二条带，读的是 g
用四个通道的图灵机
模拟这两条带的图灵机
第一个通道表示
第一条带读头的位置
1 表示读头在这个位置
第二个通道表示
第一条带的字符串
abc
读头正在读 b
b 上面标 1
第二条带
这个通道表示这个读头的位置
这个通道表示这个带的字符
这就是四个通道的标准图灵机
读头每次读的是
一个四维的向量
读一个向量，写一个向量
再左移，或者右移
两条带独自完成的内容
在这里可以实现
当然，实现可能有很多步
像在多带图灵机
读 b、读 g，换成另外字符
独立移动，只需要一步操作
而要进行这样的操作
可能要很多步了
不管有多少步
只要它能够做到就可以
这就是模拟的效果
得到结论
多带图灵机与标准图灵机
这两类图灵机
它们的功能是相同的
你能做的。我也能做
但并不意味着它们的速度是一样
看语言
{a的n次方b的n次方}
上次课用图灵机
作这语言的实现
是用 a 和 b 进行匹配
匹配的步数是多少呢？
是 O(n的平方)
这是标准图灵机
而用两条带的图灵机，只需要用 O(n) 步
怎么实现?
这个语言在标准图灵机
来回匹配，是 O(n的平方) 步
在两条带的图灵机
只需做这些操作
把第一条带 b 的n次方
复制到第二条带
只需要 n 步
把 a 的n次方
留在第一条带，也只需要 n 步
然后，比较第一条带和第二条带
也只需要 n 步
最后复杂度是 O(n)
比 n 的平方复杂度
小一个量级
说明速度，多带图灵机要快些
可以用一个双带图灵机
接受语言
{0的n次方 1的n次方 2的n次方}
标准图灵机
曾经设计过接受这个语言
用两条带怎样去设计？
留给大家做一个课后的练习
再介绍图灵机
带的另外一种扩展：多维图灵机
标准图灵机，带是一维的
这带扩展到面上
就是二维，会怎么样呢？
这里每个单元
存储一些符号
读头读 b
跟之前标准图灵机不一样
它的位置用坐标描述
这横坐标是 2
纵坐标是 -1
这种存储的方式，现在用的很多
二维的存储盘
这样的扩展
跟标准图灵机不一样
标准图灵机带只有一维，左、右移动
现在读头移动，有左移、右移
U 上移
D 下移
四种移动方式
多维图灵机
跟标准图灵机比较
第一个结论：多维图灵机
可以模拟标准图灵机
这模拟很简单
只用多维图灵机中
一个维度就可以
另一结论是：
标准图灵机也可以模拟多维图灵机
标准图灵机
使用两个通道就可以
把符号存在通道 1
符号的坐标存在通道 2
这是二维的图灵机
a 对应的横坐标是 1
纵坐标也是 1
横坐标是 1
中间用一个“#”分隔
纵坐标是 1
再用一个“#”分隔
再看 b
b 横坐标是 2
纵坐标是 -1
横坐标是2，用“#”分界
纵坐标是 -1
用“#”分界
c 等等，这些符号
都用这种形式表示
标准图灵机模拟多维图灵机
重复下面这些操作：
第一个通道写输入符号
然后计算这符号的坐标
把这坐标放在第二个通道里
状态转移到新的位置
标准图灵机在每一步
作这些动作
得到多维图灵机
跟标准图灵机的功能是相同的
这节介绍了
标准图灵机带的扩展
把一条带扩展到多条带
得到它跟标准图灵机是等价的
另外，把带的一维扩展到多维
得到的多维图灵机跟标准图灵机
也是等价的
这节内容介绍完毕
谢谢大家
-1.1 概要
--第一节
-1.2 数学基础
--Video
-1.3 图
--Video
-1.4 证明方法
--Video
-1.5 语言基础
--Video
-1.6 语言运算
--Video
-习题--作业
-2.1 确定有限自动机的概念
--Video
-2.2 确定有限自动机的定义
--Video
-2.3 扩展转移函数
--Video
-2.4 正则语言
--Video
-2.5 DFA构造
--Video
-习题--作业
-3.1 非确定有限自动机的概念
--Video
-3.2 e转移
--Video
-3.3 非确定有限自动机的定义
--Video
-3.4 扩展转移函数
--Video
-3.5 等价性证明
--Video
-3.6 文本搜索
--Video
-习题--作业
-4.1 单一终结状态的NFA
--Video
-4.2 正则语言的运算性质
--Video
-4.3 正则表示和语言
--Video
-4.4 正则表示和正则语言
--Video
-4.5 正则语言的同态
--Video
-4.6 正则表示的代数定律
--Video
-习题--作业
-5.1 文法
--Video
-5.2 线性文法
--Video
-5.3 正则文法与正则语言
--Video
-5.4 自动机的积
--Video
-习题--作业
-6.1 基本问题
--Video
-6.2 泵引理
--Video
-6.3 非正则语言的判定 1
--Video
-6.4 非正则语言的判定 2
--Video
-6.5 DFA的优化 1
--Video
-6.6 DFA的优化 2
--Video
-习题--作业
-7.1 上下文无关文法
--Video
-7.2 规约和推导
--Video
-7.3 语法分析树
--Video
-7.4 规约、推导和语法分析树之间的关系
--Video
-7.5 上下文无关语言
--Video
-习题--作业
-8.1 CFG的应用
--Video
-8.2 CFG的转化
--Video
-8.3 文法二义性
--Video
-8.4 二义性的消除方法
--Video
-8.5 CFG的构造方法
--Video
-8.6 CFG的构造实例
--Video
-第八章 CFG的应用与文法的二义性--习题
-9.1 PDA介绍
--Video
-9.2 PDA的定义
--Video
-9.3 PDA的即时描述
--Video
-9.4 PDA的语言
--Video
-9.5 PDA与CFG的关系
--Video
-习题--作业
-10.1 确定下推自动机
--Video
-10.2 DPDA与其他语言的关系
--Video
-10.3 终态型DPDA和空栈型DPDA
--Video
-10.4 消除无用符号
--Video
-10.5 消除e产生式
--Video
-10.6 消除单一产生式
--Video
-10.7 CFG的化简与Chomsky范式
--Video
-习题--作业
-11.1 CFL的必要条件
--Video
-11.2 CFL的Pumping引理
--Video
-11.3 CFL的闭运算性质
--Video
-11.4 CFL的同态性质
--Video
-11.5 CFL的交运算
--Video
-11.6 CFL的判定性质
--Video
-习题--作业
-12.1 图灵机的介绍
--Video
-12.2 图灵机的定义
--Video
-12.3 图灵机的即时描述
--Video
-12.4 图灵机的计算
--Video
-12.5 图灵机的编程技术
--Video
-习题--作业
-13.1 Turing理论
--Video
-13.2 图灵机带的扩展
--Video
-13.3 图灵机移动的扩展
--Video
-13.4 受限图灵机
--Video
-13.5 图灵机与其他自动机
--Video
-习题--作业
-14.1 图灵机编码
--Video
-14.2 对角线语言与通用语言
--Video
-14.3 图灵机语言的性质
--Video
-14.4 判定问题和语言
--Video
-14.5 计算复杂性问题
--Video
-第十四章 不可判定问题--习题
-15.1 时间自动机
--Video
-15.2 Buchi自动机
--Video
-15.3 软件形式化验证
--Video
-15.4 模型检测方法
--Video
-15.5 M3C模型检测系统
--Video
-习题--作业
-期中考试
