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 en fonction 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 façon dont ils effectuent leurs opérations et quels types d'entrées ils peuvent recevoir.

Lors de la classification des machines abstraites, l'une des distinctions les plus simples concerne le nombre d'opérations qu'ils sont autorisés à effectuer àtout point donné.Une machine abstraite est appelée déterministe s'il n'y a toujours qu'une seule façon pour qu'elle continue.Il est non déterministe si plusieurs possibilités existent pour la machine dans au moins un de ses états possibles.Un Automaton Pushdown est celui qui a la capacité de manipuler sa pile d'entrées, plutôt que de simplement répondre à eux un par un dans l'ordre dans lequel ils apparaissent.

Wolfram Mathworld donne deux exemples célèbres de machines abstraites.L'un de ces exemples est Conways Game of Life, qui est une machine abstraite déterministe car une seule configuration peut émerger à partir de toute autre.Ce jeu utilise une grille dans laquelle chaque boîte, ou cellule, peut avoir la vie de l'État ou mort.L'état de toute 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 de vivre.S'il en a un, deux ou plus de trois voisins (jusqu'à huit possibles), il meurt.Une cellule morte avec exactement trois voisins prendra vie;Sinon, il restera mort.

Un autre exemple, la machine Turing, est l'une des machines abstraites les plus fondamentales et les plus fondamentales en informatique.Une machine Turing effectue des opérations sur une bande mdash; une chaîne de symboles mdash; de taille illimitée.Il contient des instructions à la fois pour modifier les symboles et pour changer le symbole sur lequel il fonctionne.Une simple machine Turing peut avoir le symbole de transformation d'instruction uniquement en 1, puis se déplacer à droite.Cette machine ne sortira rien d'autre qu'une chaîne de 1.Cette simple machine de Turing est déterministe, mais il est également possible de construire des machines de Turing non déterministes qui peuvent effectuer plusieurs opérations différentes étant donné 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 pour de vrais systèmes informatiques.La machine abstraite est au cœur de l'informatique en tant que discipline.