计算机导论 教案 二

计算机导论 教案 二

2009 2009年秋季计算机学院本科课程

计算机导论(Introduction to Computers)

西南科技大学计算机学院

宋晖 songhui@http://doc.guandang.net1

计算机导论 教案 二

计算机导论 - Introduction to Computers

这次课的主要内容什么是计算与可计算？ 什么是计算与可计算？ 二进制

计算机导论 教案 二

计算机导论 - Introduction to Computers

什么是计算与可计算？ 什么是计算与可计算？

计算机导论 教案 二

计算机导论 - Introduction to Computers

什么是计算(Computing)?直观的计算：数的加减乘除；函数的微分、积分； 直观的计算 ： 数的加减乘除 ； 函数的微分 、 积分 ； 微分 方程的求解；定理的证明推导；等等。 方程的求解；定理的证明推导；等等。 计算的实质： 输入) 计算的实质：从一个符号序列 A(输入)得出另一个符号 输出) 序列 B(输出)。 计算的例子： 计算的例子：A:11+1(由1、1、+、1这四个符号组成),B:12(由1、 : 这四个符号组成) ( 、 、 、 这四个符号组成 ： ( 、 加法。 2这两个符号组成)。从 11+1 得出 12:十进制加法。 这两个符号组成) 这两个符号组成 ：十进制加法 A:11+1,B:100。从 11+1 得出 100:二进制加法。 : 加法。 , : 。 :二进制加法 A:″computer ″,B: ″计算机 。从 ″computer″ 得出 ″计 ： 计算机″。 , : 计算机 计 算机″:英译汉 英译汉。 算机 英译汉。 ....4

计算机导论 教案 二

计算机导论 - Introduction to Computers

什么是可计算(Computable)?从设计和制造一种机器的角度来看， 从设计和制造一种机器的角度来看 ， 我们不能满足于泛 泛的“ 泛的“从 A 得出 B”。 。因此要求： 出发， 有限步内真正具体 因此要求：能够从符号序列 A 出发，在有限步内真正具体 地求出符号序列 B。 。

可计算： 可计算 ： 在可以预先确定的时间和步骤之内能够具体进 行的计算。 行的计算。例如， 请猜出我现在所想的那个数， 例如，当 A 是“请猜出我现在所想的那个数，但你只能猜 一次” 则在预先确定的时间之内不能保证得到 。 一次”,则在预先确定的时间之内不能保证得到 B。

什么样的任务才是可计算的任务？ 什么样的任务才是可计算的任务 ？ 这是计算机科学必须 要回答的一个最基本的问题。 要回答的一个最基本的问题。这是关系到计算机能做什么、不能做什么的根本问题。 这是关系到计算机能做什么、不能做什么的根本问题。 类比：什么样的衣服才是洗衣机可洗的？ 类比：什么样的衣服才是洗衣机可洗的？5

计算机导论 教案 二

计算机导论 - Introduction to Computers

什么是可计算(Computable)?在电子数字计算机出现之前， 在电子数字计算机出现之前 ， 数理逻辑学家们就开始研 究可计算问题了。他们的思路

是： 究可计算问题了。他们的思路是：为计算建立一个数学模型，称为计算模型 然后证明， 计算模型， 为计算建立一个数学模型，称为计算模型，然后证明，凡 是这个计算模型能够完成的任务，就是可计算的任务。 是这个计算模型能够完成的任务，就是可计算的任务。

图灵机就是这样的一个计算模型。 图灵机就是这样的一个计算模型。用图灵机能够得出对应的符号序列 给定符号序列 A,如果用图灵机能够得出对应的符号序列 ，如果用图灵机能够得出 可计算的 B,那么从 A 到 B 就是可计算的。 就是可计算 ，

Church 已经证明：图灵机、递归函数、λ演算和 Post系 已经证明：图灵机、递归函数、 演算和 系 统这四种计算模型是等价的。这意味着， 统这四种计算模型是等价的 。 这意味着 ， 人们可以选择 最合适的计算模型来确定一个任务是否可计算。 最合适的计算模型来确定一个任务是否可计算。

