Accueil🇫🇷Chercher

Machine à registres illimités

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

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

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

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.