Machine à registres illimités

Les registres de la machine sont représentés par :

${\displaystyle {\mathcal {R}}=\{R_{i}\}_{i\geq 1}}$

et peuvent contenir des éléments de ${\displaystyle \mathbb {N} }$.

Un programme pour cette machine est représenté par toute suite de la forme :

${\displaystyle 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).

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

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

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

${\displaystyle R_{i}}$ contient ${\displaystyle d_{i}}$ si ${\displaystyle i\leq d}$ ;

${\displaystyle R_{i}}$ contient ${\displaystyle 0}$ si ${\displaystyle i>d}$.

• Calculabilité
• Machine de Turing
• Lambda calcul