Machine à registres illimités

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

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

R = { R i } i ≥ 1 {\displaystyle {\mathcal {R}}=\{R_{i}\}_{i\geq 1}}

et peuvent contenir des éléments de N {\displaystyle \mathbb {N} } .

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

P = { I i } i = 1 i = n {\displaystyle P=\{I_{i}\}_{i=1}^{i=n}}

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 { a i } i ≥ 1 {\displaystyle \{a_{i}\}_{i\geq 1}} contenues dans les registres. La configuration initiale d'un programme est celle où les premiers registres contiennent les données :

{ d } i = 1 i = d {\displaystyle \{d\}_{i=1}^{i=d}}

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

R i {\displaystyle R_{i}} contient d i {\displaystyle d_{i}} si i ≤ d {\displaystyle i\leq d}  ;
R i {\displaystyle R_{i}} contient 0 {\displaystyle 0} si i > d {\displaystyle i>d} .

Voir aussi

  • Calculabilité
  • Machine de Turing
  • Lambda calcul
  • icône décorative Portail de l’informatique