Machine à compteurs

Machine à compteurs

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 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.

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.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Machine à compteurs de Wikipédia en français (auteurs)

Игры ⚽ Поможем решить контрольную работу

Regardez d'autres dictionnaires:

  • Machine a compteurs — Machine à compteurs 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 …   Wikipédia en Français

  • Machine À Compteurs — 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… …   Wikipédia en Français

  • Machine a sous — Machine à sous Photo d une machine à sous fabriquée en 1960. Une machine à sous est un appareil électronique ou mécanique de jeux de hasard et d argent qui ne demande aucune stratégie ou habileté particulière et dont les lots sont déterminés au… …   Wikipédia en Français

  • Machine À Sous — Photo d une machine à sous fabriquée en 1960. Une machine à sous est un appareil électronique ou mécanique de jeux de hasard et d argent qui ne demande aucune stratégie ou habileté particulière et dont les lots sont déterminés au lancement du jeu …   Wikipédia en Français

  • Machine à sous — Photo d une machine à sous fabriquée en 1960. Une machine à sous est un appareil électronique ou mécanique de jeux de hasard et d argent qui ne demande aucune stratégie ou habileté particulière. Sommaire 1 …   Wikipédia en Français

  • Machine à boule — Flipper Pour les articles homonymes, voir Flipper (homonymie). Flipper jeu de société [[Fichier:|280px]] …   Wikipédia en Français

  • Machine à boules — Flipper Pour les articles homonymes, voir Flipper (homonymie). Flipper jeu de société [[Fichier:|280px]] …   Wikipédia en Français

  • compteurs-décompteurs — ● compteur décompteur, compteurs décompteurs nom masculin Compteur d impulsions provoquant l arrêt d une machine ou fournissant un signal lorsque leur nombre atteint une valeur déterminée …   Encyclopédie Universelle

  • Calculabilite — Calculabilité La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l informatique théorique. Alors que la notion intuitive de fonction calculable est aussi vieille que les …   Wikipédia en Français

  • Calculabilité — La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est une branche de la logique mathématique et de l informatique théorique. Alors que la notion intuitive de fonction calculable est aussi vieille que les mathématiques …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”