中国科学技术大学：《计算机科学导论》课程教学资源（PPT课件讲稿）第五讲 经典计算的计算模型（主讲：陈意云）

课程内容 课程内容 围绕学科理论体系中的模型理论,程序理论和计算理论 1.模型理论关心的问题 给定模型M,哪些问题可以由模型M解决;如何 比较模型的表达能力本讲座简要介绍三种经 2.程序理论关心的问题典的抽象计算模型 给定模型M,如何用模型M解决问题 包括程序设计范型、程序设计语言、程序设计 形式语义、类型论、程序验证、程序分析等 3.计算理论关心的问题 给定模型M和一类问题,解决该类问题需多少资源

课 程 内 容 • 课程内容 围绕学科理论体系中的模型理论, 程序理论和计算理论 1. 模型理论关心的问题 给定模型M，哪些问题可以由模型M解决；如何 比较模型的表达能力 2. 程序理论关心的问题 – 给定模型M，如何用模型M解决问题 – 包括程序设计范型、程序设计语言、程序设计、 形式语义、类型论、程序验证、程序分析等 3. 计算理论关心的问题 给定模型M和一类问题, 解决该类问题需多少资源 本讲座简要介绍三种经 典的抽象计算模型 2

讲座提纲 基本知识 计算、计算模型、并行计算模型 图灵机概述 图灵的基本思想、基本图灵机、图灵机的变种 λ演算 入表达式的文法、λ演算的变换规则、 Church数 码 递归函数 直观意义的可计算函数、原始递归函数、递归函 数

讲 座 提 纲 • 基本知识 – 计算、计算模型、并行计算模型 • 图灵机概述 – 图灵的基本思想、基本图灵机、图灵机的变种 • 演算 – 表达式的文法、 演算的变换规则、Church数 码 • 递归函数 – 直观意义的可计算函数、原始递归函数、递归函 数 3

基本知识 计算 抽象地说,计算就是从一个符号序列y得出另 个符号序列n(从y出发,在有限步内真正求出m) y:12+3,:15 ∥该计算是加法 y:x×x,们:2x ∥该计算是微分 y:英文句子,:含意相同的中文句子翻译 y:一组公理和推理规则,7:一个定理/定理证明 下面的是完全定义的函数,但函数值求不出来 1若在z的十进制表示中有连续x个5 f(r) 0其他情况

基 本 知 识 • 计算 抽象地说，计算就是从一个符号序列 得出另一 个符号序列（从 出发，在有限步内真正求出） –  : 12+3,  : 15 //该计算是加法 –  : x  x,  : 2x //该计算是微分 –  : 英文句子,  : 含意相同的中文句子 //翻译 –  : 一组公理和推理规则,  : 一个定理 //定理证明 下面的f是完全定义的函数，但函数值求不出来 1 若在 的十进制表示中有连续x个5 f(x) = 0 其他情况 4

基本知识 计算 不要狭隘理解计算 很多非数值问题(如文字识别,图像处理等)都 可以转化为数值问题来交给计算机处理(可以在有 限步骤内被解决) 不要对计算有过高预期 哥德巴赫猜想问题不属于“可计算问题”之列: 因为计算机无法给出数学意义上的证明 没有任何理由期待计算机能解决世界上所有的问 题

基 本 知 识 • 计算 – 不要狭隘理解计算 很多非数值问题（如文字识别，图像处理等）都 可以转化为数值问题来交给计算机处理（可以在有 限步骤内被解决） – 不要对计算有过高预期 哥德巴赫猜想问题不属于“可计算问题”之列， 因为计算机无法给出数学意义上的证明 没有任何理由期待计算机能解决世界上所有的问 题 5

基本知识 计算模型 刻画计算概念的抽象形式(0m系统或数学系统 如图灵机、λ演算、递归函数和Post系统 在可计算性理论和计算复杂性理论中,计算模型 是指包括一组操作及其代价的抽象机器 可用来实现算法 可度量算法的执行时间和空间的复杂性 ●可分析算法需要的计算资源 ●可讨论算法或计算机的局限

基 本 知 识 • 计算模型 – 刻画计算概念的抽象形式(formal)系统或数学系统 如图灵机、演算、递归函数和Post系统 – 在可计算性理论和计算复杂性理论中，计算模型 • 是指包括一组操作及其代价的抽象机器 • 可用来实现算法 • 可度量算法的执行时间和空间的复杂性 • 可分析算法需要的计算资源 • 可讨论算法或计算机的局限 6

基本知识 并行计算模型 通常指把各种(至少一类)并行计算机的基本特 征抽象出来,由此形成的抽象并行机器 对于串行计算机,全世界基本上都在使用冯·诺伊 曼的计算模型;对于并行计算,一些有价值的参考 计算模型已提出,但没有一个能被大家接受的统 的计算模型 新型计算的计算模型 云计算模型、网域( cyberspace)计算模型

基 本 知 识 • 并行计算模型 – 通常指把各种（至少一类）并行计算机的基本特 征抽象出来，由此形成的抽象并行机器 – 对于串行计算机，全世界基本上都在使用冯·诺伊 曼的计算模型；对于并行计算，一些有价值的参考 计算模型已提出，但没有一个能被大家接受的统一 的计算模型 • 新型计算的计算模型 – 云计算模型、网域（cyberspace）计算模型 7

图灵机概述 图灵的基本思想 用机器来模拟人用纸和笔进行数学计算的过程, 该过程由两类简单动作的序列构成 在纸上写出或擦除某个符号 把注意力从纸上一个位置移到另一个位置 决定下一步动作的依据:纸上某个位置的符号和 人当前的思维状态 为模拟人的这种计算过程,图灵( Turing)在20世纪 30年代构造了一种假想的简单机器

图 灵 机 概 述 • 图灵的基本思想 用机器来模拟人用纸和笔进行数学计算的过程， 该过程由两类简单动作的序列构成 – 在纸上写出或擦除某个符号 – 把注意力从纸上一个位置移到另一个位置 决定下一步动作的依据：纸上某个位置的符号和 人当前的思维状态 为模拟人的这种计算过程，图灵(Turing)在20世纪 30年代构造了一种假想的简单机器 8

图灵机概述 基本图灵机纸带[aa2…|a1…anbb 读写头 有限根据机器所 控制器处状态以及读 有一个状写头所指符号 态寄存器来决定读写头

图 灵 机 概 述 • 基本图灵机 根据机器所 处状态以及读 写头所指符号 来决定读写头 的动作 a1 a2 … ai … an b b … 有限 控制器 纸带 读写头 有一个状 态寄存器 9

图灵机概述 基本图灵机纸带[aa2…|a1…anbb T=(Q,r,b,Σ,q0,F,δ) 读写头 Q:有穷非空的状态集 有限 I:有穷非空的带符号集 控制器 b∈r:空白符号 ∑cI{b}:输入符号集 q0∈Q:开始状态 FcQ:终止状态集 δ:(QF×)→Qxr×{,R:迁移函数,L和R表 示读写头的左右移 例如:8(q0,0)-(q1,X,R,δ(q1,1)->(q2,Y,L)0

图 灵 机 概 述 • 基本图灵机 T= Q, , b, , q0 , F,   – Q: 有穷非空的状态集 – : 有穷非空的带符号集 – b: 空白符号 –  \{b}: 输入符号集 – q0Q: 开始状态 – FQ: 终止状态集 –  :(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={01n≥1} 的图灵机 有限 策略:从左向右,控制器 轮番把带上最左的0和1分别写成X和Y(期间要向右 和向左移动读写头),直至全部写完 T=〈Q,r,b,Σ,q0,F,) Q={q0,q1,…,q5 F={0,1,b,X,Y ∑={0,1} F={5 6见下一页

图 灵 机 概 述 • 例： 识别语言 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