Machine à compteurs

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Une machine à compteurs est un modèle de calcul très rudimentaire. Les machines à compteurs sont parfois appelées machines à registres ou machines de Minsky.

Définition[modifier | modifier le code]

Dans sa version la plus simple une machine à compteurs est composée de deux compteurs (ou registres) et d'un programme. Chaque compteur a la valeur d'un entier naturel (non borné). Le programme est composé des seules instructions (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[modifier | modifier le code]

D'une façon surprenante 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. 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[modifier | modifier le code]


Voir aussi[modifier | modifier le code]