Machine à compteurs
Cet article est une ébauche concernant l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
En informatique théorique, une machine à compteurs est un modèle de calcul. Les machines à compteurs[1] sont parfois appelées machines à registres ou machines de Minsky. Bien que les machines à compteurs soient simples à définir et à comprendre, elles ont la même puissance de calcul que les machines de Turing (voir calculabilité).
Définition modifier
Dans sa version la plus simple une machine à compteurs est composée de deux compteurs (ou registres) et d'un programme. On note C1 le premier compteur et C2 le deuxième. Chaque compteur est un entier naturel (non borné). Le programme d'une machine à compteurs est une suite d'instructions. Les instructions possibles sont :
- incrémente C1 ;
- décrémente C1 ;
- incrémente C2 ;
- décrémente C2 ;
- si C1=0 alors saut vers l'instruction i1 sinon saut vers l'instruction i2 ;
- si C2=0 alors saut vers l'instruction i1 sinon saut vers l'instruction i2.
Dans ces instructions, i1 et i2 sont des étiquettes (ou numéro de lignes) du programme.
Exemple modifier
Propriétés modifier
Les machines à compteurs ont la même puissance de calcul que les machines de Turing (voir calculabilité). On peut donc simuler toute machine de Turing par une machine à deux compteurs, et inversement. En particulier, l'arrêt d'une machine à deux compteurs est indécidable. On peut aussi simuler, avec une machine à deux compteurs, une machine à 3, 4, 5 compteurs ou plus.
La classe des machines avec un seul compteur est quant à elle moins puissante que la classe des automates à pile.
Notes et références modifier
- Marvin L. Minsky, Computation : Finite and Infinite Machines, Prentice-Hall, Inc., , 317 p. (ISBN 0-13-165563-9, lire en ligne).
