Machine à registres illimités

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\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 :

Ri contient di si i \le d ;
Ri contient 0 si i > d.

Voir aussi


Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Machine à registres illimités de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Machine a registres illimites — 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… …   Wikipédia en Français

  • 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 …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”