当前课程知识点:软件理论基础 > 第十二章 Turing机 > 12.4 图灵机的计算 > Video
欢迎同学们来到《软件理论基础》MOOC课堂
现在介绍第四节:图灵机的计算
前面介绍了图灵机
也介绍过有限自动机
DFA、NFA
还介绍了下推自动机
都有相同的一个功能
识别字符串
图灵机不单单识别字符串
还有其他一些功能
下面要讲
图灵机有计算功能
首先,介绍数的表示
整数5,在十进制里可以表示成5
二进制表示101
在单位制里可以表示成00000
为了讲图灵机的机制
采用这种数的表示
单位制表示
易于图灵机的实现
一个函数可计算
如果存在一个图灵机
对任何一个字符串
满足:开始这样的结构
q0 是初始状态
读这个字符串
经过这个图灵机
最终能够达到这结构,这是终态
是另外的一个结构
对任何w字符串,如果都有这种形式
则 f 是可计算的
对这表示
跟即时描述类似
所以,可计算也可用这种表示
其中,这是初始的即时描述
这是最终即时描述
看一个例子
二元函数: x+y
“+”是普通的加
这个函数是可计算的
其中 x、y 是整数
根据定义,是不是能计算?
必须对应一个图灵机
若 f 对应图灵机 M
输入是 x、y
x 个 0 和 y 个 0
用 1 作分界线
把这两个字符串分开
这是输入
图灵机计算
希望最后输出的结果是 x+y
xy 个 0
这个表示作输出
如果能够构造出这样的图灵机
这个函数是可计算的
这个图灵机怎样构造?
开始是这种形式
这是 x,这是 y
中间有分割线 1
结束时
应该得到 xy 个 0
而 1 放在最后
1 留在这里
主要用于其它的计算
如果能够得到这种形式
这个函数就是可计算的
实现刚才功能的图灵机
用五个状态就可以
读到 0,不变
读到1,1 改成 0
移到最右边
把最右边的 0 改成 1
图灵机是这样实现的
说明函数 x+y 是可计算的
再看一个例子
函数:2x 是可计算的
其中 x 为整数
是不是存在图灵机
输入是 x
当然,还是单位制
输出是 xx?
如果存在这样的图灵机
这个函数是可计算的
开始是 x
最后得到的是 2x
这样表示
怎样实现这个功能呢?
x 个 0,变成2x 个 0
要实现这个图灵机
首先,把 x 个 0 用一种特殊的符号表示
就用$
表示 x 个 0 中每一个 0
然后,找到最右边的一个$
把它替换成 0
到带的最右边
插入一个 0
如此反复,所有的$全部都换成 0
最后结果应该是 2x 个 0
实现这个图灵机
4个状态就可以
首先,q0 实现 0 换成 $ 的功能
q1,把一个$换成一个0
q2 把一个空白符换成一个 0
这操作
假如是 00
图灵机可以得到 0000
这说明,刚才的
2x 函数是可计算的
再看一个例子
这是一个二元函数
x、y 是整数
x 大于 y 时,等于 1
x 小于或等于 y 时,等于 0
这比刚才两个数加或者2倍
要复杂些
这个函数也是可计算的
它对应的图灵机输入是 x 和 y
中间用的 1 作分隔线
输出要么是 1,要么是 0
怎样设计这个图灵机?
实现这个功能
用 x 中的0 与 y 中的 0 匹配
直到匹配完之后
x 如果还有剩余的 0
擦去带中的符号
写 1
表示 x 大于 y
除此以外
擦去其它符号,写 0
这就表示 x 小于或等于 y
大家按前面的设计方法
给出它的状态转移图或者状态转移函数
容易实现
这节内容介绍了图灵机
它除了识别字符串以外
还有计算功能
这是图灵机最重要的功能
以后还要介绍图灵机的
其它的一些功能
这节内容介绍完毕
谢谢大家
-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
-习题--作业
-期中考试