Máquina de Turing vs máquina de Von Neumann

Question

Fondo

La arquitectura Von-Neumann describe la computadora con programa almacenado donde se almacenan instrucciones y datos en la memoria y la máquina funciona cambiando su estado interno, es decir, una instrucción opera sobre algunos datos y modifica los datos de . Por lo tanto intrínsecamente, se mantiene en el estado del sistema.

La Turing arquitectura de la máquina funciona mediante la manipulación de símbolos en una cinta. es decir una cinta con número infinito de ranuras existe, y en cualquier punto en el tiempo, la máquina de Turing es en una ranura particular. Basado en el símbolo leído en esa ranura, la máquina puede cambiar el símbolo y pasar a una ranura diferente. Todo esto es determinista.

---

Preguntas

1. ¿Hay alguna relación entre estos dos modelos? Fue el modelo de Von Neuman basa en o inspirado en el modelo de Turing?

2. ¿Se puede decir que el modelo de Turing es un superconjunto del modelo de Von Newman?

3. ¿Tiene Programación ajuste funcional en el modelo de Turing? ¿Si es así, cómo? Asumo programación funcional no se presta muy bien al modelo de Von Neuman.

Answer 1

máquinas de Turing son conceptos teóricos inventado para explorar el dominio de los problemas computables matemáticamente y para obtener formas de describir estos cálculos.

La arquitectura Von Neumann es una arquitectura para la construcción de ordenadores reales (que implemento lo que la máquina de Turing describe teóricamente).

La programación funcional se basa en la lambda-cálculo , que es un otro método de cálculos que describen o - más precisamente - funciones computables. A pesar de que utiliza un enfoque completamente diferente, es igualmente poderosa para máquina de Turing (se dice que ser turing completa ).

Cada programa de lambda-cálculo (término) T se escribe simplemente utilizando una combinación de

• variables como x
• funciones anónimas como λx. T
• aplicaciones de función T T

A pesar de ser sin estado, esto es suficiente para cada cálculo de una computadora puede hacer. Las máquinas de Turing y términos lambda puede emular entre sí, y un ordenador de Von-Neumann puede ejecutar ambos (aparte de las restricciones técnicas, como para el almacenamiento infinita, que una máquina de Turing podría requerir).

Sin embargo, debido a su naturaleza sin estado y más abstracto, los programas funcionales podrían ser menos eficiente y menos "intuitiva" en los ordenadores Von-Neumann en comparación con programas imperativos que le siguen de estilo de binario, la memoria y la actualización .

Answer 2

En general se refiere a la arquitectura de la Von Neumann , en contraste con la arquitectura Harvard . El primero tiene código y los datos almacenados en la misma manera, mientras que el último tiene vías de memoria y de bus separado para el código y los datos. Todos los PCs de escritorio modernos son Von Neumann, la mayoría de los microcontroladores son Harvard. Ambos son ejemplos de diseños del mundo real que intentan emular una máquina de Turing teórico (lo cual es imposible, porque una verdadera máquina de Turing requiere memoria infinita).

Answer 3

modelo de Turing define las capacidades computacionales sin entrar profundamente en la implementación, nadie va a crear equipo que se parecerá a la máquina de Turing, literalmente. (Excepto los entusiastas http://www.youtube.com/watch?v=E3keLeMwfHY ).

Turing modelo no arquitectura .

Von Neuman es una guía de cómo construir computadoras. No dice nada acerca de las capacidades de cálculo. Dependiendo del conjunto de instrucciones del ordenador producido puede o no puede ser Turing completo (medios pueden resolver mismas tareas que la máquina de Turing)

La programación funcional (cálculo lambda) es otro modelo de cálculo que se Turing completa, pero no puede estar en forma nativa en la arquitectura Von Neumann.

Answer 4

No sé qué relación histórica que existe entre las máquinas de Turing y arquitecturas von Neuman. Estoy seguro, sin embargo, que von Neuman estaba al tanto de las máquinas de Turing cuando desarrolló la arquitectura de von Neuman.

En lo que a la capacidad de cálculo, sin embargo, las máquinas de Turing y máquinas de von Neuman son equivalentes. Cualquiera de ellos puede emular el otro (IIRC, emulando un programa de von Neuman en una máquina de Turing es una operación O (n ^ 6)). La programación funcional, en la forma del cálculo lambda, es también equivalente. De hecho, todos los marcos computacionales conocidos al menos tan potente como las máquinas de Turing son equivalentes:

• máquinas de Turing
• cálculo lambda (programación funcional)
• máquinas de von Neuman
• funciones recursivas parciales

No hay ninguna diferencia en el conjunto de funciones que se pueden calcular con cualquiera de estos modelos.

La programación funcional se deriva del cálculo lambda, por lo que no se correlaciona directamente a cualquiera de las máquinas de Turing o von Nemuan. Cualquiera de ellos puede ejecutar programas funcionales, hoewver, a través de la emulación. Creo que la asignación para las máquinas de Turing es probablemente más tedioso que la asignación para máquinas de von Neuman, así que mi respuesta a la tercera pregunta sería "no, de hecho, es peor."

Answer 5

El "modelo" de Turing no es un modelo arquitectónico en absoluto. Era sólo una máquina inexistente que Turing planteó la hipótesis de que sirva de vehículo para su prueba de la href="http://en.wikipedia.org/wiki/Decision_problem" rel="nofollow noreferrer"> problema de decisión .