当前课程知识点:软件理论基础 > 第十三章 图灵机的扩展 > 13.3 图灵机移动的扩展 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍第三节
图灵机移动的扩展
标准图灵机读头
读完之后,左、右移动
这是一种移动
状态转移
从一个状态转到另外一个状态
也是移动
这两种移动能作哪些扩展呢?
读头移动增加一个功能
对这个带
读头读 a
可以左移、可以右移
还增加一种移动:不动
停止在这里
用 S 表示
例子
q1,正在读 a
把 a 改成 b,停在这里
之后
转到状态 q2
跟 q1 的位置一样
标准图灵机没有这样的操作
增加了一种功能之后
这类图灵机跟标准图灵机的功能是不是相同的?
定理
具有停止功能的图灵机
跟标准图灵机具有相同的功能
要证明这结论
第一个结论:具有停止功能的图灵机
具有标准图灵机的功能
标准图灵机能够做到的事
停止功能的图灵机也能做
因为具有停止选择功能图灵机
只要不使用停止功能
其它的跟标准图灵机是一致的
所以结论是显然的
另外,还有结论:
具有停止功能的图灵机
能做的事,标准图灵机也能做
这就证明了标准图灵机
模拟
具有停止功能的图灵机
具有停止功能的图灵机
读一个字符
写一个字符
左移动到新的状态
这跟标准图灵机是一样的
所以标准图灵机是能做的
右移动,也是一样
差异是哪呢?
具有停止功能的图灵机
能做这样的事
在 q1 状态读 a,改成 b,停止
然后到新的状态 q2
这是停止功能图灵机具有的特点
标准图灵机没有
标准图灵机是不是能
模拟这个动作呢?
可以这样模拟
q1 把 a 改成 b
首先左移到一个新的状态
用 \overline{q2} 表示
它读任何一个符号
还是写成这个符号
不变
然后,右移到新的状态 q2
中间作了一个辅助
完成了这个动作
x 是任意一个符号
它就可以模拟
具有停止功能的图灵机
看一个实例
q1 读 a
a 改成 b,不动
到 q2 状态
在停止功能图灵机
读 a
a 改成 b,不动到 q2
标准图灵机,按刚才的做法
q1 读 a,a 改成 b
首先,左移动到 \overline{q2}
\overline{q2} 读 b
b 不变
然后,右移动到
状态 q2
开始,这是一样的
结束,这跟这也是一样的
模拟
做到要的结果
当然,中间步数可能多一些,这没关系
只要达到相同的结果就可以了
这就是模拟的实质
具有停止选择的图灵机
跟标准图灵机的功能是相同的
下面介绍另一个移动扩展
状态转移的扩展
标准图灵机
状态转移每一次移动
只能一种,或者停机
或者一个转移
对这个功能进行扩展
有限自动机有 DFA、NFA
下推自动机
有PDA、DPDA
特别,下推自动机
DPDA 跟 PDA 是不等价的
对图灵机也做扩展
非确定图灵机
也有状态、输入字母
带符号,等等
只是状态转移有多种选择
状态转移函数定义为
(状态,带符号),二维
到幂集合,(状态,带符号,左右移)
构成幂集合的映射
是一个三元组的集合
有多种选择
这跟标准图灵机不一样了
是新的一类图灵机
它跟标准图灵机是不是功能相同的?
q1 读 a
a 改成 b,左移到 q2
还在 q1 读 a,把 a 改成 c,右移到 q3
这在标准图灵机是不行的
但非确定图灵机可以
非确定图灵机作这样的转移
一次移动
开始 q1 状态读 a
下一次
得到的第一个选择是这个结果
第二个选择是这样的结果
一次就得到这样的转移
在非确定图灵机
因为有多种选择
怎么是接受和拒绝?
一个字符串
表示的初始即时描述
如果在这图灵机
经过若干次的转移,能转移到这种形式
qf 是终态
叫做最终的即时描述
有一种实现能得到这样
w 就被接受
这是非确定图灵机的接受
下面有结论
非确定图灵机能模拟标准图灵机
确定图灵机
是非确定图灵机中
一种特殊的情形
确定图灵机
也是标准图灵机,能做到的事情
非确定图灵机一定能够做到
这个结论显然
接下来,标准图灵机
也是确定图灵机
能够模拟非确定图灵机
在带中保留所有可能的计算
用一个示意图
这是非确定图灵机
每一个分支表示一种计算
比如,状态 q1 到 q2、q4,等等
是第一个计算
另外,q1、q2、q5、q6
也是一种计算
记为第二种计算
还有其它的计算
非确定图灵机
用标准图灵机模拟
保留所有的计算路径
然后,把这些计算
都存在二维的带里
看这个例子
状态 q1 读 a,写成 b,左移到 q2
同样,状态 q1 读 a,改写成 c,右移到 q3
在非确定图灵机
开始读 a
写到二维
没有作任何移动时
开始状态 q1 读 a 得到的形式
在非确定中
第一个选择,a 改成 b,左移到 q2
第二种选择,a 换成 c,右移到 q3
这是非确定
把这种情形记在二维带里
bbc 记到这个通道
对应 q2 是这个位置
这里 cbc,对应状态 q3 在这个位置
每次计算都作这样的处理
有多种选择
每一次选择都作这样的复制
就得到标准图灵机
能够模拟非确定图灵机
每一次重复这样的步骤:
每一步执行一个计算
如果当前计算有两个或者多个选择
把之前结构都复制出来
然后,把复制的状态改变
重复这样的步骤,直到完成
用标准图灵机也能够模拟非确定图灵机
得到非确定图灵机
跟标准图灵机具有相同的功能
说明
功能是相同的
但它们的计算复杂性是不一样的
确定图灵机
要模拟非确定图灵机
时间应该是指数级
在计算复杂性中
还要作进一步地介绍
这一节介绍了
图灵机的另一种扩展
读头移动的扩展
原来只有左移和右移
增加停止不动
对图灵机的状态转移的移动
状态转移可以有多个选择
也就是非确定图灵机
我们证明了所有这些扩展
跟标准图灵机
功能都是相同的
这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试