当前位置:首页 >> 理学 >>

1 图灵机模型


计算机导论

计算机导论
第二讲 图灵机模型
2008-10-12

本讲内容 参考祈亨 年教材第 一章内容

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

图灵机模型概论
图灵机模型理论是计算学科最核心的理论 之一 图灵机模型为计算机设计指明了方向 图灵机模型是算法分析和程序语言设计的 基础理论.

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

本章主要内容
图灵机缘起 图灵机描述 计算"X+1"的图灵机 通用图灵机 图灵机模型的启示

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

图灵机缘起
1900,德国数学家希尔伯特提出"23个数学难题"中,
– 逻辑的完备性问题,即是否所有数学问题原则上都可解.

1936, 英国数学家图灵
– "论可计算数及其在判定问题中的应用"(On Computable Numbers With an Application to the Entscheidungs Problem)

结论:
– 可解的问题是能够用"图灵机"的自动机理论模型表达的 问题.

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

图灵机的直观描述
3个部件:有穷控制器(有限状态机),无穷带 (符号集合)和读写头(读,改写,左移,右移)

3个动作:改写当前格,左移或右移一格 图灵机的计算:由控制器控制执行的一系列动作
11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

图灵机的形式化描述
图灵机是一个五元组(K,∑,δ,s,H), 其中:
– K 是有穷个状态的集合; – ∑ 是字母表,即符号的集合; – s ∈K是初始状态; – H K 是停机状态的集合,当控制器内部状态为 停机状态时图灵机结束计算; – δ是转移函数,即控制器的规则集合.

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

图灵机工作过程:计算"x+1"的图灵机
目标
– 利用二进制来设计一个专门计算"x+1"的图灵机,要求计算完成 时,读写头要回归原位 – x由0,1串组成,"*"为x的分隔符,界定符

状态集合K
{start,add,carry,noncarry,overflow,return,halt}

字母表∑
{0,1,*}

初始状态s
start;

停机状态集合H
{halt};

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

"x+1"图灵机规则集合(1)
规则
如果 A 那么 B,形式化表示:A→ B

图灵机控制器的规则:
(控制器当前状态,读写头当前位置的符号)→ (读 写头移动动作指示,读写头新位置的符号,控制器新 状态)

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

x+1"图灵机规则集合(2)
规则集合δ:

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

举例:"5+1"的计算过程(1)
初始状态

根据规则 集合δ:

第一步完成后状态

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

"5+1"的计算过程(2)

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

"5+1"的计算过程(3)

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

"5+1"的计算过程(4)

停机状态

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

课后思考
计算7+1的图灵机运算过程

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

通用图灵机
图灵机本质在进行字符串的处理
图灵机输入是一个字符串 图灵机输出也是一个字符串

如果将图灵机的有限内部状态与读写头的 有限动作用字符串表示 那么每条转换规则也可以用一个字符串表 示(当前状态,当前符号,动作,新状态) 图灵机可以由一个较长字符串完全表示
通用图灵机
11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

通用图灵机实现"5+1"计算(1)
编码方案

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

通用图灵机实现"5+1"计算(2)
3带通用图灵机M
图灵机输入字符串:0010 0001 0000 0001 0010(对应*100*)
图灵机的所有规则,每个规则16位字符 (当前状态,当前符号,动作,新状态) 初始状态编码:0101(对应start状态)

利用编码描述的规则:

0101 0010
11:07

0010

0011

0110

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

通用图灵机实现计算的过程
扫描第三条带获 得当前状态S

开始

计算机导论

发现什么?
计算过程与具体的编 码和规则都不相关!
(Si,Ci,A,Sn)即转换规则 (当前状态,当前符号,动 作,新状态)

扫描第一条带获 得当前符号C

意味着什么?
程序可以重复执行

扫描第二条带查找规则串 (Si,Ci,A,Sn) 根据A对第一条带 执行相应动作

否 Si == S Ci == C

S = Sn

是 Si == 结束 状态? 是



11:07

END 信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

思考
利用X+1图灵机模型计算
– X-1
X+(-1), -1用补码表示

– X+2
X+1+1

