Machine abstraite
En informatique théorique, et notamment en théorie des automates, un automate abstrait ou une machine abstraite est un modèle théorique d'un ordinateur digital et discret. Il importe peu, dans ce cadre, de savoir si cet appareil peut effectivement être construit, mais plutôt d'appréhender, par ce modèle simplifié, le fonctionnement des machines, et de les comparer entre eux.
La notion d'automate ou de machine abstraite, aussi appelé « modèle de machine »[1] joue un rôle central en informatique théorique. Ainsi, en théorie de la calculabilité et en théorie de la complexité les automates modélisent la notion centrale de calcul. Les automates jouent aussi un rôle déterminant en informatique pratique, par exemple dans la définition du langage intermédiaire durant la construction des compilateurs et plus généralement comme modèle pour la description du fonctionnement de programmes informatiques. En électronique numérique les automates servent dans les circuits de commande ou dans les systèmes hybrides. De tels automates de commande ont des applications en architecture matérielle, en réseau informatique et dans les systèmes réactifs.
Description
En général, une machine abstraite consiste en données d'entrée, en données de sortie et en un ensemble d'opérations autorisées pour transformer les entrées en sorties. On peut considérer les possibilités de transitions internes qui régissent le comportement d'une machine comme le programme informatique qui la dirige.
La machine de Turing est historiquement la première machine abstraite imaginée et c'est par conséquent la plus connue. D'autres exemples sont les types abstraits dont le comportement peut être défini par leur sémantique opérationnelle; l'illustration la plus simple est la spécification d'une pile (informatique) à l'aide d'un tableau (informatique).
Une machine abstraite peut aussi être un projet de microprocesseur pas encore réalisé, ou servant seulement de modèle. Une machine abstraite implémentée par un logiciel de simulation ou pour laquelle un interprète existe, est appelée une machine virtuelle.
Des définitions plus complexes consistent en des machines abstraites avec un jeu d'instructions complet, des registres et un modèle de mémoire. Un tel modèle fréquemment mentionné est la random access machine (ou RAM) qui permet un accès direct à la mémoire. L'accès à la mémoire externe, ou à la mémoire en cache, joue un rôle croissant dans la conception d'algorithmes, et conduit au modèle des cache-oblivious algorithm (en).
Dans certaines définitions[2], une machine abstraite est un logiciel qui permet, comme une machine, d'exécuter un programme (d'où le terme « machine »), mais pas à pas, et en omettant certains détails (d'où le qualificatif « abstraite »). Aux deux extrêmes, on trouve un langage intermédiaire de compilation avec une sémantique opérationnelle de bas niveau, ou au contraire la conception d’un ordinateur encore en projet. Pris dans ce sens, tout langage de programmation porte en lui un modèle de calcul qui décrit comment l’exécution d'un programme doit être réalisée, et ce modèle est une machine abstraite.
Le terme « machine virtuelle » peut être utilisé[2] pour l'implémentation de machines abstraites, un peu comme un programme peut être vu comme une implémentation d'un algorithme. Dans les systèmes d'exploitation, plusieurs niveaux d'abstraction sont appelés « virtuels ».
Théorie des machines abstraites
Dans la théorie, on distingue les accepteurs des transducteurs. Les premiers jugent de la pertinence de la donnée, et répondent par « oui » ou par « non » selon que la donnée est correcte ou non. Les deuxièmes transforment les données d'entrée en données de sortie; ils sont plus proches des calculateurs.
En théorie toujours, on distingue des machines déterministes des machines non déterministes ; si les premières ont toujours un comportement déterminé par la donnée et par la configuration dans laquelle elles se trouvent, les deuxièmes peuvent avoir au contraire le choix entre plusieurs actions dans certaines situations. Des variations de ces automates non déterministes sont les automates pondérés, parmi lesquels les automates stochastiques, qui mesurent le degré de non-déterminisme respectivement le considèrent comme probabilité. On distingue aussi les machines séquentielles et les machines parallèles.
La hiérarchie de Chomsky introduit une première classification, en définissant les concepts de :
Cette hiérarchie a été depuis raffinée et ramifiée, par exemple par extension à des structures autres que les mots, par des automates sur les arbres, sur les graphes ou sur des structures de calcul (comme les λ-termes). D'autres variations concernent le support de l’information, comme :
- machines de Turing à plusieurs bandes, ou opérant en deux dimensions ;
- automates cellulaires
- réseaux de neurones artificiels
- réseaux de Petri
- automates sur les mots infinis
Les modèles de machine équivalentes aux machines de Turing ont eux-mêmes été comparés quant à leur efficacité. La « thèse d'invariance », dans la formulation de van Emde Boas[1] stipule que deux modèles de machine « raisonnables » peuvent être simulés l'un par l'autre dans un temps polynomialement borné et avec une proportion constante de place additionnelle. Concernant les modèles parallèles, la « thèse du calcul parallèle »[1] stipule que tout ce qui peut être résolu en espace polynomial sur une machine séquentielle raisonnable peut être résolu en temps polynomial sur une machine parallèle raisonnable, et vice-versa.
Autres machines abstraites
- Machine à états abstraits
- Machine de Gandy[3]
- Automate fini
- Specification and Description Language
- Warren's Abstract Machine
- MMIX
- MikroSim (en)
- Ten15 (en)
- TenDRA Distribution Format (en)
- Parallel random access machine
Machines liées au lambda-calcul
Notes et références
Bibliographie
- Peter van Emde Boas, « Machine Models and Simulations », dans Jan van Leeuwen (éditeur), Handbook of Theoretical Computer Science. Volume A: Algorithms and Complexity, The MIT PRESS/Elsevier, , 1003 p. (ISBN 9780444880710), p. 1–66.
- Stephan Diehl, Pieter Hartel et Peter Sestoft, « Abstract machines for programming language implementation », Future Generation Computer Systems, vol. 16, no 7,‎ , p. 739-751 (DOI 10.1016/s0167-739x(99)00088-6, lire en ligne).
- (en) Abstract Computing Machines : A Lambda Calculus Perspective, Berlin, Heidelberg, Springer, , 384 p. (ISBN 978-3-540-27359-2, lire en ligne)
- (en) Werner Kluge, Abstract Computing Machines : A Lambda Calculus Perspective, Berlin, Heidelberg, Springer Science & Business Media, , 384 p. (ISBN 978-3-540-27359-2, lire en ligne)
- David B. Skillicorn, Foundations of Parallel Programming, Cambridge University Press, , 212 p. (ISBN 978-0-521-01856-2, lire en ligne).