66

背景

冯-诺依曼架构描述了存储程序计算机,其中指令和数据存储在内存中,机器通过改变其内部状态来工作,即指令对某些数据进行操作并修改数据。所以本质上,系统中维护着状态。

图灵机架构通过操纵磁带上的符号来工作。即存在无限数量的插槽的磁带,并且在任何一个时间点,图灵机都在特定的插槽中。根据在该插槽读取的符号,机器可以更改符号并移动到不同的插槽。所有这些都是确定性的。


问题

  1. 这两个模型之间有什么关系吗?冯诺依曼模型是基于图灵模型还是受其启发?

  2. 我们可以说图灵模型是冯纽曼模型的超集吗?

  3. 函数式编程适合图灵模型吗?如果是这样,怎么做?我认为函数式编程并不适合冯诺依曼模型。

4

5 回答 5

56

图灵机是为了从数学上探索可计算问题的领域并获得描述这些计算的方法而发明的理论概念。

Von-Neumann 架构是一种用于构建实际计算机的架构(它实现了图灵机理论上描述的内容)。

函数式编程基于lambda-calculus,这是另一种描述计算或更准确地说是可计算函数的方法。虽然它使用了完全不同的方法,但它对图灵机同样强大(据说是图灵完备的)。

每个 lambda 演算程序(术语)T都是使用以下组合编写的

  • 变量如x
  • 匿名函数如λx. T
  • 功能应用T T

尽管是无状态的,但这对于计算机可以执行的每个计算来说已经足够了。图灵机和 lambda 项可以相互模拟,而冯诺依曼计算机可以同时执行两者(除了图灵机可能需要的提供无限存储等技术限制)。

但是由于它们的无状态和更抽象的性质,与遵循二进制、内存和更新风格的命令式程序相比,函数式程序在冯诺依曼计算机上的效率和“直观性”可能较低。

于 2010-05-06T15:09:14.080 回答
15

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

于 2010-05-06T16:36:55.563 回答
4

我不知道图灵机和冯诺依曼架构之间有什么历史关系。然而,我敢肯定,冯·诺依曼在开发冯·诺依曼架构时就意识到了图灵机。

然而,就计算能力而言,图灵机和冯诺依曼机是等价的。任何一个都可以模拟另一个(IIRC,在图灵机上模拟冯诺依曼程序是一个 O(n^6) 操作)。以 lambda 演算形式的函数式编程也是等价的。事实上,至少与图灵机一样强大的所有已知计算框架都是等效的:

  • 图灵机
  • Lambda 演算(函数式编程)
  • 冯诺依曼机器
  • 部分递归函数

可以使用任何这些模型计算的函数集没有区别。

函数式编程源自 lambda 演算,因此它不直接映射到图灵机或 von Nemuan 机器。但是,它们中的任何一个都可以通过仿真运行功能程序。我认为图灵机的映射可能比冯诺依曼机的映射更繁琐,所以我对第三个问题的回答是“不,实际上它更糟”。

于 2010-05-06T15:24:46.170 回答
4

图灵模型在没有深入实现的情况下定义了计算能力,没有人会创造出字面上看起来像图灵机的计算机。(爱好者除外http://www.youtube.com/watch?v=E3keLeMwfHY)。

图灵模型不是架构

冯诺依曼指导如何构建计算机。它没有说明计算能力。根据指令集,生产的计算机可能是图灵完备的,也可能不是图灵完备的(意味着可以解决与图灵机相同的任务)

函数式编程(lambda演算)是另一种图灵完备的计算模型,但不能原生地适应冯诺依曼架构。

于 2010-05-06T15:07:26.820 回答
0

图灵“模型”根本不是架构模型。这只是图灵假设的一台不存在的机器,作为他证明决策问题的工具。

于 2010-05-06T19:27:13.767 回答