图灵和图灵机模型.ppt

第2课 图灵和图灵机模型
#!app=2&via=&pos=1366384958
1
主要内容
计算本质的认识历史
图灵机计算模型
图灵简介
2
计算本质的认识历史
在20世纪30年代以前，人们并没有真正认识计算的本质
很早以前，我国的学者认为，对于一个数学问题，只有当确定了其可用算盘解算它的规则时，这个问题才算可解。这就是古代中国的“算法化”思想。
蕴涵了计算的根本问题，即“能行性”问题
这对现代计算学科的研究具有重要的意义：
图灵机
几何定理的机器证明
对计算本质的真正认识取决于形式化研究的进程
3
图灵对计算本质的揭示
在哥德尔研究成果的影响下，20世纪30年代后期，图灵从计算一个数的一般过程入手对计算的本质进行了研究，从而实现了对计算本质的真正认识
所谓计算，就是计算者（人或机器）对一条两端可无限延长的纸带上的一串0和1执行指令，一步一步地改变纸带上的0或1，经过有限步骤，最后得到一个满足预先规定的符号串的变换过程
图灵的研究成果是：可计算性 = 图灵可计算性
任一过程是能行的（理论上的能行，能够具体表现在一个算法中），当且仅当它能够被一台图灵机实现
5
图灵机计算模型
6
图灵机的特征
图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成
写在带子上的符号为一个有穷字母表：{S0，S1，S2，Sp}
一个给定机器的程序认为是机器内的五元组（qiSjSkRql 或qiSjSkLql或qiSjSkNql ）形式的指令集
qi表示机器目前所处的状态
Sj表示机器从方格中读入的符号
Sk表示机器用来代替Sj写入方格中的符号
R、L、N分别表示向右移一格、向左移一格、不移动
ql表示下一步机器的状态
7
图灵机的工作原理
机器从给定带子上的某起始点出发，根据其初始状态及机内五元组决定其动作，经过有限步骤机器停止时，带子上的信息即为机器计算的结果。
可能产生的问题：
无休止工作
如：q1S2S2Rq3指令和q3S3S3Lq1指令同时出现在机器中时
产生二义性
如：q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中时
8
实例
设b表示空格，q1表示机器的初始状态，q4表示机器的结束状态，如果带子上的输入信息是10100010，读入头对准最右边第一个为0的方格，状态为初始状态q1。按照以下规则执行之后，输出正确的计算结果。
q1 0 1 L q2
q1 1 0 L q3
q1 b b N q4
q2 0 0 L q2
q2 1 1 L q2
q2 b b N q4
q3 0 1 L q2
q3 1 0 L q3
q3 b b N q4
9
图灵机对例子的计算过程
S(x) = x + 1
10
现代计算机的产生
自从图灵机思想提出不到10年，世界上第一台电子计算机诞生了
图灵机反映的是一种计算模型，而现代计算机正是这种模型的具体实现
反映了计算学科的抽象、理论和设计3个过程
抽象和理论两个过程关心的是解决具有能行性和有效性的模型问题
设计过程关心的是模型的具体实现问题
11