Qu'est-ce qu'une machine abstraite?
Les machines abstraites, également appelées automates, sont un élément de l'informatique théorique. Une machine abstraite ressemble à une fonction en mathématiques. Il reçoit des entrées et produit des sorties selon des règles spécifiées. Les machines abstraites diffèrent des machines plus littérales car elles sont supposées fonctionner parfaitement et indépendamment du matériel. Ils sont subdivisés en types sur la base de caractéristiques telles que la manière dont ils effectuent leurs opérations et les types d'intrants qu'ils peuvent recevoir.
Lors de la classification des machines abstraites, l'une des distinctions les plus simples concerne le nombre d'opérations qu'elles sont autorisées à effectuer à un moment donné. Une machine abstraite est dite déterministe s’il n’ya toujours qu’une façon de procéder. Il n’est pas déterministe s’il existe plusieurs possibilités pour la machine dans au moins un de ses états possibles. Un automate "pushdown" est un automate qui a la capacité de manipuler sa pile d'entrées, plutôt que de simplement y répondre une par une dans l'ordre dans lequel elles apparaissent.
Wolfram MathWorld donne deux exemples célèbres de machines abstraites. L'un de ces exemples est le jeu de la vie de Conway, qui est une machine abstraite déterministe car une seule configuration peut émerger d'une autre. Ce jeu utilise une grille dans laquelle chaque case ou cellule peut avoir l'état "vivant" ou "mort". L'état de l'ensemble de la grille est déterminé sur la base de l'état précédent. Si une cellule vivante touche exactement deux ou trois autres cellules vivantes, elle continue à vivre. S'il a un, deux ou plus de trois voisins (jusqu'à huit possibles), il meurt. Une cellule morte avec exactement trois voisins va s'animer; sinon, il restera mort.
Un autre exemple, la machine de Turing, est l’une des machines abstraites les plus fondamentales et les plus fondamentales de l’informatique. Une machine Turing effectue des opérations sur une bande - une chaîne de symboles - de taille illimitée. Il contient des instructions pour changer les symboles et pour changer le symbole sur lequel il fonctionne. Une simple machine de Turing pourrait n'avoir que l'instruction "transformer le symbole en 1, puis aller à droite". Cette machine ne produirait qu'une chaîne de 1. Cette machine de Turing simple est déterministe, mais il est également possible de construire des machines de Turing non déterministes pouvant effectuer plusieurs opérations différentes avec la même entrée.
Ces machines abstraites peuvent servir à plusieurs fins. Ils peuvent être des jouets théoriques amusants, mais ils peuvent également servir de modèles à de véritables systèmes informatiques. La machine abstraite est au cœur de l'informatique en tant que discipline.