如果有x+y的描述规则? 如果有x*y的描述规则? …… 那么

– X*2
X+X=X+1+1……

– X/2
X-2-2……

– ……
11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

通用图灵机蕴含的计算思想(1)
程序也是数据
– "x+1"图灵机功能是固定的,相当于一个程序 – 通用的图灵机功能根据输入编码的不同而变化

存储程序和程序控制 M图灵机进一步展示了程序和其输入可以先 保存到存储带上,M就按程序一步一步运行 直到给出结果,结果也保存在存储带上.

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

通用图灵机蕴含的计算思想(2)
通用图灵机模型是计算机的计算能力的极限
因为,根据丘奇-图灵论题: 不能用图灵机完成的计算任务是不可计算的

计算机系统应该有:
– 存储器(相当于存储带) – 中央处理器(控制器及其状态),并且其字母表可以 仅有0和1两个符号; – 为了能将数据保存到存储器并将计算结果从存储器送 出来展示给用户,计算机系统还应该有输入设备和输 出设备如键盘,鼠标,显示器和打印机等.
11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

通用图灵机蕴含的计算思想(3)
通用图灵机的所有规则构成指令集 指示指示了操作的对象(当前符号) 指令指示了待实施的操作

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

冯诺依曼机对图灵机的实现

1944年,冯诺依曼参与ENIAC研究小 组 1945年,在ENIAC基础上,冯诺依曼 提出了EDVAC(Electronic Discrete Variable AutomaticCompUter)设计方 案, 计算机的组成包括:运算器,逻辑 控制装置,存储器,输入和输出设备
11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

新的概念的提出
随机读写(Random Access)
随机读写存储器RAM(Random Access Memory)

地址(Address) 指令(Instruction) = 操作码(Operating Code, Opcode) + 操作数(Operand) 计算机指令系统 精简指令集计算机 复杂指令集计算机
11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

课后作业(1)
阅读《大学计算机基础》1.1; 1.2; 1.3; 预习《大学计算机基础》第2章全部内容 根据个人基础与下周实验课学习内容,选 择预习《大学计算机基础》第5,6,7,8, 9章相应小节内容 准备一个笔记本,上课做笔记,下课做阅 读与预习笔记

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

课后作业(2)
阅读《计算机文化》第0章的Section A, Section B,第1章Section A,第3章 Section A,Section B, Section C, Section D 全部内容 根据个人基础与下周实验课学习内容,选 择阅读《计算机文化》第11章(计算机程 序)Section A,Section B,Section C内容

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

课后作业(3)
计算7+1的图灵机运算过程

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

关于后续课程时间安排
下周一下午实验课7,8,9,10(以后三周 也如此,第十周以后视其他课室是否空闲 情况而定) 下周二到教4-205上理论课(以后每周均如 此)

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn

计算机导论

11:07

信息学院 教育技术系 曾玲 ling-zeng@scau.edu.cn


