图灵与图灵机模型26页PPT

形式语言与自动机课件——图灵机
36、如果我们国家的法律中只有某种 神灵， 而不是 殚精竭 虑将神 灵揉进 宪法， 总体上 来说， 法律就 会更好 。—— 马克·吐 温 37、纲纪废弃之日，便是暴政兴起之 时。— —威·皮 物特
38、若是没有公众舆论的支持，法律 是丝毫 没有力 量的。 ——菲 力普斯 39、一个判例造出另一个判例，它们 迅速累 聚，进 而变成 法律。 ——不 容忽视 的。— —爱献 生
46、我们若已接受最坏的，就再没有什么损失。——卡耐基 47、书到用时方恨少、事非经过不知难。——陆游 48、书籍把我们引入最美好的社会，使我们认识各个时代的伟大智者。——史美尔斯 49、熟读唐诗三百首，不会作诗也会吟。——孙洙 50、谁和我一样用功，谁就会和我一样成功。——莫扎特

多维图灵机
多维图灵机具有通常的有限控制器，但带却 由k维单元阵列组成。这里，在所有2k个方 向上（k个轴，每轴正、负两个方向），都 是无限的，根据状态和扫视的符号，该装 置改变状态，打印一个新的符号，在2k个 方向上移动它的读头，开始时，输入沿着 一个轴排列，读头在输入的左端。
离线图灵机
定理4-5 如果L被一个二维图灵机M1接受， 那么L将被一个一维图灵机M2接受。
数 以图灵机为模型,研究问题的可计算性，即
确定该问题是可计算的、部分1 图灵机模型 4.2 图灵机的变化和组合 4.3 通用图灵机 4.4 图灵机可计算性
4.1 图灵机模型
4.1 图灵机模型
定义4-1 图灵机M = ( K, Σ, Γ, δ, q0, B,F)， 其中
定义4-3 设当前的瞬时描述 ID1= x1x2 … xi-1 q xi … xn
若有δ(q, x i) = (p, y, L)，则图灵机瞬时描述 变为 ID2 = x 1x 2 …x i-2p x i-1 y x i+1 … x n；
若有 δ(q, x i) = (p, y, R)，则图灵机瞬时描 述变为 ID2 = x1x2 … xi-1 y pxi+1 … xn。
4.1 图灵机模型
【例4-4】设计一个图灵机，计算二个自然数m、n
的减法：
m-n 若m≥n
m－n=
0 否则
设计时，整数n用0n表示。开始时，带上符号为 0m10n，结束时，带上符号为0。每当在1的左边 将一个0改变为B，就在1的右边将一个0改为1， 若1的右边无0时，再将左边改为B的0恢复回来。
4.1 图灵机模型
δ(q,a)=(p,b,z) 表示状态q下读头所读符号为a时，状态转移为p, 读头符号变为b，同时读头变化为z.

在宾尼法尼大学诞生，命名EDVAC（埃德瓦克）. 存储原理、快240倍（1952核武器理论运算） 与此同时，同样类型的被称为EDSAC（埃德沙克）的 电子延迟存储自动计算机 由英国剑桥大学的 Maurice
Wilkes 制造产生.
28
国内第一台模拟电子计算机 1956年，东北大学教授李华天带领工作人员开发 研制出国内第一台模拟电子计算机。 全套设备占地面积 40 平方米，拥有 5 个 2.3 米高的
1930 普林斯顿大学客座教授， 1931 年他成
为美国普林斯顿大学的第一批终身教授
1933 年转到该校的高级研究所，成为最初 六位教授之一，并在那里工作了一生．
14
四个子系统 Four subsystems
基于冯诺依曼模型的计算机分为四个子系统: 存储器memory 、算术逻辑单元 arithmetic logic unit, 控制单元control unit、输入输出单元 input/output
17世纪，法国Blaise Pascal发明了 Pascaline. 一个用来进行加减运算的计算 机器。20世纪，尼克劳斯.澳思发明了一种结构化程序设计语言Pascal 17世纪后期，德国数学家Gottfried Leibnitz 发明了既能进行乘除又能加减 的更复杂的机器，该机器称为莱布尼茨之轮 Leibnitz’ wheel.
Figure 1.2 基于图灵模型的计算机：可编程数据处理器
9
Figure 1.3 相同的程序，不同的数据
10
Figure 1.4 相同的数据，不同的程序
11
通用图灵机 The universal Turing machine
通用图灵机是对现代计算机的首次描述， 该机器只要提供了合适的程序就能做任何计算。

