Machine à registres illimités
911315
26246314
2008-02-14T19:51:34Z
DumZiBoT
280295
Robot : Passage au modèle {{ébauche}} : {{ébauche|informatique}} ; changement de type cosmétique
{{ébauche|informatique}}
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 [[Machine de Turing|machines de Turing]] et le [[lambda-calcul]]. Une URM est [[turing-complet|Turing-complète]].
== Notations ==
Les [[registre (informatique)|registres]] de la machine sont représentés par :
:<math>\mathcal{R} = \{ R_i \}_{i \geq 1}</math>
et peuvent contenir des éléments de <math>\mathbb{N}</math>.
Un programme pour cette machine est représenté par toute suite de la forme :
:<math>P = \{ I_i \}_{i=1}^{i=n} </math>
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 <math>\{ a_{i} \}_{i\geq1}</math> contenues dans les registres. La configuration initiale d'un programme est celle où les premiers registres contiennent les données :
:<math>\{ d \}^{i=d}_{i=1}</math>
et où tous les autres registres sont à zéro :
:<math>R_i</math> contient <math>d_i</math> si <math>i \le d</math> ;
:<math>R_i</math> contient <math>0</math> si <math>i > d</math>.
== Voir aussi ==
* [[Calculabilité]]
* [[Machine de Turing]]
* [[Lambda calcul]]
{{Portail informatique}}
[[Catégorie:Calculabilité]]