基本知识 并行计算模型 -通常指把各种 (至少一类)并行计算机的基本特 征抽象出来，由此形成的抽象并行机器 对于串行计算机，全世界基本上都在使用冯·诺伊 曼的计算模型；对于并行计算，一些有价值的参考 计算模型已提出，但没有一个能被大家接受的统 的计算模型 新型计算的计算模型 云计算模型、网域(cyberspace)计算模型
基 本 知 识 • 并行计算模型 – 通常指把各种（至少一类）并行计算机的基本特 征抽象出来，由此形成的抽象并行机器 – 对于串行计算机，全世界基本上都在使用冯·诺伊 曼的计算模型；对于并行计算，一些有价值的参考 计算模型已提出，但没有一个能被大家接受的统一 的计算模型 • 新型计算的计算模型 – 云计算模型、网域（cyberspace）计算模型 7
图灵机概述 图灵的基本思想 用机器来模拟人用纸和笔进行数学计算的过程， 该过程由两类简单动作的序列构成 - 在纸上写出或擦除某个符号 把注意力从纸上一个位置移到另一个位置 决定下一步动作的依据：纸上某个位置的符号和 人当前的思维状态 为模拟人的这种计算过程，图灵(Turing)在20世纪 30年代构造了一种假想的简单机器
图 灵 机 概 述 • 图灵的基本思想 用机器来模拟人用纸和笔进行数学计算的过程， 该过程由两类简单动作的序列构成 – 在纸上写出或擦除某个符号 – 把注意力从纸上一个位置移到另一个位置 决定下一步动作的依据：纸上某个位置的符号和 人当前的思维状态 为模拟人的这种计算过程，图灵(Turing)在20世纪 30年代构造了一种假想的简单机器 8
图灵机概述 。基本图灵机 纸带 aaa…anbb 读写头 有限 根据机器所 控制器 处状态以及读 有一个状 写头所指符号 态寄存器 来决定读写头 的动作
图 灵 机 概 述 • 基本图灵机 根据机器所 处状态以及读 写头所指符号 来决定读写头 的动作 a1 a2 … ai … an b b … 有限 控制器 纸带 读写头 有一个状 态寄存器 9
图灵机概述 基本图灵机 纸带 a2…4.anbb T=(2,T,b,Σ，qo,F,δ〉 读写头 - Q:有穷非空的状态集 有限 - T:有穷非空的带符号集 控制器 -b∈T:空白符号 - ∑sT{b:输入符号集 - 4o∈2：开始状态 FsO:终止状态集 -δ：(QF×)→Q×T×{L,R:迁移函数，L和R表 示读写头的左右移 例如：8(go,0)→(q1,X,R),δ(q1,1)-→(q2,Y,L)0
图 灵 机 概 述 • 基本图灵机 T= Q, , b, , q0 , F, – Q: 有穷非空的状态集 – : 有穷非空的带符号集 – b: 空白符号 – \{b}: 输入符号集 – q0Q: 开始状态 – FQ: 终止状态集 – :(Q\F ) → Q {L, R}: 迁移函数， L和R表 示读写头的左右移 例如： (q0 , 0)→(q1 , X, R), (q1 , 1)→(q2 , Y, L) a1 a2 … ai … an b b … 有限 控制器 纸带 读写头 10
图灵机概述 。例： 000111bb 识别语言 L={0n1n|n≥1} 的图灵机 有限 控制器 策略：从左向右， 轮番把带上最左的0和1分别写成和Y(期间要向右 和向左移动读写头)，直至全部写完 T=〈2，T,b,∑，qo,F,δ》 -2={q0,41,,q5} -T={0,1,b,X,W -2={0,1} F={4s) -δ见下一页 11
图 灵 机 概 述 • 例： 识别语言 L={0n1 n | n 1} 的图灵机 策略：从左向右， 轮番把带上最左的0和1分别写成X和Y（期间要向右 和向左移动读写头），直至全部写完 T= Q, , b, , q0 , F, – Q = {q0 , q1 , …, q5 } − = {0, 1, b, X, Y} – = {0, 1} − F = {q5 } – 见下一页 0 0 0 1 1 1 b b … 有限 控制器 11