穷的、构造性的问题求解思路，一个问题的求解可以通过构造其图灵机(即程 序)来解决。 (4)图灵认为：凡是能用算法方法解决的问题也一定能用图灵机解决; 凡是 图灵机解决不了的问题任何算法也解决不了----图灵可计算性问题。
谢谢观看！
过三第一组全体成员！
用》，提出了图灵机模型，后来，冯·诺依曼根据这个模型设
计出历史上第一台电子计算机。 1950 年，发表了划时代的文章：《机器能思考吗?》,成为了人 工智能的开山之作。
计算机界于1966年设立了最高荣誉奖：ACM 图灵奖。
你能查阅一下哪些人获得图灵奖了吗？ 因为什么贡献而获奖呢？
图灵认为什么是计算?
控制器
0,0,R 1,1,R
S1
0,0,N S4
1,1,R S2
0,1,L 1,1,L
S3
001111000
S1：开始状态 S2：右移状态 S3：左移状态 S4：停机状态
功能：将一串1的后面再加一位1
(S1,0,0,R,S1)
001111000
(S1,1,1,R,S2)
001111000
(S2,1,1,R,S2)
计算
所谓计算就是计算者(人或机器)对一条两端可无限延长的纸带上的一串 0或1，执行指令一步一步地改变纸带上的0或1，经过有限步骤最后得到 一个满足预先规定的符号串的变换过程。
0110101
程 序
…10001110110
输入
通用机器
由“程序”控制，
一步步将输入 10001…
“转换”为输出
输出
0110101
执
001111000
行 过
程
(S2,0,1,L,S3)
001111000 (S3,1,1,L,S3)

＝ （302.578125）10
.
27
一般地，任意一个八进制数可以表示为： C ＝ c n－18 n－1 +c n－28 n－2 +…+c 18 1 +
c 08 0+c－18－1 +…+c－m8－m
在上式中，C i 只能取0～7之一的值；八进制 的基数是8。
.
28
（4）十六进制
十六进制记数法也有两个特点：
.
40
必须注意:
逐次除2取余的余数是按从低位到高位的 排列顺序与二进制整数数位相对应的；逐 次乘2取整的整数是按从高位向低位的排列 顺序与二进制小数数位相对应的。其共同 特点是以小数点为中心，逐次向左、右两 边排列。
.
41
（1）八进制、十六进制数转换成十进制数
同二进制数到十进制数的转换，分别套用 相应公式 。
.
24
例如： （10110.1）2 ＝ 1×2 4 ＋0×2 3 ＋1×2 1 ＋0×2 0 ＋1×2－1 ＝ （22.5）10
任意一个二进制数B，可以展开成多项式之和, 即
B = b n－12 n－1 +b n－22 n－2 +…+b 12 1+b 02 0+
b－12－1 +…+b－m2－m
.
25
.
30
一个任意的十六进制数可以表示为： D ＝ d n－116 n－1 +d n－216 n－2 +…
+d 116 1+d 016 0 +d －116－1 +…+d－m16－m 在上式中，d i可以取0～F之一的值；十六进制 的基数是16。
.

