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 ordinateurdigital 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.
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.
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 :
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.
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. (ISBN9780444880710), 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 (DOI10.1016/s0167-739x(99)00088-6, lire en ligne).
(en) Abstract Computing Machines : A Lambda Calculus Perspective, Berlin, Heidelberg, Springer, , 384 p. (ISBN978-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. (ISBN978-3-540-27359-2, lire en ligne)
