图灵机与冯诺依曼结构计算机

Answer 1

图灵机（英语：Turing machine），又称确定型图灵机，是英国数学家艾伦·图灵于1936年提出的一种将人的计算行为抽象掉的数学逻辑机，其更抽象的意义为一种计算模型。

图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程，他把这样的过程看作下列两种简单的动作：

为了模拟人的这种运算过程，图灵构造出一台假想的机器，该机器由以下几个部分组成：

一条无限长的纸带TAPE。纸带被划分为一个接一个的小格子，每个格子上包含一个来自有限字母表的符号，字母表中有一个特殊的符号表示空白。纸带上的格子从左到右依次被编号为0, 1, 2, ...，纸带的右端可以无限伸展。
一个读写头HEAD。该读写头可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。

一套控制规则TABLE。它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态，按照以下顺序告知图灵机命令：

一个状态寄存器。它用来保存图灵机当前所处的状态。图灵机的所有可能状态的数目是有限的，并且有一个特殊的状态，称为停机状态。参见停机问题。

注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过程。

图灵机看起来简单，但是功能非常强大。它把计算思维用形式化语言描述，从而模拟人类的计算方法，为设计计算机提供了理论基础。

冯·诺依曼（John von Neumann，1903年12月28日-1957年2月8日），美籍匈牙利数学家、计算机科学家、物理学家，是20世纪最重要的数学家之一。 冯·诺依曼是布达佩斯大学数学博士，在现代计算机、博弈论、核武器和生化武器等领域内的科学全才之一，被后人称为“现代计算机之父”、“博弈论之父”。

数学家冯·诺依曼提出了计算机制造的三个基本原则，即采用二进制逻辑、程序存储执行以及计算机由五个部分组成（运算器、控制器、存储器、输入设备、输出设备），这套理论被称为冯·诺依曼体系结构。

先来看看计算机各个功能部件的作用。

计算机使用二进制逻辑有很多好处，利于数据的传输、储存、表示。例如用高电平表示1，用低电平表示0。由此可以建立数字逻辑系统，用简单的物理元件组合表示更复杂的运算和处理。

程序控制是计算机体系结构里的一个核心思想。先把指令和数据都存放在存储器中，然后根据指令的地址取出指令，经过译码产生不同的控制信号，实现对计算机的控制，完成指令的功能。

把存储器里的信息分为指令和数据是很有必要的。指令就是指挥机器工作的指示和命令，程序就是一系列按一定顺序排列的指令，执行程序的过程就是计算机的工作过程。数据是被操作的内容。

计算机可以从时间和空间两方面来区分指令和数据。在时间上，取指周期从内存中取出的是指令，而执行周期从内存取出或往内存中写入的是数据；在空间上，从内存中取出指令送控制器，而执行周期从内存从取的数据送运算器、往内存写入的数据也是来自于运算器。

把图灵机和冯诺依曼计算机做个对比：
图灵机的纸带 ≈ 存储器，
读写头 ≈ MAR MDR 寄存器，
控制规则 ≈ 运算器+控制器，
状态 ≈ 时序+各种寄存器。

个人认为，图灵机是对于人类计算思维的理论模型，冯诺依曼计算机是通用图灵机的工程化实现。