title: Machine à registres illimités
text: # 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 :
  
      ${\mathcal {R}}=\{R_{i}\}_{i\geq 1}$
  
  et peuvent contenir des éléments de $\mathbb {N}$.
  
  Un programme pour cette machine est représenté par toute suite de la forme :
  
      $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\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}$
  
  et où tous les autres registres sont à zéro :
  
      $R_{i}$ contient $d_{i}$ si $i\leq d$ ;
      $R_{i}$ contient $0$ si $i>d$.
  