可计算问题

可计算性

• 任何同一类问题都能找到对应的一组算法求解结果，而对于该类问题中的任何一个具体问题，都能按照这组规则完全机械地在有限步骤内求解出结果。

可计算函数

• 凡是可以由图灵机计算的函数，其一定能够用计算机进行计算；反之，则为不可计算函数，不能够用计算机计算。

---

图灵机

• 图灵机是对使用纸笔进行运算的过程进行的抽象，理论上模拟现代数字计算机的一切运算，是现代数字计算机的数学模型

图灵机的组成

• 一条双向都可以无限延长的被分为一个个小方格的纸带，每个方格可以有不同颜色或者书写给定字母表上的符号，也可以为空白B
• 一个在纸带上可以左右移动的读/写头
• 一个有限状态控制器，含有有限个内在状态及控制读/写头移动或读写的控制规则表

图灵机工作原理

• 在每个时刻，读/写头都要从当前纸带上读入一个方格信息
• 根据读入信息和当前控制器中内部状态查找对应规则，即查表，得到一个输出动作
• 移动读/写头或在纸带上当前位置写入符号，包括空白并确定其下一时刻的内部状态

图灵机与现代计算机

• 图灵机描述了计算的过程（算法），通用图灵机是现代通用计算机最原始模型
• 为现代计算机系统的出现奠定了理论基础
• 提出了现代计算机主要架构雏形
• 通用图灵机储存器（纸带）上记录问题数据和记录指令，图灵机按照程序步骤运行得出结果，结果也保存在储存器上。

---

冯·诺依曼体系结构

冯·诺依曼物理实现计算机的定义

• 图灵机是理论模型，冯·诺依曼计算机是图灵机的工程化实现
• 现代计算机使用冯·诺依曼体系结构，被称为冯·诺依曼计算机

冯·诺依曼原理

• 将完成某一计算任务的步骤，用机器语言程序预先送到计算机存储器中保存，然后启动机器，按照程序编排的顺序，一生一步地取出指令，控制计算机各部分的运行，并获得所需结果。
• 因此，冯·诺依曼原理也称为 "存储程序”的工作原理，它是当代计算机最基本的工作原理。根据这一原理组成的计算机称为冯·诺依曼型计算机。

冯·诺依曼体系结构的基本要点

• 计算机的指令和数据采用二进制表示和存储
• 计算机包括运算器、储存器、控制器、输入设备、输出设备五大基本部件
• 基本工作过程是在控制器的控制下，计算机自动从内存中获取指令，分析指令再执行该指令，接着获取下一条指令，周而复始地工作。
• 计算机在控制器的控制下，将数据和程序通过输入设备输入到存储器，经过运算器的运算处理，送到存储器，最后经输出设备输出
• 部件间用信号线来传递数据、指令和控制信号

总线

• 为节省并简化电路结构，采用公共通道——总线（Bus）
• 计算机总线主要有三条：
  • 数据总线DB（主要传递数据信息也传递指令和状态信息等）
  • 地址总线AB(传递存储器地址信息）
  • 控制总线CB（主要传递控制信号和时序信号）

冯·诺依曼体系结构五大基本部件

运算器 ALU

• 功能：完成对数据的算数运算、逻辑运算、逻辑判断等操作
• 是计算机处理数据、形成信息的加工厂
• 运算器又被称为算数逻辑部件

控制器

• 功能：计算机的“指挥中心”
• 控制器按人们预先编好的程序进行工作，根据程序中指令的要求，有序地向各个部件发出控制信息，控制信息存储、各种运算、信息输入输出

存储器

• 功能：用来存储数据和程序，根据功能不同，可以分为内存储器和外存储器
• 内存储器：称为内存或主存储器，用来存放正在运行的程序的指令和数据，可以直接与ALU和控制器交换信息，具有存取速度快、容量小的特点，数据易挥发
• 外存储器：称为辅助存储器，用来存放需要长期保存的信息，不能直接与存储器、控制器交换信息，需要通过内存进行交换。具有存取速度较慢、容量成本低、长期保存数据的特点

注：目前很多人会将内外储存器混淆，比如将外存储器(硬盘容量等）称为内存。

• 储存器的层次结构：为了使存储器的性能/价格比达到最优，往往采用分层的塔式结构

输入和输出设备

• 输入设备和输出设备统称为I/O设备（Input/Output）

---

计算机系统组成

• 一个完整的计算机系统由硬件系统和软件系统两大部分组成
• 硬件 Hardware：计算机系统的物质基础
• 软件 Software：发挥机器硬件功能的关键

---

软硬件的关系

• 软硬件的等价性：任何操作可以由软件来实现，也可以由硬件来实现；任何指令的执行可以由硬件完成，也可以由软件来完成。这就是计算机软件和硬件的等价性
• 硬件层始终位于软件层之下