丘奇-图灵论题.ppt

朴秀峰
******@
计算理论
第3章 丘奇--图灵论题
*
讲解：XX
引言
什么是计算？
计算机的基本能力和局限性是什么？
*
讲解：XX
引言
计算机科学历史上关于概念的争论
什么是计算
什么是操作系统 基本上解决
什么internet ?
什么是数据库
什么是数据仓库 还在争论
什么是数据网格
解决方法， 给出大众能理解的代表
*
讲解：XX
引言
计算机科学历史上关于概念的争论
解决的办法， 给出一个代表
什么是 3的倍数 { 3N |N=1,2,3}, {x| x mod 3 =0}
代表元 ：3
什么是操作系统 代表元：Windows, Unix
什么internet 代表元：大众理解：Web ， IE
什么是计算? 多个模型；代表元：图灵机, 或 递归函数论
*
讲解：XX
引言
在还没有计算机的时候， 凭想象力把后来出现的 把计算机的理论模型建立起来了。
1936年
想得如此周到、严密
好像从高度文明的外星来的文化使者
*
讲解：XX
引言
Alan M. Turing (1912–1954)
In 1936, Turing introduced hisabstract model for computation inhis article “On Computable Numbers,”.
At the same time, Alonzo Church published similar ideas and results. 殊途同归
Turing model 成为理论计算科学的标准模型standard model
*
讲解：XX
引言
图灵机（Turing Machine，TM），是计算机的一种简单的数学模型。
历史上，冯•诺曼计算机的产生就是由图灵机诱发的。
丘奇—图灵论题：一切合理的计算模型都等同于图灵机.
*
讲解：XX
主要内容
丘奇—图灵论题
图灵机的形式化定义
图灵机的例子
图灵机的变形
多带图灵机
非确定型图灵机
枚举器
与其他模型的等价性
算法的定义
希尔伯特问题
描述图灵机的术语
*
讲解：XX
图灵机(Turning Machine)
非形式化描述
根据当前状态和字符 xi ，决定 写 移 转三动作
-写 letter, 有存储器- 左或右移动
转移状态 可以作循环语句
磁带相当于数组，可读写。这是增加的重要资源
internal state set Q
R
L
每一步，读写头在单向无穷带上左右移动并读写。
*
讲解：XX
图灵机
state q0
初始, 带子上只有输入串w*,其它地方是空的。开始状态 q0。
计算过程中读写头左右移动，机器内部状态改变，带子上内容重写。
数组结构
*
讲解：XX