Machine à compteurs
Une machine à compteurs est un modèle de calcul très rudimentaire. Les machines à compteurs[1] sont parfois appelées machines à registres ou machines de Minsky.
Définition
Dans sa version la plus simple une machine à compteurs est composée de deux compteurs (ou registres) et d'un programme. Chaque compteur est un entier naturel (non borné). Le programme est une suite d'instructions de la forme (C1 désigne le premier compteur et C2 le deuxième compteur) :
- 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
Où i1 et i2 sont des étiquettes (ou numéro de lignes) du programme.
Propriétés
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.
Une machine avec un seul compteur est quant à elle moins puissante qu'un automate à pile.
Notes et références
- Marvin L. Minsky, Computation : Finite and Infinite Machines, Prentice-Hall, Inc., , 317 p. (ISBN 0-13-165563-9, lire en ligne)