当前课程知识点:软件理论基础 >  第十二章 Turing机 >  12.4 图灵机的计算 >  Video

返回《软件理论基础》慕课在线视频课程列表

Video在线视频

下一节:Video

返回《软件理论基础》慕课在线视频列表

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

-习题--作业

第六章 正则语言的性质与DFA优化

-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

-习题--作业

第八章 CFG的应用与文法的二义性

-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

-习题--作业

第十章 下推自动机与CFG化简规范

-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

-习题--作业

第十二章 Turing机

-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

-习题--作业

期中考试

-期中考试

Video笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。