- 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 :
et peuvent contenir des éléments de
.Un programme pour cette machine est représenté par toute suite de la forme :
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
contenues dans les registres. La configuration initiale d'un programme est celle où les premiers registres contiennent les données :et où tous les autres registres sont à zéro :
- Ri contient di si
; - Ri contient 0 si i > d.
Voir aussi
Wikimedia Foundation. 2010.
