图灵机与冯·纽曼机

Question

背景

Von-Neumann体系结构描述了存储程序计算机，其中指令和数据存储在内存中，机器通过改变内部状态工作，即指令对某些数据进行操作并修改数据。因此，从本质上说，系统中存在着状态。

图灵机体系结构通过操纵磁带上的符号来工作。也就是说，有无限多插槽的磁带存在，在任何一个时间点，图灵机都在一个特定的插槽中。根据在该插槽处读取的符号，机器可以更改符号并移动到另一个插槽。所有这些都是决定性的。

问题

1. 这两种模式之间有什么关系吗？Von Neuman模型是建立在图灵模型的基础上还是受到图灵模型的启发？
2. 我们可以说图灵模型是冯·纽曼模型的超集吗？
3. 函数编程是否适合图灵模型？如果是这样的话，是怎么做的？我假设函数式编程不能很好地帮助Von模型。

Answer 1

图灵机是用来从数学上探索可计算问题的领域和获得描述这些计算的方法的理论概念。

Von体系结构是一种用于构建实际计算机的体系结构(它实现了图灵机理论上描述的功能)。

函数式编程基于兰伯达微积分，这是另一种描述计算或更精确地描述可计算函数的方法。虽然它使用了完全不同的方法，但它与图灵机器(据说是图灵完整的)一样强大。

每个lambda微积分程序(术语) T都是使用以下两个组合编写的

• 像x这样的变量
• 匿名函数(如λx. T )
• 功能应用T T

尽管是无状态的，但对于计算机所能做的每一次计算，这都是足够了。图灵机器和lambda术语可以相互模仿，Von-Neumann计算机可以两者执行(除了提供无限存储(图灵机可能需要的)等技术限制外)。

但由于其无状态和更抽象的性质，功能程序在Von-Neumann计算机上可能效率较低，“直观”较低，与遵循其二进制、内存和更新风格的命令式程序相比。

Answer 2

通常，一个是指冯·诺依曼体系结构，与哈佛大学体系结构形成对比。前者以相同的方式存储代码和数据，而后者为代码和数据提供独立的内存和总线路径。所有现代台式电脑都是冯·诺依曼，大多数微控制器都是哈佛大学的。这两者都是试图模仿理论图灵机的现实世界设计的例子(这是不可能的，因为真正的图灵机需要无限的内存)。

Answer 3

图灵模型定义了计算能力而不深入实现，没有人会创建看起来像图灵机的计算机。(除了狂热者http://www.youtube.com/watch?v=E3keLeMwfHY )。

图灵模型不是体系结构。

冯·纽曼指导如何建造计算机。它没有提到计算能力。根据指令集的不同，产生的计算机可能是完全的，也可能不是完全的(方法可以解决与图灵机相同的任务)

函数式编程(lambda演算)是另一种计算模型，它是图灵完整的，但不能完全适应冯·诺依曼体系结构。