当前课程知识点：软件理论基础 > 第十二章 Turing机 > 12.5 图灵机的编程技术 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍第五节
图灵机的编程技术
前面介绍了图灵机
图灵机的模型是七元组
有状态
输入字母、有带符号、状态转移
空白符、初态、终态，等等
这些基本功能
有的可以扩充
下面编程要用到的一些技术
第一，在状态增加一些参数
状态是图灵机
转移的特征
它占用系统的资源
读头受状态的控制
在状态增加参数，像 a、b、c 等等
这一个状态
可以当多个状态使用
对一般的图灵机
状态 Q 定义为：有一个状态集合 S
还有 T 作为参数
得到的笛卡尔积
a 是增加的参数
或者元素
S 是原来的状态集
原来的状态 S
增加了这些之后
状态个数
|Q| 比 |S| 多
这项技术在现在计算机应用很多
就是内存
下面在带适当做扩充
原来图灵机，一条带
分成一个个单元
两端是无限的
现在可以将这条带改成多道
读的带，不是一个符号
而是一个向量
这里给出三个通道
三个通道，一个读头
读一个向量（x,y,z）
写的也是一个向量
再左、右移动
这也看作是标准图灵机
只是现在读的不是一个符号
而是一个向量
下面是数 n，也就是0的n次方
它的复制子程序
复制n个 0，跟之前讲的
f(x)=2x
原理是类似的
用五个状态表示
q1，把第一个 0 换成 x
之后在最右边空白符写一个 0
直到所有的 0 都换成 x
右边写出了 n 个 0
之后，把原来的 x 都还原成 0
n 个 0
就复制出 n 个 0 了
复制中间用 1 作分隔线
复制干什么用呢？
看乘法
之前讲过加法
2倍、判断
但是，m 乘 n 用图灵机怎么实现？
m乘n，相当于m个n
n 写这里
2n，就是复制一个 n
3n，再复制一个 n
复制它都是相同的
这个复制作子程序
要计算 m 乘 n
就是用这个思想
这是主程序
在 m 中读一个 0
就复制一个 n
如果还有 0
再读一个 0
把 0 变成空白符
再复制一个 n
多少个m的0
就复制了多少个 n
得到m乘n
复制的程序记作copy
主程序是这样的
这里调用了这个子程序
每一次作这样的调用
最后，m 乘 n 个 0 就表示出来了
最后表示结果
就是 m 乘 n 个 0
本节介绍了图灵机的一些编程技巧
这些编程技巧，现在同学们用的很多
图灵在上个世纪30年代
已经把这些思想或者技术
已经想到了
今天介绍了新的自动机
图灵机
给出了图灵机的定义
给出了图灵机的一些功能
像识别字符串、一些计算功能
图灵机的语言
递归可枚举语言、递归语言
这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试