相关文章:
1 图灵机模型.ppt
1 图灵机模型_理学_高等教育_教育专区。图灵机模型理论是计算学科最核心的理论之一图灵机模型为计算机设计指明了方向图灵机模型是算法分析和程序语言设计的基础理论计...
图灵和图灵机模型.ppt
图灵可计算性 任过程是能行的(理论上的能行,能够具体表现在个 算法中),当且仅当它能够被图灵机实现 4 2.2 图灵机计算模型 5 图灵机的特征 ? ...
实验1 图灵机模型与计算机硬件系统虚拟拆装 实验报告.doc
实验1 图灵机模型与计算机硬件系统虚拟拆装 实验报告_电脑基础知识_IT/计算机_专业资料。实验 1 图灵机模型与计算机硬件系统虚拟拆装 实验报告学号 1500202151 姓名 ...
图灵机模型.ppt
图灵机全介绍,值得读的文档图灵机全介绍,值得读的文档隐藏>> 图灵机模型 ? ? ? 图灵机(Turing machine)是由图灵(Alan Mathisom Turing)在1936年提出的,它...
图灵机模型.ppt
图灵机模型 - 第1图灵机模型 图灵机模型理论是计算学科最核心的理 论之 图灵机模型为计算机设计指明了方向 图灵机模型是算法分析和程序语言设计 的基础理论...
实验一图灵机模型与计算机系统虚拟拆装实验报告.doc
实验一图灵机模型与计算机系统虚拟拆装实验报告_电脑基础知识_IT/计算机_专业资料。五、实验报告 实验名称:图灵机模型与计算机硬件系统虚拟拆装 学号 姓名 班级: 实验...
北理大学计算机实验基础 实验一_图灵机模型与计算机硬....doc
北理大学计算机实验基础 实验_图灵机模型与计算机硬件系统虚拟拆装-实验报告_互联网_IT/计算机_专业资料。实验 图灵机模型与计算机硬件系统虚拟拆装五、实验报告 ...
北航 计算理论 第二章 计算模型_图文.ppt
北航 计算理论 第二章 计算模型 - 计算理论 第二章 计算模型 主要内容 ? ? ? ? 图灵机模型 RAM机 RASP机 Lambda演算模型 2.1 图灵机模型 ? 图灵机组成...
算法与图灵机模型.ppt
算法与图灵机模型_计算机软件及应用_IT/计算机_专业资料。软件设计方法学第二章 程序算法与图灵机模型 01:00 2.1 算法概念 ? 定义:算法是完成个任务所需要的...
计算机的过去现在与未来-02、图灵和图灵机模型.ppt
计算机的过去现在与未来-02、图灵和图灵机模型 - 第2课 图灵和图灵机模型 罗东俊 ZSUJONE@126.COM 主要内容 2.1 计算本质的认识历史 2.2 图灵机计算模型 2...
计算理论第4章 图灵机.ppt
计算理论第4章 图灵机 - 第4章 图灵机 许桂靖 杨莹 1 Overview ? 图灵机(Turing Machine,TM),是 计算机的种简单的数学模型图灵机诱发的。 ?...
图灵机_含小虫类比.pdf
() 图灵与图灵机图灵机是计算机的理论模型,这个名字来源于它的发明人,阿兰图
教材习题及答案.doc
模型建立的前提下,利用计算机求解问题的核心工作就( 算法 3. 算法是组规则...答:输入信息,输出信息、程序、内部状态 (1.1) 5.简述图灵机的工作过程。 答...
图灵机.ppt
图灵机 - 第4章 图灵机 1 Overview ? 图灵机(Turing Machine,TM),是 计算机的种简单的数学模型图灵机诱发的。 ? 历史上,冯?诺曼计算机的产生就...
图灵机模型.ppt
图灵机模型_计算机硬件及网络_IT/计算机_专业资料。图灵机模型 图灵机模型概论 ? ? ? 图灵机模型理论是计算学科最核心的理论之 图灵机模型为计算机设计指明了方...
图灵机.ppt
图灵机 - 第4章 图灵机 1 Overview 图灵机(Turing Machine,TM),是 计算机的种简单的数学模型。 历史上,冯诺曼计算机的产生就是由 图灵机诱发的。 丘奇...
第2章 程序算法与图灵机模型.ppt
第2章 程序算法与图灵机模型_计算机软件及应用_IT/计算机_专业资料。第2章 程序算法与图灵机模型 2.1 算法 ? 什么是算法? 指完成个任务所需要的具体步骤和...
1.图灵机与计算问题(1节课).pdf
1.图灵机与计算问题(1节课) - 图灵机的今生来世 目录 ? ? ? ? 1、问题的起源 2、图灵的贡献 3、图灵机 4、图灵机的计算极限与计算复杂性 目录 ? ? ?...
图灵机的思想与模型简介.ppt
图灵机的思想与模型简介 - 冯.诺依曼计算机:机器级程序及其执行 2.2.1 图灵机的思想与模型简介 图灵机的思想与模型简介 ---图灵的贡献 ---图灵机:计算机...
图灵机.pdf
究竟什么是计算?什么是图灵机?计算与人 类智能是怎样的关系? () 图灵与图灵机图灵机是计算机的理论模型,这个名字来源于它的发明人,阿兰图灵(Alan Turing) . ...
更多相关标签: