计算机科学与计算机工程 ·与CE相关的三个经典问题 -巴贝奇(Charles Babbage)问题，1833 ·自动计算的实现：程序控制 ·建造“分析机”：三角函数、级数相乘、伯努利函数 ·Ada,第一位程序员，Ada语言1981 一图灵问题：智能的机械化 -布什(Vannevar Bush)问题，1945 ·“As We May Think'”:信息的广义互连？ ·计算机研究的两条路线 一计算机理论：图灵 ·Turing Machine,1936,可计算性，存储程序 一计算机工程：冯·诺依曼 ·von Neuman Machine,1945,存储程序
计算机科学与计算机工程 • 与CE相关的三个经典问题 – 巴贝奇（Charles Babbage）问题，1833 • 自动计算的实现：程序控制 • 建造“分析机”：三角函数、级数相乘、伯努利函数 • Ada，第一位程序员，Ada语言1981 – 图灵问题：智能的机械化 – 布什（Vannevar Bush）问题，1945 • “As We May Think”：信息的广义互连？ • 计算机研究的两条路线 – 计算机理论：图灵 • Turing Machine，1936，可计算性，存储程序 – 计算机工程：冯·诺依曼 • von Neuman Machine，1945，存储程序
能行计算理论(computability thed) ·计算：是对运算过程的一种高度抽象 ·算法 一对计算的步骤或状态的一种刻画，是计算方法的一种实现方式 一将计算抽象为输入到输出的函数映射，是一个封闭的计算过程 算法可计算性：判断一类数学问题是否机械可解 一可计算问题：算术逻辑运算 一非可计算问题：明天是否下雨？ ·计算模型(MoC) 一刻画“计算”概念的抽象的形式化系统或数学系统。 ·入演算（串行、递归）、π演算（并行、分布）等 -状态迁移系统(LTS) ·具有状态转换特征，能够对所处理的对象的数据或信息进行表示、 加工、变换、输出的数学机器。 一图灵机
能行计算理论(computability theory) • 计算：是对运算过程的一种高度抽象 • 算法 – 对计算的步骤或状态的一种刻画，是计算方法的一种实现方式 – 将计算抽象为输入到输出的函数映射，是一个封闭的计算过程 • 算法可计算性：判断一类数学问题是否机械可解 – 可计算问题：算术逻辑运算 – 非可计算问题：明天是否下雨？ • 计算模型（MoC） – 刻画“计算”概念的抽象的形式化系统或数学系统。 • λ演算(串行、递归)、π演算（并行、分布）等 – 状态迁移系统（LTS） • 具有状态转换特征，能够对所处理的对象的数据或信息进行表示、 加工、变换、输出的数学机器。 – 图灵机
MoC:图灵机(Turing Machine,1936) STC 自动计算机结构与行为 一一条两端可以无限延伸的纸带 01 -一个读写头（符号包括0、1、b) 一个控制器（执行控制读写头工作的命令） 五元组：（状态、读符号）（写符号、移动、状态》 状态集：开始状态，中间状态，结束状态 当进入结束状态时，停机(H) 六个操作原语(primitives):读、写、左、右、擦除、停止 控制命令示例： 00011101111100 qi01Rq 控制器 q10Rq q bbRq2 q2bbLq3 初始状态 中间状态 结束状态 q200Hq1 q211Hq1
MoC：图灵机(Turing Machine,1936) • 自动计算机结构与行为 – 一条两端可以无限延伸的纸带 – 一个读写头（符号包括0、1、b） – 一个控制器（执行控制读写头工作的命令） • 五元组：（状态、读符号）→（写符号、移动、状态） – 状态集：开始状态，中间状态，结束状态 – 当进入结束状态时，停机(H) – 六个操作原语（primitives）：读、写、左、右、擦除、停止 0 0 0 1 1 1 0 1 1 1 1 1 0 0 控制器 q101Rq1 q110Rq1 q1bbRq2 q2bbLq3 q200Hq1 q211Hq1 控制命令示例：
关于MoC的两个重要原理 一计算复杂性是否与计算模型有关？ 一不同计算模型解决同一类问题所需资源是否相同？ 相似性原理 一相似性原理：所有计算模型的计算能力等同 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 ·Turing完备性 丘奇一图灵论题：可计算性等价于图灵机的可计 算性 ·对偶性原理 一在并行计算模型上，计算的时间与空间可以互换
关于MoC的两个重要原理 – 计算复杂性是否与计算模型有关？ – 不同计算模型解决同一类问题所需资源是否相同? • 相似性原理 – 相似性原理：所有计算模型的计算能力等同 • 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 • Turing完备性 – 丘奇－图灵论题：可计算性等价于图灵机的可计 算性 • 对偶性原理 – 在并行计算模型上，计算的时间与空间可以互换
图灵完备性Turing-complete/Turing-equivalent ·图灵机：六个基本原语 一如果某个系统能够模拟图灵机，那么就称该系 统是图灵完备的 Brainfuck ·图灵完备语言 > ++ptr; --ptr; + -最小图灵完备语言BF(1993) ++*ptr; --*ptr; ·机器模型+8种运算符 putchar(*ptr); *ptr =getchar(); ·非图灵完备语言 [ while (*ptr){ -HTML,XML... 在屏幕上打印"Hello World" ·算盘=计算机？ 1++++++++[>+++++>+++++++>++>+<<<<-] 2 >++.>+,+++++++..+++.>++.<<+++++++++++++++. 3 >.+++.-- ---.>+.>
图灵完备性Turing-complete/Turing-equivalent • 图灵机：六个基本原语 – 如果某个系统能够模拟图灵机，那么就称该系 统是图灵完备的 • 图灵完备语言 – 最小图灵完备语言BF（1993） • 机器模型+8种运算符 • 非图灵完备语言 – HTML，XML… • 算盘=计算机？ 在屏幕上打印"Hello World!