在一个图灵机的动作中图灵机根据带头读写头所扫描的符号和有限控制器的状态可能作在一个图灵机的动作中图灵机根据带头读写头所扫描的符号和有限控制器的状态可能作?改变状态?在被扫描的带单元上重新写一个符号以代替图灵机的工作机制4schoolofcomputerscienceamp
• TM的基本定义 • TM的格局 • TM接受的语言 • TM的构造技术 • TM的变形；
• 改变状态 • 在被扫描的带单元上重新写一个符号，以代替原来写在该单元上的符号. • 将带头向左或者右移一个单元。 * 图灵机和双向有限自动机的区别：图灵机能改变它带上的符号。
3
第3页/共31页
图灵机的形式化描述
形式定义 一个图灵机 TM (Turing machine) 是一个七元组
M = (Q, T, , , q0 , B , F ).
├M X0Yq31Z2 ├*M q3X0Y1Z2 ├M Xq00Y1Z2 ├*M XXYYZq22
├M XXYYq3ZZ├*M Xq3XYYZZ├M XXq0YYZZ├*M XXYYq4ZZ
11
├M XXYYZq5Z ├M XXYYZZq5B ├M XXYYZZBq6B
第11页/共31页
Y/Y
Z/Z
Z/Z
转移图与转移表
0/0
1/1
1/1
Y/Y
Start
q0 0 / X
q1 1 / Y
q2 2 / Z
q3
0/0
Y/Y q4 Z / Z
X/X
q5 B / B
q6
Y/Y
Z/Z
State 0
1
Symbol
2
X
Y
Z
B
q0 (q1 ,X, R) q1 (q1 ,0, R) q2 q3 (q3 ,0, L) q4

1.2 计算机系统结构的概念
1. Amdahl提出的系统结构 传统机器语言级程序员所看到的计算机属性。 1. 广义的系统结构定义：指令集结构、组成、硬件
（计算机设计的3个方面）
2. 对于通用寄存器型机器来说，这些属性主要是指： 指令系统
包括机器指令的操作类型和格式、指令间的 排序和控制机构等。
计算机系统结构的发展
1.1 引 言
1. 第一台通用电子计算机诞生于1946年 2. 计算机技术的飞速发展得益于两个方面
计算机制造技术的发展
计算机系统结构的创新
3. 经历了4个发展过程
1.1 引言
时 间
1946年起的25年 20世纪70年代末 －80年代初
原 因
两种因素都起着主要的作用 大规模集成电路和微处理器 出现,以集成电路为代表的制 造技术的发展
信息保护
（包括信息保护方式和硬件对信息保护的支持）
1.2 计算机系统结构的概念
I/O结构
包括I/O连结方式、处理机/存储器与I/O设备之间
数据传送的方式和格式以及I/O操作的状态等
计算机系统结构概念的实质：
确定计算机系统中软、硬件的界面，界面之上是软件实
现的功能，界面之下是硬件和固件实现的功能。
按照指令流和数据流的多倍性进行分类。 指令流：计算机执行的指令序列。
1.2 计算机系统结构的概念
数据流：由指令流调用的数据序列。 多倍性：在系统受限的部件上，同时处于同一执
行阶段的指令或数据的最大数目。
Flynn分类法把计算机系统的结构分为4类：

单指令流单数据流(SISD)
每年的性能增长
25%
约35%
20世纪80年代中开 RISC结构的出现，系统结构不断更 始 新和变革，制造技术不断发展 2002年以来 3个（见下页）

