Machine de Turing vs machine de Von Neuman
Background
architecture Von-Neumann décrit l'ordinateur à programme enregistré où les instructions et les données sont stockées en mémoire et où la machine fonctionne en changeant son état interne, I. e une instruction opère sur certaines données et modifie les données. Ainsi, l'état est maintenu dans le système.
machine de Turing architecture fonctionne en manipulant des symboles sur une bande. I. e une bande avec le nombre infini de fentes existe, et à n'importe quel moment dans le temps, la machine de Turing est dans une fente particulière. Basé sur le symbole lu à cette fente, la machine peut changer le symbole et se déplacer à une fente différente. Tout cela est déterministe.
Questions
- <!-Y a-t-il une relation entre ces deux modèles? Le modèle Von Neuman était-il basé sur le modèle Turing ou s'en inspirait-il?
- <!-Peut-on dire que le modèle Turing est un super-ensemble de Von Newman modèle?
la programmation fonctionnelle s'inscrit-elle dans le modèle Turing? Si oui, comment? Je suppose la programmation fonctionnelle ne se prête pas très bien au Modèle von Neuman.
5 réponses
les machines de Turing sont concepts théoriques inventé pour explorer le domaine des problèmes calculables mathématiquement et d'obtenir des façons de décrire ces calculs.
L'architecture Von-Neumann est une architecture pour construire ordinateurs (œuvre ce que la machine de Turing décrit théoriquement).
la programmation Fonctionnelle est basée sur l' lambda-calcul, qui est un autre méthode de description des calculs ou - plus précisément - calculable fonctions. Bien qu'il utilise une approche complètement différente, il est tout aussi puissant à la machine de Turing (il est dit d'être turing).
chaque programme lambda-calculus (terme) T est écrit juste en utilisant une combinaison de
- variables comme
x - fonctions anonymes comme
λx. T - applications de fonctions
T T
en dépit d'être apatride, c'est suffisant pour chaque calcul qu'un ordinateur peut faire. Les machines de Turing et les Termes lambda peuvent s'imiter, et un ordinateur Von-Neumann peut exécuter les deux (à l'exception de restrictions techniques telles que le stockage infini, qu'une machine de turing pourrait exiger).
mais en raison de leur nature apatride et plus abstraite, les programmes fonctionnels pourraient être moins efficaces et moins " intuitifs" sur les ordinateurs de Von-Neumann par rapport à programmes impératifs qui suivent son style de binaire, de mémoire et de mise à jour.
en général, on fait référence au Von Neumann l'architecture, comme en contraste avec l' Harvard l'architecture. Le premier a le code et les données stockées de la même manière, tandis que le second a la mémoire séparée et les chemins de bus pour le code et les données. Tous les ordinateurs de bureau modernes sont Von Neumann, la plupart des microcontrôleurs sont Harvard. Les deux sont des exemples de conceptions du monde réel qui tentent d'émuler une machine de Turing théorique (ce qui est impossible parce qu'une vraie machine de Turing nécessite infinie de la mémoire).
le modèle de Turing définit les capacités de calcul sans entrer profondément dans la mise en œuvre, personne ne créera jamais d'ordinateur qui ressemblera littéralement à une machine de Turing. (Sauf les enthousiastes http://www.youtube.com/watch?v=E3keLeMwfHY).
modèle de Turing n'est pas architecture.
Von Neuman guide la construction des ordinateurs. Il ne dit rien sur les capacités de calcul. En fonction des instructions, l'ordinateur produit peut ou peut ne pas être Turing complete (les moyens peuvent résoudre les mêmes tâches que Turing Machine)
la programmation fonctionnelle (lambda calculus) est un autre modèle de calcul qui est complet mais ne peut pas être nativement adapté dans l'architecture de Von Neumann.
Je ne sais pas quelle relation historique il y a entre les machines de Turing et les architectures von Neuman. Je suis sûr, cependant, que von Neuman était au courant des machines de Turing quand il a développé l'architecture von Neuman.
- Machines de Turing
- Lambda calcul (programmation fonctionnelle)
- von Neuman machines
- fonctions récursives partielles
Il n'y a pas de différence dans l'ensemble de fonctions qui peuvent être calculées avec l'un de ces modèles.
la programmation Fonctionnelle est dérivé du calcul lambda, donc il ne correspond pas directement aux machines Turing ou von Nemuan. L'un ou l'autre peut exécuter des programmes fonctionnels, hoewver, via émulation. Je pense que la cartographie des machines de Turing est probablement plus fastidieuse que celle des machines von Neuman, donc ma réponse à la troisième question serait "non, en fait, c'est pire."
le "modèle" Turing n'est pas du tout un modèle architectural. C'était juste une machine inexistante que Turing a supposé servir de véhicule pour sa preuve de la problème de décision.