computer-science - turing - von neumann informatica
Máquina de Turing vs máquina de Von Neuman (5)
El "modelo" de Turing no es en absoluto un modelo arquitectónico. Era solo una máquina inexistente que Turing supuso que serviría como el vehículo para su prueba del problema de decisión .
Fondo
La arquitectura de Von-Neumann describe la computadora de programa almacenado donde las instrucciones y los datos se almacenan 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. Así que inherentemente, hay estado mantenido en el sistema.
La arquitectura de la máquina de Turing funciona mediante la manipulación de símbolos en una cinta. es decir, existe una cinta con un número infinito de ranuras y, en cualquier momento, la máquina de Turing se encuentra en una ranura en particular. Según el símbolo leído en esa ranura, la máquina puede cambiar el símbolo y moverse a una ranura diferente. Todo esto es determinista.
Preguntas
¿Hay alguna relación entre estos dos modelos? ¿Se basó o inspiró el modelo de Von Neuman en el modelo de Turing?
¿Podemos decir que el modelo de Turing es un superconjunto del modelo de Von Newman?
¿La Programación funcional encaja en el modelo de Turing? ¿Si es así, cómo? Supongo que la programación funcional no se adapta bien al modelo de Von Neuman.
El modelo de Turing define las capacidades computacionales sin profundizar en la implementación, nadie creará una computadora que se parezca literalmente a la Máquina de Turing. (Excepto entusiastas http://www.youtube.com/watch?v=E3keLeMwfHY ).
El modelo de Turing no es la arquitectura .
Von Neuman es una guía de cómo construir computadoras. No dice nada sobre las capacidades de cómputo. Dependiendo del conjunto de instrucciones, la computadora producida puede o no puede ser Turing completa (los medios pueden resolver las mismas tareas que Turing Machine)
La programación funcional (cálculo lambda) es otro modelo computacional que se completa con Turing pero no se puede adaptar de forma nativa a la arquitectura de Von Neumann.
En general, se refiere a la arquitectura de Von Neumann , en contraste con la arquitectura de Harvard . El primero tiene el código y los datos almacenados de la misma manera, mientras que el segundo tiene memoria y rutas de bus separadas para el código y los datos. Todas las PC de escritorio modernas 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órica (lo cual es imposible porque una máquina de Turing verdadera requiere memoria infinita).
Las máquinas de Turing son conceptos teóricos inventados para explorar matemáticamente el dominio de problemas computables y para obtener formas de describir estos cálculos.
La arquitectura de Von-Neumann es una arquitectura para construir computadoras reales (que implementan lo que la máquina de Turing describe teóricamente).
La programación funcional se basa en el lambda-calculus , que es otro método para describir los cálculos o, más precisamente, las funciones computables. Aunque utiliza un enfoque completamente diferente, es igualmente poderoso para la máquina de Turing (se dice que se está completando ).
Cada programa de lambda-cálculo (término) T se escribe usando solo una combinación de
- variables como
x - Funciones anónimas como
λx. Tλx. T - aplicaciones de función
TT
A pesar de ser apátrida, esto es sufficient para cada cálculo que puede hacer una computadora. Las máquinas de Turing y los términos lambda pueden emularse entre sí, y una computadora Von-Neumann puede ejecutar ambos (además de las restricciones técnicas, como proporcionar un almacenamiento infinito, que una máquina de Turing podría requerir).
Pero debido a su naturaleza sin estado y más abstracta, los programas funcionales pueden ser menos eficientes y menos "intuitivos" en las computadoras Von-Neumann en comparación con los programas imperativos que siguen su estilo de binario, memoria y actualización.
No sé qué relación histórica hay entre las máquinas de Turing y las arquitecturas de von Neuman. Sin embargo, estoy seguro de que von Neuman estaba al tanto de las máquinas de Turing cuando desarrolló la arquitectura de von Neuman.
En cuanto a la capacidad computacional, sin embargo, las máquinas de Turing y las de von Neuman son equivalentes. Cualquiera de los dos puede emular al 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 forma de cálculo lambda, también es equivalente. De hecho, todos los marcos computacionales conocidos al menos tan potentes como las máquinas de Turing son equivalentes:
- Maquinas de turing
- Cálculo lambda (programación funcional)
- máquinas de von Neuman
- Funciones recursivas parciales.
No hay 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 asigna directamente a 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 el mapeo de las máquinas de Turing es probablemente más tedioso que el mapeo de las máquinas de von Neuman, por lo que mi respuesta a la tercera pregunta sería "no, de hecho es peor".