• 笔者早期也曾涉及此类研 究，提出过“可构造实数 论中若干谓词在Kleen分层 下所属的类型”（《数学 学报》1964年第四期。）
28
6.怎么度量计算的能力和复杂度
• 图灵机的提出，影响深远，可以说它为以 后整个计算机科学的研究奠定了重要的理 论基础。
• 例如关于形式语言和自动机的理论和算法 复杂度的理论研究就以图灵机作为基础， 它对计算机编译系统和操作系统技术以及 应用软件的发展起着重要作用。
(L)或右移(R)一格。
12
图灵机器 演示
S ：{ql
Q：{ q1,…,qm } si,qj sk,ql, d 其中 d = H,L 或 R
13
通用图灵机的概念 演示
• 存在这样的一个图灵机T，称为通用图灵机 (Universal Turing Machine ) :
23
有一些对此论题的质疑
• 当然在学界也有一些对此论题的质疑， • 例如有人认为交互式机器超越了图灵机（Peter
Wegner）， • 有人认为量子计算机，生物计算机可能会超越图
灵机，但是这些意见都还没有能给出具有说服力 的论证，从而也没有为普遍学者所认可。 • 在纪念图灵诞辰100周年之际，关于是否有超越 图灵机计算能力的模型也是一个争论的热门话题。
• ENIAC是一台为各种炮火 计算弹道的专用计算机， 程序是用外接电路板输入。
• 后查证，世界上第一台专用电子计算机，1939 年爱荷华 （Iowa） 州立大学用电子管开发了Atanasoff –Berry Computer(简称ABC)，另外，二战中德国也研制了计算机。
15
冯·诺伊曼的设计思想
西北大学信息科学与技术学院
“大学生IT创新教学实践”活动

第4章 图灵机
许桂靖 杨 莹
精选
Overview
图灵机（Turing Machine，TM），是 计算机的一种简单的数学模型。
历史上，冯•诺曼计算机的产生就是由 图灵机诱发的。
丘奇—图灵论题：一切合理的计算模 型都等同于图灵机.
精选
类型 文 法 结 构 产 生 式 形 式 限 制 条 件
0 短语结构文法 Phrase Structure
精选
4.1 图灵机模型
定义4-3 瞬时描述ID1经过一步变为瞬时描述ID2，称
ID1与ID2具有一步变化关系，表示为 ID1├ID2
若ID1经过n步变为ID2(n≥0)，即有 ID1├ID├… ├ ID2
称ID1与ID2具有多步变化关系，简记为 ID1 ├*ID2
精选
4.1 图灵机模型
定义4-4 对于图灵机M = ( K, Σ, Γ, δ, q0, B, F)，定义图灵机接受的语言集 L(M) 为 L(M)={w|∈Σ* ∧q∈K∧qf ∈F ∧q0w├*u0qB├*uqfv)}
精选
4.1 图灵机模型
【例4-1】设计一个图灵机，使得 L(M) = {0 n1 n | n≥1}。
设计思路: 在带上每当将一个0变为X，就把 一个1变为Y。当将所有的0变为X时，恰将 所有的1变为Y，这个串就是合法的，最后 将X、Y分别还原为0、1。
精选
4.1 图灵机模型
精选
4.1 图灵机模型
精选
4.1 图 灵 机 模 型
精选
4.1 图灵机模型
【例4-4】设计一个图灵机，计算二个自然数m、n
的减法：
m-n 若m≥n
m－n=
0 否则
设计时，整数n用0n表示。开始时，带上符号为 0m10n，结束时，带上符号为0。每当在1的左边 将一个0改变为B，就在1的右边将一个0改为1， 若1的右边无0时，再将左边改为B的0恢复回来。

15
图灵简介
• 1939年为“二战”服务，主要从事破译德军 密码工作。
– 他用继电器（后改用电子管）做成译码机，破译 了不少密报，发现了德军的动向，为盟军战胜德 国法西斯立了不少功劳。
– 二战期间，他除了不修边幅、讲话木讷、孤僻等 外，最不可思议的是他对英国获胜没有信心，把 所有积蓄换成两条银条埋了起来，但后来记不起 埋在哪儿了。
– 1946年5月以前由于找不到称心的助手，一直“单枪匹马”，直到威 尔金森（1970年图灵奖获得者）成了图灵得力助手，此时ACE已到 第5版，前4版由于图灵不善于也不重视保管文档资料而不知去向。
– ACE是一种存储程序式计算机，但其存储程序思想并非受冯·诺伊曼 论文的影响，而是他自己的构思。冯·诺伊曼本人也从来没有说过存 储程序的概念是他的发明，却不止一次地说过图灵是现代计算机设计 思想的创始人。
6
实例
• 设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
• 这个时期，他对生物学和化学也产生了兴趣，曾经 发表有关器官形成的化学基础的论文，探讨海星为 什么呈五轴对称，原肠胚在特定的点上形成沟槽等 现象。这使他被公认为是生物学中研究器官形态领 域的先驱，也是远离平衡态化学的奠基人。
• 由于图灵的一系列杰出贡献和重大创造，1951年他 被选为英国皇家学会院士。