计算机导论 教案 二

计算机导论 - Introduction to Computers

图灵机一个图灵机包括三个部分： 一个图灵机包括三个部分：一条无限长的带：带上划上格子， 一条无限长的带：带上划上格子，每个格子中可以写一个 符号；所有允许出现的符号属于一个预先规定好的字母表。 符号；所有允许出现的符号属于一个预先规定好的字母表。 一个读写头：每次可以从带上读出一个符号， 一个读写头：每次可以从带上读出一个符号，也可以擦去 或改写这个符号；读写头可以左移一格、 或改写这个符号；读写头可以左移一格、右移一格或者保 持不动。 持不动。 一个控制器： 一个控制器： 控制器里存有一个程序(Program)(程序就 是指令 (Instructions)的序列 ) ; 控制器在每个时刻处于一 定的状态，叫做机器状态；当读写头从带上读出一个符号 定的状态， 叫做机器状态； 机器状态 控制器就根据这个符号和当时的机器状态， 后，控制器就根据这个符号和当时的机器状态，参照程序 作出反应，即指挥读写头进行书写或者移动， 作出反应，即指挥读写头进行书写或者移动，并决定是否 改变机器状态。 改变机器状态。7

计算机导论 教案 二

计算机导论 - Introduction to Computers

用图灵机来进行计算代表空白 代表空白

例：读写头 带 控制器 程序 q1 q1 q2 q2 q3 q3 1 b 1 b 1 b 1 1 1 b b b R R R L H H

字 母 表： { 1, b } 机器状态： 机器状态： { q1, q2, q3 }

一条指令

q1 q2 q2 q3 q3 q38

计算机导论 教案 二

计算机导论 - Introduction to Computers

用图灵机来进行计算代表空白 代表空白

例：读写头 带 当前机器状态 控制器 程序

字 母 表： { 1, b } 机器状态： 机器状态： { q1, q2, q3 }

当前应写入的符号 读写头的动作： 读写头的动作：

当前读入的符号

q1 q1 q2 q2 q3 q3

1 b 1 b 1 b

1 1 1 b b b

R R R L H H

q1 q2 q2 q3 q3 q3

R-右移；L- 右移； 右移 左移；H-不动。 不动。 左移； 不动

下一机器状态9

计算机导论 教案 二

计算机导论 - Introduction to Computers

用图灵机来进行计算代表空白 代表空白

例1: :读写头 带 控制器 程序 q1 q1 q2 q2 q3 q3 1 b 1 b 1 b 1 1 1 b b b R R R L H H

字 母 表： { 1, b } 机器状态： 机器状态： { q1, q2, q3 }

q1 q2 q2 q3 q3 q3

指令各部分的合作： 指令各部分的合作： 1)在当前机器状态下 ) 2)判断读入的符号 ) 3)写一个符号 ) 4)控制读写头动作 ) 5)设置下一机器状态 )10

计算机导论 教案 二

计算机导论 - Introduction to Computers

用图灵机来进行计算例1: :读写头 带 1 1 1 1 1 1 1 当前机器状态：q1 当前机器状态： 机器状态 程序 q1 q1 q2 q2 q3 q3 1 b 1 b 1 b 1 1 1 b b b R R R L H H q1 q2 q2 q3 q3 q3 指令各部分的合作： 指令各部分的合作： 1)在当前机器状态下 ) 2)判断读入的符号 ) 3)写一个符号 ) 4)控制读写头动作 ) 5)设置下一机器状态 )11

控制器

计算机导论 教案 二

计算机导论 - Introduction to Computers

用图灵机来进行计算例1: :读写头 带 1 1 1 1 1 1 1 当前机器状态：q1 当前机器状态： 机器状态 程序 q1 q1 q2 q2 q3 q3 1 b 1 b 1 b 1 1 1 b b b R R R L H H q1 q2 q2 q3 q3 q3 指令各部分的合作： 指令各部分的合作： …… 此处隐藏：3198字，全部文档内容请下载后查看。喜欢就下载吧 ……