图灵机与冯·诺伊曼机的区别

Question

图灵机与冯·诺伊曼机的区别

computer-sciencecpu-architectureturing-machinesvon-neumann

69

背景

Von-Neumann结构描述了存储程序计算机，其中指令和数据存储在内存中，计算机通过改变其内部状态来工作，即指令对某些数据进行操作并修改数据。因此，系统中固有地保持着状态。

Turing机结构通过操作纸带上的符号来工作。即存在具有无限槽位的纸带，并且在任何时候，Turing机都在特定的槽中。基于读取该槽中的符号，机器可以更改符号并移动到其他槽中。所有这些都是确定性的。

问题

这两种模型之间是否有关系？ Von Neuman模型是基于还是启发自Turing模型？
我们可以说Turing模型是Von Newman模型的超集吗？
函数式编程是否适用于Turing模型？如果是，如何适用？我认为函数式编程不太适用于Von Neuman模型。

- Santhosh

6个回答

17

通常我们提到冯·诺伊曼体系结构，与之相对比的是哈佛体系结构。前者将代码和数据以相同方式存储，而后者则为代码和数据分别设置独立的内存和总线路径。所有现代台式电脑都是冯·诺伊曼，大多数微控制器都是哈佛结构。这两种结构是现实世界中的设计示例，旨在模拟理论上的图灵机（由于真正的图灵机需要无限内存，因此这是不可能的）。

- rmeador

1

感谢您提出哈佛架构与图灵机的对比。 - Santhosh

5

或许这只是一个打错字，但我并没有提出这样的对比。正如我在我的回答中所说的，冯诺伊曼和哈佛结构都是图灵机。它们之间的对比是它们的内存布局。 - rmeador

5

图灵模型定义了计算能力，而不深入实现细节。除了一些热衷者外（http://www.youtube.com/watch?v=E3keLeMwfHY），没有人会真的创建出类似图灵机的电脑。

图灵模型并非“架构”。

冯·诺依曼则是指导如何构建计算机的方法。它并未涉及计算能力。根据指令集，制造出的电脑可能是图灵完备的（能够解决与图灵机相同的问题），也可能不是。

函数式编程（lambda演算）是另一个计算模型，它是图灵完备的，但不能直接适用于冯·诺依曼架构。

- Andrey

4

我不知道图灵机和冯·诺伊曼体系结构之间有什么历史关系。但是我确信，当冯·诺伊曼开发冯·诺伊曼架构时，他知道图灵机。

然而，就计算能力而言，图灵机和冯·诺伊曼机器是等效的。任何一个都可以模拟另一个（如果我没记错，在图灵机上模拟冯·诺伊曼程序是一个O(n^6)的操作）。λ演算形式的函数式编程也是等效的。实际上，所有已知的计算框架至少与图灵机一样强大，并且是等效的：

- 图灵机 - λ演算（函数式编程） - 冯·诺伊曼机器 - 部分递归函数

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

函数式编程源自λ演算，因此它不能直接映射到图灵或冯·诺伊曼机器。但是，通过模拟，它们都可以运行函数式程序。我认为，对于图灵机来说，映射可能更繁琐，而对于冯·诺伊曼机器来说，映射可能更简单，因此我的答案是“不，实际上更糟”。

- Michael Ekstrand

1

O(n^6)？针对什么n？运行时间不会取决于程序的细节吗？ - rakslice

0

Turing“模型”根本不是一种架构模型。它只是图灵假设的一台不存在的机器，用于证明决策问题。

- Dinah

0

理解它们之间的区别的简单方法是...冯·诺伊曼将图灵的α机器概念扩展到支持在共享、集中、不受保护的内存中运行多个算法。这导致了远离阿隆佐·邱奇的λ演算和函数式编程，转向精简指令集（RISC）指令、危险共享静态寻址、独裁超级用户、中央操作系统、虚拟内存、虚拟机和无尽的网络犯罪。

相反，图灵机旨在成为λ演算的λ引擎，创建虚拟函数（而不是虚拟机）。请记住，艾伦·图灵是阿隆佐·邱奇在1936年和1937年的博士生。他们打算使用阿隆佐·邱奇的符号化、功能性模块化来封装和保护单一算法，作为实现他们的Church-Turing论文的简单二进制计算机。

λ机器码通过使用不可变名称、面向对象程序和基于能力的寻址来强制执行函数式编程，从而创建一个更好、更强大的计算机。当以这种方式封装二进制计算机（无论是图灵的还是冯·诺伊曼的）时，创建了一个具有六个额外Church指令的Church-Turing机器，以编程方式控制应用程序命名空间、执行线程、安全调用和返回到子例程抽象、编程函数和二进制对象，如Civilizing Cyberspace: The Fight For Digital Democracy所述。

- Kenneth J Hamer-Hodges

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dario · Accepted Answer

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

冯·诺依曼体系结构是用于构建实际计算机的架构（它们实现了图灵机在理论上描述的内容）。

函数式编程基于lambda演算，这是另一种描述计算或更准确地说是可计算函数的方法。虽然它使用完全不同的方法，但与图灵机同样强大（它被认为是turing complete）。

每个lambda演算程序（术语）T都只是使用以下组合编写的：

像x这样的变量
匿名函数，如λx.T
函数应用TT

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

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