Machine à compteurs

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique théorique
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.

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[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 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[modifier | modifier le code]

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[modifier | modifier le code]

  1. Marvin L. Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., (ISBN 0131655639, lire en ligne)

Voir aussi[modifier | modifier le code]