Machine à registres illimités

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 :

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

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

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

R_i contient d_i si i \le d ;
R_i contient 0 si i > d.

Voir aussi[modifier | modifier le code]