图灵机与冯·诺伊曼机器

Question

背景

的冯·诺依曼体系结构描述了指令和数据被存储在存储器中所存储的程序的计算机和机的工作原理,通过改变其内部状态,即,一个指令在某些数据进行操作,并修改数据.因此,系统中存在状态.

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

---

问题

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

2. 我们可以说图灵模型是Von Newman模型的超集吗？

3. 功能编程是否适合图灵模型？如果是这样,怎么样？我认为功能编程并不适合Von Neuman模型.

Answer 1

图灵机是发明的理论概念,用于在数学上探索可计算问题的领域并获得描述这些计算的方法.

Von-Neumann架构是用于构建实际计算机的架构(其实现图灵机在理论上描述的内容).

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

每个lambda演算程序(术语)T只是使用组合

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

尽管是无状态的,但这对于计算机可以进行的每次计算都是足够的.图灵机和lambda术语可以相互模拟,Von-Neumann计算机可以同时执行(除了提供无限存储等技术限制,图灵机可能需要).

但是由于其无状态和更抽象的性质,功能性程序在Von-Neumann计算机上的效率可能更低,而且不那么"直观",而命令式程序则遵循二进制,内存和更新的风格.

Answer 2

一般来说,一个是指冯·诺依曼建筑,与哈佛建筑形成鲜明对比.前者具有以相同方式存储的代码和数据,而后者具有用于代码和数据的单独的存储器和总线路径.所有现代台式电脑都是Von Neumann,大多数微控制器都是哈佛.两者都是试图模仿理论图灵机的现实世界设计的例子(这是不可能的,因为真正的图灵机需要无限的存储器).

Answer 3

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

图灵模型不是架构。

冯·诺依曼指导如何建造计算机。它没有提到计算能力。根据指令集，生产的计算机可能是图灵完备的，也可能不是图灵完备的（意味着可以解决与图灵机相同的任务）

函数式编程（lambda 演算）是另一种图灵完备的计算模型，但本身无法适合冯·诺依曼架构。