Machine à compteurs
Un article de Wikipédia, l'encyclopédie libre.
Une machine à compteurs est un modèle de calcul très rudimentaire. Dans sa version la plus simple une machine à compteurs est composée de 2 compteurs (ou registres) et d'un programme. Chaque compteur "contient" un entier naturel (non borné). Le programme est composé des seules instructions :
- incrémente C1 (C1 désigne ici le premier compteur)
- décrémente C1
- incrémente C2 (C2 désigne ici le deuxième compteur)
- 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.
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...
Les machines à compteurs sont parfois appelées machines à registres ou machines de Minsky. Une machine avec un seul compteur est quant à elle moins puissante qu'un automate à pile.
[modifier] voir aussi
- machine de Turing
- calculabilité
- en:counter machine article plus complet
