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é]]