MoC:图灵机(Turing Machine,1936) STC 自动计算机的结构与行为(ABC) 一一条两端可以无限延伸的纸带 一个读写头（符号包括0、1、b) 01( 一个控制器（执行控制读写头工作的命令） 五元组：（状态、读符号）→（写符号、移动、状态） -状态集：开始状态，中间状态，结束状态 当进入结束状态时，停机(H) 六个操作原语(primitives):读、写、左、右、擦除、停止 控制命令示例： 00011101111100 qi01Rq 控制器 q10Rq q bbRq2 q2bbLq3 初始状态 中间状态 结束状态 q200Hq1 q211Hq1
MoC：图灵机(Turing Machine,1936) • 自动计算机的结构与行为（ABC） – 一条两端可以无限延伸的纸带 – 一个读写头（符号包括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 控制命令示例：
图灵完备性Turing-complete/.Turing-equivalent ·图灵机：六个基本原语 如果某个系统能够模拟图灵机，那么就称该系统是 图灵完备的 一读、写、擦除、左移、右移、停机 Brainfuck C > ++ptr; 图灵完备语言 --ptr; + ++*ptr; -最小图灵完备语言BF(1993) --*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!
关于MoC的两个重要原理 一计算复杂性是否与计算模型有关？ 一不同计算模型解决同一类问题所需资源是否相同？ 相似性原理 一相似性原理：所有计算模型的计算能力等同 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 ·Turing完备性 丘奇一图灵论题：可计算性等价于图灵机的可计 算性 ·对偶性原理 一在并行计算模型上，计算的时间与空间可以互换
关于MoC的两个重要原理 – 计算复杂性是否与计算模型有关？ – 不同计算模型解决同一类问题所需资源是否相同? • 相似性原理 – 相似性原理：所有计算模型的计算能力等同 • 所有合理的、功能足够强大的计算模型可以相互模拟计 算，且使用的本质相同的并行计算时间、串行计算时间 和空间 • Turing完备性 – 丘奇－图灵论题：可计算性等价于图灵机的可计 算性 • 对偶性原理 – 在并行计算模型上，计算的时间与空间可以互换
计算机科学与计算机工程 ·计算机研究的两条路线 一计算机理论：图灵 ·Turing Machine,1936 -可计算性，计算复杂性 -图灵问题：智能的机械化 ·存储程序 一计算机工程：冯诺依曼 von Neuman Machine,1945 ·存储程序：p44 一“指令和数据都存储在存储器中，易于更改
计算机科学与计算机工程 • 计算机研究的两条路线 – 计算机理论：图灵 • Turing Machine，1936 – 可计算性，计算复杂性 – 图灵问题：智能的机械化 • 存储程序 – 计算机工程：冯·诺依曼 • von Neuman Machine，1945 • 存储程序：p44 – “指令和数据都存储在存储器中，易于更改
第一台现代电子计算机，真空管，1946用 唐$2.1 ENIAC(Electronic Numerical Integrator and Computer),1946年宾夕法尼亚大学 运算速度5000次/秒，功耗150kw/h,占地170m2,造价100万美元。用于测定氢弹可靠性。 ·不具备“存储程序”能力一不可编程，且程序无法共享 程序要通过外接电路板输入(wied)。对于不同类型的计算，需要设计相应的外接插板。 十进制并行计算机（同时处理10个数）
第一台现代电子计算机，真空管，1946启用 • ENIAC( Electronic Numerical Integrator and Computer)，1946年宾夕法尼亚大学 – 运算速度 5000次/秒，功耗150kw/h，占地170m2 ，造价100万美元。用于测定氢弹可靠性。 • 不具备“存储程序”能力——不可编程，且程序无法共享 – 程序要通过外接电路板输入（wired）。对于不同类型的计算，需要设计相应的外接插板。 – 十进制并行计算机（同时处理10个数）。 唐$2.1