Machine à registres illimités

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant l’informatique
Cet article est une ébauche concernant l’informatique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

En informatique, une machine à registres illimités ou URM (de l'anglais : Unlimited Register Machine) est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tout comme les machines de Turing et le lambda-calcul. Une URM est Turing-complète.

Notations[modifier | modifier le code]

Les registres de la machine sont représentés par :

et peuvent contenir des éléments de .

Un programme pour cette machine est représenté par toute suite de la forme :

qui contient une suite finie d'instructions.

Une instruction peut être :

  • une remise à zéro du i-ème registre : Z(i) ;
  • l'incrémentation du i-ème registre : S(i) ;
  • le transfert du contenu du i-ème registre dans le j-ème registre : T(i, j) ;
  • un saut conditionnel à la k-ème instruction lorsque les i-ème et j-ème registres sont égaux : J(i, j, k).

Fonctionnement[modifier | modifier le code]

Une URM exécute les instructions d'un programme séquentiellement, sauf lorsqu'elle rencontre une instruction de saut.

La configuration ou l'état d'un programme est l'ensemble des valeurs contenues dans les registres. La configuration initiale d'un programme est celle où les premiers registres contiennent les données :

et où tous les autres registres sont à zéro :

contient si  ;
contient si .

Voir aussi[modifier | modifier le code]