第四章：图灵论题.ppt

1
计算理论
2
引言
什么是计算?
计算机的基本能力和局限性是什么?
3
引言
Alan M. Turing (1912–1954)
In 1936, Turing introduced hisabstract model putation inhis article “putable Numbers,”.
At the same time, Alonzo Church published similar ideas and results.
Turing model 成为理论计算科学的标准模型standard model
4
引言
图灵机(Turing Machine,TM),是计算机的一种简单的数学模型。
历史上,冯•诺曼计算机的产生就是由图灵机诱发的。
丘奇—图灵论题:一切合理的计算模型都等同于图灵机.
5
主要内容
丘奇—图灵论题
图灵机的形式化定义
图灵机的例子
图灵机的变形
多带图灵机
非确定型图灵机
枚举器
与其他模型的等价性
算法的定义
希尔伯特问题
描述图灵机的术语
6
图灵机(Turning Machine)
非形式化描述
根据当前状态和字符 xi ,决定写移转三动作
-写 letter, 有存储器- 左或右移动
转移状态可以作循环语句
磁带相当于数组,可读写。这是增加的重要资源
internal state set Q
R
L
每一步,读写头在单向无穷带上左右移动并读写。
7
图灵机
state q0
初始, 带子上只有输入串w*,其它地方是空的。开始状态 q0。
计算过程中读写头左右移动,机器内部状态改变,带子上内容重写。
数组结构
8
图灵机
输出约定
三种输出:接受、拒绝、循环
state ept
state qreject
or
非常规意义循环——不停机
引出可判定性
9
图灵机与有限自动机
状态
控制器
相似性:有限状态集
区别:
(1)图灵机在带子上既能读也能写。
(2)图灵机的读写头既能向左也能向右移动。
(3)图灵机的带子是无限长的。
(4)图灵机进入拒绝和接受状体将立即停机。
10
图灵机
考虑图灵机 M1,它检查语言 B = { w#w | w∈{0,1}* } 的成员关系。即设计 M1,使得如果输入是 B 的成员,它就接受,否则拒绝。
M1=“对于输入字符串 w
(1) 在# 两边对应的位置上来回移动,检查这些对应位置是否包含相同的符号,如不是,或者没有#,则拒绝,为跟踪对应的符号,消去所有检查过的符号。
(2) 当# 左边的所有符号都被消去时,检查# 右侧是否还有符号,如果有则拒绝,否则接受。”