转换图一个完成除2的有限状态转换系统图灵机模型图灵机的图示通用图灵机通用图灵机状态转换与计算可计算性理论现实的计算机CPU（中央处理器）负责处理信息，由控制器和运算器组成。控制器负责解释指令（“大脑”），运算器负责执行指令（“手”）。主存储器又称“内存”，用于存储计算机运行时所用的程序和数据。对应于图灵机存储带。外部存储器（外存）保存其他备用信息：备用程序与数据。一旦需要，即可装入内存使用。各种输入输出设备实现计算机与外部的信息交换。与人，与其他计算机系统或者设备。计算机的核心信息处理部件，用半导体集成电路技术制造的。一小块硅片，内部结构极复杂，包含数以百万、千万计的元件和电路。能执行一组操作：取数据，由几个数据算出一个结果（加减乘除等），送出数据等。与每个动作对应有一条指令：CPU接到指令时完成对应动作。一系列指令形成一个程序，能指挥CPU完成一系列动作。对应于通用图灵机G的控制器。问题：指令从何而来？ENIAC：程序记录在穿孔卡片上。计算机读一张卡片做一动作，速度受机械读卡机限制。冯·诺依曼看出问题症结，提出了“存储程序原理”，导致现代意义的计算机的诞生了。存储器原来只保存数据，CPU执行指令时由存储器取数据，计算结果存回存储器。冯·诺依曼方案：将程序存入存储器，由CPU自动提取指令并执行，循环地做。这样计算机就可以摆脱外界拖累，以自己的速度（电子电路的速度）自动运行了。按“存储程序原理”造出的就是“程序存储计算机”，也称为“冯·诺依曼计算机”。到目前为止，所有主流计算机都是这种计算机。CPU是个绝对服从指挥的奴仆，每时每刻都按命令（指令）行事。CPU的指令一般有几十到一二百种。而实际领域里，各方面需要应用计算机情况千差万别、错综复杂。计算机怎么能应付这些情况呢？答案：程序。通过一些不同指令的各种适当排列，人能写出的程序是无穷无尽的。考虑数字和数，汉字字和中文的作品。程序：对应于特定图灵机的编码。计算机的工作原理带来两方面的获益：CPU原理并不复杂。而最先进的CPU又极端复杂，是有史以来人制造的最复杂产品。原因：过去人常说：计算机发展经历了电子管、晶体管、集成电路和大规模集成电路四个阶段，把以这些方式构造起来的计算机分别称为第一、二、三、四代计算机。今天看，这种说法并无太大的意义。计算机器件基础的变化并不是根本性的（其意义不可低估：降低成本、减小体积等），是人们寻求合适方式制造计算机的一个短暂探索阶段，大约三十年。人们一直在研究真正新型的计算机。提出的有：光计算机、量子计算机、生物计算机等。从本质上与今天计算机不同的信息处理工具会出现吗？能取代目前流行的这种电子计算机吗？我们正拭目以待。数字化计算机存储处理信息的基础是信息的数字化，为此，我们只需：为数值确定一种计算机内部的表示方式；将一切信息用数字形式表示，进而就可以用计算机处理。信息的数字形式也称为信息的编码。“万物皆为数”在自然界不真，而在计算机里“成立”。问题：怎样数字化？怎样编码？数制计算机中用二进制数的方式表示数值。原因：理论：用两个符号的序列能有效表示复杂的信息。（一进制表达效率低，能力不够）实际：常规器件最容易表示两种不同状态。用一个器件表示一个基本的数据单位，用一系列器件的状态表示复杂的数据。将一个器件的状态看成一个二进制数字，将一系列器件的状态看成一个二进制数。二进制二进制与八、十六进制的对照二进制与十进制之间的转换二进制表示范围数的符号与负数表示有符号数的表示范围小数与实数的编码文字信息的编码中文编码与国际码其他信息的编码，转换程序的编码