当前课程知识点：软件理论基础 > 第十三章 图灵机的扩展 > 13.1 Turing理论 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
我是清华大学教师罗贵明
今天介绍的内容是图灵机的扩展
内容包括：Turing 理论
图灵机带的扩展
图灵机移动的扩展
受限图灵机
最后，介绍图灵机与其它自动机的关系
首先介绍Turing理论
上一讲介绍了图灵机
图灵机是一个七元组
具有识别串的功能
计算函数的功能
图灵机有有限自动机、下推自动机等功能
图灵机还能够做什么呢？
上个世纪30年代
Turing 提出
能够机械计算的就一定能用图灵机实现
这成为计算机科学的理论研究
Turing 这个观点是不是正确的？
能机械计算的
是不是一定能由图灵机实现？
到目前为止还没有找到
比图灵机更强大的计算机模型
算法的定义
函数 f 是能计算的
定义为计算这个函数 f 的一个图灵机
算法就是一个图灵机
存在一个算法
意味着存在一个实现这个算法的图灵机
如果图灵机 M1 与图灵机 M2
它们的语言相同
这两个图灵机是等价的
两类图灵机，它们功能相同是指
两类图灵机接受的语言
集合是相同的
第一类任意一个图灵机
在第二类
一定能找到另外一个图灵机
它们的语言相同
反之亦然
回顾一下
标准图灵机有一条带
两端无限
有一个读头
读、写之后，左移或右移
它受一个有限状态机控制
这有限状态机是确定的
这是标准图灵机
之前介绍的有限自动机
有DFA、还有NFA
介绍的下推自动机，有非确定的
有确定的，等等
标准图灵机是不是功能最强大？
带是一条的
如果有多条带会怎样呢？
如果是受限的，它又怎样呢？
这带是一维的
如果改成多维的会怎样呢？
再看读头移动
左移动或右移动
这个移动再增加其它移动会怎样呢？
如果在确定的
扩展到非确定
图灵机又会怎样呢？
对标准图灵机
功能进行一些扩展
扩展得到的每一类图灵机与标准图灵机
要证明，功能相同
或语言相同
现在采用新的证明方法
模拟的方法
模拟的方法，是用另外的一类的
图灵机
模拟第一类的图灵机
反过来也成立
模拟方法
原来图灵机记为M1
在第二类
有一个图灵机 M2
M2 模拟图灵机 M1
M1 能做的事情 M2 也能做
用图灵机的结构模拟
图灵机的结构用即时描述表示
原来的图灵机实现
从这个即时描述转移
到这个即时描述，...，等等
一直 dn 即时描述
这是原来图灵机能做到的
另一类的图灵机模拟它的动作
模拟这些即时描述的动作
模拟 d0 的动作
记为 d0'
这个即时描述
与这个即时描述
除了一些字母不一样
其它都是一样的
d1' 模拟 d1
dn' 模拟 dn
d0 一步经过转移到 d1
模拟时，从d0' 到 d1' 可能不止一步
这里用了一个转移闭包，是若干步
第二类图灵机
能够转移到 d1' 就可以了
其它的移动也是这样
用若干步
只要能转移到这里
就是成功的
特别，这个模拟是互相模拟的
df 是最终的即时描述
df' 模拟这个图灵机
最终的即时描述
它们之间也是可以互相模拟的
说明模拟这个图灵机
与原来的图灵机
接受相同的语言
这一节介绍了标准图灵机
一些功能可以作扩展
还介绍了怎么样对扩展的功能
进行证明
也就是模拟方法
下一节要逐步介绍
标准图灵机的功能作扩展之后
得到每一类的图灵机
这节介绍完毕，谢谢大家！
-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
-习题--作业
-期中考试
