通用计算机是一种通用信息处理设备

•通用：计算机是一种通用信息处理设备，只要有合适的软件，它能适用于各种专门用途。•电子：是计算机硬件实现的物理基础，计算机的运行最终都通过电子电路中的电流、电位等实现。•数字化：是计算机的信息表示方式。一切信息，无论原本是数值、文字、图形、声音等，在计算机里都统一到二进制的数字化表示上。数字化是计算机的一种基本特征，是通用性的重要基础。•“计算机”：这是一种做计算的机器。全名：“通用电子数字计算机”（General-PurposeElectronicDigitalComputer）。说明许多性质：计算机基本原理计算机能做的基本动作如数的加减乘除等，极简单。但它可以按程序要求瞬间完成数以万亿计的基本动作，就可能完成一件大工作。我们看到的是这些动作的综合效果。计算机的基本结构不很复杂，能按指挥行事，做得快。更了不起的东西是程序、软件，每个程序都是特殊的，针对具体需要专门实现。“电脑”——木手——铁脚？信息处理的“普适性”：计算机远不能与人脑相比。状态与转换•一个系统S有一集可能的状态（包括一个初始状态和一组结束状态）；•S在每个时刻处于某一个状态；•当这个系统由外界接受输入时，它就可能转换到另一个状态，并可能产生一个输出；•在开始时S处于某初始状态s；•当输入用完且S达到某个结束状态时，系统的运行成功结束，否则失败结束。有限状态转换系统（一种最简单的计算模型）：转换图•S的每个状态用一个小圆圈表示；•如果S在状态s1遇到输入a时，应转到状态s2并输出b，那就画一条从表示s1的圆圈到表示s2的圆圈的弧线，并在线上标出(a,b)；一种描述有限状态转换系统的方式：(a,b)s1s2一个完成除2的有限状态转换系统•系统中s1是初始状态，s1和s2是终止状态；•它输入n个a时输出n/2个a。(a,)s1s2(a,a)自我练习：定义只读入k个abb的序列才成功结束的有限状态转换系统(k=0,1,2,…)。图灵机模型•一个有限状态转换系统，也称控制器；•一条两端无穷的包含无穷多个格子的存储带，每个格里可以存储一个符号；•一个读写头，每时刻定位于一个存储格；•每步执行，当前格的符号作为控制器输入，控制器按此符号做一次状态转换，可能将一个符号写入当前格，并可能命令读写头左移或右移一个位置。•结束：有许多等价定义方式。一个图灵机T包括：图灵机的图示设：初始时存储带上的符号序列是输入I；运行结束时带上的符号序列是输出O；图灵机T实现的计算就是T(I)=O。有限状态控制器通用图灵机•设带字符集至少包含两个符号；•存在一种编码方式c，使每个图灵机T对应于一个符号序列c(T)，T的编码。•G(c(T)^I)=O•这里c(T)^I表示将T的编码和输入I并排放在输入带上。•通用图灵机可以实现任意图灵机的功能。通用图灵机G也是一台图灵机，对任意图灵机T和输入I，如果T(I)=O，那么就有：通用图灵机•放在G的存储带上的c(T)就是指挥G如何工作的“程序”；•G的活动就是按照所给的c(T)工作，处理输入I，最终得到输出O。图灵还得到了另一个深刻结论：存在着不可计算的函数。状态转换与计算•每个计算从一个状态s0开始，输入是这个状态的一部分。•计算过程形成一个状态序列：s0,s1,s2,s3,…sn,…...•如果计算经过n步结束，所需要的输出包含于最终的状态里。•存在着不终止的计算。一个计算过程可以看作是一个状态转换序列。可计算性理论研究计算的模型和“可计算性”。计算复杂性理论研究一个或者一类计算所历经的状态转换次数。因为实际的计算步骤需要花时间。程序理论在通用计算机制（如通用图灵机）的基础上，完成具体计算只需要给出程序。程序理论研究程序的意义和程序描述的规律。现实的计算机•现实的计算机是用大规模集成电路和其他元器件构造起来的一种复杂电子设备。•它可以看成是图灵机的一种实现。•现实的计算机由一些部分构成：CPU主存储器中央处理部件输入设备输出设备键盘鼠标器……显示器打印机……辅助（外部）存储设备磁盘机、磁带机、光盘机等输入输出输入输出控制器运算器•CPU（中央处理器）负责处理信息，由控制器和运算器组成。控制器负责解释指令（“大脑”），运算器负责执行指令（“手”）。•主存储器又称“内存”，用于存储计算机运行时所用的程序和数据。对应于图灵机存储带。•外部存储器（外存）保存其他备用信息：备用程序与数据。一旦需要，即可装入内存使用。•各种输入输出设备实现计算机与外部的信息交换。与人，与其他计算机系统或者设备。计算机主要部件•计算机的核心信息处理部件，用半导体集成电路技术制造的。一小块硅片，内部结构极复杂，包含数以百万、千万计的元件和电路。•能执行一组操作：取数据，由几个数据算出一个结果（加减乘除等），送出数据等。•与每个动作对应有一条指令：CPU接到指令时完成对应动作。一系列指令形成一个程序，能指挥CPU完成一系列动作。•对应于通用图灵机G的控制器。•问题：指令从何而来？CPU与存储程序原理•ENIAC：程序记录在穿孔卡片上。计算机读一张卡片做一动作，速度受机械读卡机限制。•冯·诺依曼看出问题症结，提出了“存储程序原理”，导致现代意义的计算机的诞生了。•存储器原来只保存数据，CPU执行指令时由存储器取数据，计算结果存回存储器。•冯·诺依曼方案：将程序存入存储器，由CPU自动提取指令并执行，循环地做。•这样计算机就可以摆脱外界拖累，以自己的速度（电子电路的速度）自动运行了。•按“存储程序原理”造出的就是“程序存储计算机”，也称为“冯·诺依曼计算机”。到目前为止，所有主流计算机都是这种计算机。计算机的基本运行过程很简单，两步循环，“CPU基本循环”。CPU每次从存储器取出要求它执行的下一条指令，然后按指令完成对应动作。循环到程序执行完（遇到要求CPU停止工作的指令），或者永无休止地运行下去。取指令执行指令图CPU基本执行循环•CPU是个绝对服从指挥的奴仆，每时每刻都按命令（指令）行事。•CPU的指令一般有几十到一二百种。而实际领域里，各方面需要应用计算机情况千差万别、错综复杂。计算机怎么能应付这些情况呢？•答案：程序。通过一些不同指令的各种适当排列，人能写出的程序是无穷无尽的。•考虑数字和数，汉字字和中文的作品。•程序：对应于特定图灵机的编码。计算机的工作原理带来两方面的获益：•通用性：若干种计算机就能满足全社会的需要。可以采用大工业生产的方式，提高性能，减低成本。计算机越来越便宜，性能越来越高。•专用性：通过运行不同的程序，同一台计算机在不同时刻可以表现为不同的专用信息处理机，例如计算器、文字处理器、记事本、资料浏览检索机、帐目处理机、设计图版、游戏机等等。同一台计算机也可以同时表现为多种处理机（只要同时运行着多个不同程序）。这种通用性和专用性的完美统一，使计算机成为人类走向信息时代的过程中最锐利的武器。CPU原理并不复杂。而最先进的CPU又极端复杂，是有史以来人制造的最复杂产品。原因：1，计算机要完成的工作日趋复杂（不断有新问题），需要用更多指令才能完成。而执行指令需要时间（计算机的本质弱点）。要求更高性能的CPU。人们为提高CPU速度开发了许多巧妙技术，但这些大大增加CPU的复杂性。2，处理的数据情况越来越多。早期主要是数值，只需与算术有关的指令。今天广泛用于图形图像声音等的处理。理论上说CPU可以不改（只要写程序）。但增加些新指令能更有效处理这些特殊数据形式。这也增加了CPU的复杂性。过去人常说：计算机发展经历了电子管、晶体管、集成电路和大规模集成电路四个阶段，把以这些方式构造起来的计算机分别称为第一、二、三、四代计算机。今天看，这种说法并无太大的意义。计算机器件基础的变化并不是根本性的（其意义不可低估：降低成本、减小体积等），是人们寻求合适方式制造计算机的一个短暂探索阶段，大约三十年。人们一直在研究真正新型的计算机。提出的有：光计算机、量子计算机、生物计算机等。从本质上与今天计算机不同的信息处理工具会出现吗？能取代目前流行的这种电子计算机吗？我们正拭目以待。数字化图灵理论的一个基本点是所有信息可以用符号编码，包括图灵机本身。要用计算机处理信息，必须：•能在计算机内部存储信息、处理；这就要求确定信息在计算机内部的表示方式，•能将信息送给计算机处理，这要求能完成从外部信息到计算机内部信息的转换。计算机存储处理信息的基础是信息的数字化，为此，我们只需：•为数值确定一种计算机内部的表示方式；•将一切信息用数字形式表示，进而就可以用计算机处理。信息的数字形式也称为信息的编码。“万物皆为数”在自然界不真，而在计算机里“成立”。问题：怎样数字化？怎样编码？数制•数的进制手指与十进制，电子元件与二进制。进制形式只是数值的表示形式。•数的常见形式：二进制，八进制，十进制，十二进制，十六进制，六十进制。•任何十进制数X都可以表示为：X=kn*10n++k0*100+k-1*10-1++k-m*10-m基数为10，系数/数字ki{0,1,2,3,4,5,6,7,8,9}例：46.37(10)=4*101+6*100+3*10–1+7*10-2用进制方式表示数是人类的一项重要智力发明。计算机中用二进制数的方式表示数值。原因：•理论：用两个符号的序列能有效表示复杂的信息。（一进制表达效率低，能力不够）•实际：常规器件最容易表示两种不同状态。用一个器件表示一个基本的数据单位，用一系列器件的状态表示复杂的数据。•将一个器件的状态看成一个二进制数字，将一系列器件的状态看成一个二进制数。一个二进制位：bit（BinaryDigit），b，位，比特8位二进制数：Byte（简写B）。1KB=1024B1MB=1024KB1GB=1024MB1TB=1024GB二进制•B=kn*2n++k0*20+k-1*2-1++k-m*2-m•基数为2，系数（数字）属于{0,1}•110110(2)=1*25+1*24+0*23+1*22+1*21+0*20=32+16+0+4+2+0=54(10)运算规则：•0+0=00+1=11+0=11+1=10•0*0=00*1=11*0=01*1=1一般形式：二进制与八、十六进制的对照二进制与八进制的对照：000→0010→2100→4110→6001→1011→3101→5111→7二进制与十六进制的对照：0000→00100→41000→81100→120001→10101→51001→91101→130010→20110→61010→101110→140011→30111→71011→111111→15常用A,B,C,D,E,F作为“数字”表示10到15。二进制与十进制之间的转换二进制转换到十进制可直接使用二进制数的值计算公式完成。十进制到二进制的转换：•整数：一般采用除余法，反复整除2，收集起各次的余数。•小数：采用乘法，反复乘2，收集并去掉整数位。（注意：有限位精度的十进制小数可能无法用有限位二进制小数精确表示）•包含整数和小数部分的数分两部分计算。二进制表示范围计算机里常用固定位数方式表示整数，常见：16位：0~6553532位：0~232-1(约40亿)64位：0~264-1(约1600亿亿)近似公式：210＝1024≈103二进制数位数与整数的表示范围的关系：位数13816n范围0~10~70~2550~655350~2n-1数的符号与负数表示•有符号数取最高位表示符号，其余表示值。•为方便加减运算，计算机中的有符号数一般用模2补码表示。•对于n位的二进制数表示，正数的补码就是原来编码，负数N的补码N~满足N++N~＝2n。其中N+是|N|的补码。•求负数补码的方式：各二进制位求反，得到的数加1。负数的符号也需要编码。有符号数的表示范围用n位二进制数表示有符号整数，范围：位数816n范围-128~127-32768~32767-2n-1~2n-1-1计算机中常见的有符号整数及其表示范围：16位：-32768~3276732位：-231~231-1(约-20亿到20亿)64位：263~263-1小数与实数的编码与科学记数法对应，X=0