Loading AI tools
De Wikipédia, l'encyclopédie libre
En informatique théorique, une machine à compteurs est un modèle de calcul. Les machines à compteurs[1] sont parfois appelées machines à registres ou machines de Minsky. Bien que les machines à compteurs soient simples à définir et à comprendre, elles ont la même puissance de calcul que les machines de Turing (voir calculabilité).
Dans sa version la plus simple une machine à compteurs est composée de deux compteurs (ou registres) et d'un programme. On note C1 le premier compteur et C2 le deuxième. Chaque compteur est un entier naturel (non borné). Le programme d'une machine à compteurs est une suite d'instructions. Les instructions possibles sont :
Dans ces instructions, i1 et i2 sont des étiquettes (ou numéro de lignes) du programme.
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.
La classe des machines avec un seul compteur est quant à elle moins puissante que la classe des automates à pile.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.