1、第二章 计算机科学的基本概念和基本知识2.1 计算模型与二进制数学不等于计算，但数学确实起源于对计算的研究。数学、计算模型（计算方法、数学机器）、形式化与形式化方法我们说，形式是事物的内容存在的外在方式、形状和结构的总和。所谓形式化是将事物的内容与形式相分离，用事物的某种形式来表示事物。形式化方法是在对事物描述形式化的基础上，通过研究事物的形式变化规律来研究事物变化规律的全体方法的总称。1.1.1 计算模型与图灵机所谓计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统，而算法是对计算过程步骤（或状态的一种刻划，是计算方法的一种能行实现方式。在计算机科学中，我们通常所说的计算模型，并不是指
2、在其静态或动态数学描述基础上建立求解某一 (类 )问题计算方法的数学模型，而是指具有状态转换特征，能够对所处理的对象的数据或信息进行表示、加工、变换、输出的数学机器。由于观察计算的角度不同，产生了各种不同的计算模型。递归函数、 Turing机等 (1) s(x) x 1 （ 后继函数）；(2) o(x) 0 （ 零函数）；(3) Uj(n)(x1， x2， ， xn) xj （ 射影函数）。由初始函数和有限次使用算子可以构造各种复杂的递归函数，或者可计算函数。图灵机的示意图控制器的命令可表示为：（状态，符号） （写符号，移动，状态）； 控制器 一旦图灵机在运行中进入了一个状态，而且这个状态是一
3、个结束状态，那么，图灵机就停机，计算任务宣告完成，此时带上的内容就是计算的输出结果。例 1 M的字母表 A 0， 1， b， b表示空格。状态集 Qq1， q2， q3， 其中，指定 q1是开始状态， q3是终止状态。M的程序（控制器的命令）如下：q1 0 1 R q1；q1 1 0 R q1；q1 b b R q2；q2 b b L q3；q2 0 0 H q1；q2 1 1 H q1；对图灵机的工作过程从不同的角度考察，可以给予不同的解释。第一 ，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，否则为不接受。例 2 一台图灵
4、机可以设计成识别下面的序列：1000110, 10011101, 010101011。第二 ，把图灵机看作生成器，对给定的输入集合，考察输出集合，并研究输入输出集合性质之间的关系，这就研究了图灵机的生成能力。例 3 设一台图灵机的输入集合为 In 1n0nnN ， 可设计一台图灵机，对给定的输入集合 In， 得到输出集合Out 0n1nnN 。 其中， N是全体自然数的集合。第三 ，把图灵机看作计算器，相当于一个函数。图灵机的输入是函数的自变量的值，图灵机的输出是函数的值。例 4 图灵机可以计算下列函数：(1) s(x) x 1；(2) o(x) 0；(3) A(0， y) y 1，A(x 1
5、， 0) A(x， 1)，A(x 1， y 1) A(x， A(x 1， y)。第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提一下，第三个函数叫做阿克曼函数，它是阿克曼（ W.Ackermann） 在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理论中具有重要价值。事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。 沿着这样一种思路，图灵机被证明具有很强的计算能力，它与 30年代发展的递归函数论（一种能行可计算性理论）中一类最一般的可计算函数（部分递归函数或部分可计算函数）在计算表达能力上是等价的。然而，
6、图灵机简洁的构造和运行原理隐含了存储程序的原始思想，深刻地揭示了现代通用电子数字计算机最核心的内容。 图灵奖2.1.2 二进制也许是图灵机读写带上只出现两个符号启发了研究者，在当时的技术条件下，从便于元器件的设计和制造考虑，计算机的研制很自然地选择了二进制。后来的实践也证明了这种选择具有极大的优点。十进制数的表示 例如， 1997.630这个数可以写成：1997.630 110 3 910 2 910 1 710 0 610 -1 310 -2 010 -3一般地，任何一个十进制数 S都可以表示为：S knkn-1 k 0. k -m kn10 n kn-110 n-1 k010 0 k-m1
7、0 -m-m ki10 ii n其中， 10称为十进制的基数 ,ki0,1,2,3,4,5,6,7,8,9， m， n为正整数。小数点的位置不言自明。二进制和十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。二进制表示数的符号只有两个，即 0和 1，其数值与十进制中的 0和 1相同。此外，与十进制不同之处在于二进制数是逢二进一。例如，十进制数与二进制数中的一些可作如下对应：十进制 二进制(0) (0)(1) (1)(2) (10)(3) (11)(4) (100)(5) (101) (9) (1001)(10) (1010) 一般地，任何一个二进制数 S都可以表示为：S knkn-1 k 0. k -m kn2 n kn-12 n-1 k02 0 k-m2 -m-m ki2 ii n 其中， 2称为二进制的基数， ki0,1,m,n 为正整数。进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。 二进制的运算规则比十进制的运算规则简单得多。 只要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。 计算机的理论基础是逻辑和代数。当二进制与同样只使用 “ 真 ” 和 “ 假 ” 两个值的逻辑代数建立了联系后，这就为计算机的逻辑设计提供了便利的工具。
