图灵机模型形象地模拟了人类进行计算的过程。假如我们希望计算任意两个3位数的加法:139+919。我们需要一张足够大的草稿纸以及一支可以在纸上不停地涂写的笔。之后,我们需要从个位到百位一位一位地按照10以内的加法规则完成加法。我们还需要考虑进位,例如9+9=18,这个1就是加在十位上。我们是通过在草稿纸上记下适当的标记来完成这种进位记忆的。最后,我们把计算的结果输出到了纸上。
图灵机把所有这些过程都模型化了:草稿纸被模型化为一条无限长的纸带,笔被模型化为一个读写头(中间那个大盒 子),固定的10以内的运算法则模型化为输入给读写头的程序,对于进位的记忆则被模型化为读写头的内部状态(盒子上的方块,由程序对盒子进行控制)。于是,设计好纸带上的初始信息,以及读写头的当前内部状态和程序规则,图灵机就可以运行起来了。它在每一时刻读入一格纸带信息,并根据当前的内部状态,查找相应的程序,从而给出下一时刻的内部状态并输出信息到纸带上。上图的整体装置就是根据程序的命令及其内部状态进行磁带的读写和移动。其工作原理是:从读写头在纸带上读出一个方格的信息,并且根据它当前的内部状态开始在程序表中查找对应的指令,然后得出一个输出动作,也就是往纸带上写信息,还是移动读写头到下一个方格。程序也会告诉它下一时刻内部状态转换到哪一个。
具体的程序就是一个列表,也叫做规则表或指令表,如下图所示:
当前内部状态(S) | 输入数值(i) | 输出动作(o) | 下一时刻的内部状态(s') |
B | 1 | 前移 | C |
A | 0 | 往纸带上写1 | B |
C | 0 | 后移 | A |
… | … | … | … |
因此,图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表,就可以确定它下一时刻的内部状态和输出动作了。只要修改它的程序(也就是上面的规则表),它就可以为你做计算机能够完成的任何工作。因此可以说,图灵机就是一个简单的计算机模型。
图灵机模型信息处理的本质:输入集合、输出集合、内部状态、固定的程序。任何图灵机都可以把输入、输出信息进行编码,任何一个变换也可以最终分解为对01编码的变换,而对01编码的所有计算都可分解成三种基本的布尔运算(与、或、非),所以,用布尔电路可以组合出任意的图灵机。
冯·诺依曼机与图灵机是一脉相承的,但最大的不同在于,冯·诺依曼的读写头不再需要一格一格地读写纸带,而是根据指定的地址,随机地跳到相应的位置完成读写。这也就是我们今天所说的随机访问存储器(Random Access Memory, RAM)的前身。
为了实现过程的自动化,不能让机器操作一步告知一个指令和需要的数据,而是将整个过程的全部指令和数据全部组织好,存储起来,由机器自动读取指令,存取数据,自动完成整个过程的全部指令。这就是冯·诺依曼体系的自动存储结构。