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
