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 :

R i

contient

d i

si $i \le d$ ;

R i

contient

0

i > d

Voir aussi

Portail de l’informatique

Ce document provient de « Machine %C3%A0 registres illimit%C3%A9s ».

Catégorie : Calculabilité

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

Dictionnaires et Encyclopédies sur 'Academic'

Machine À Registres Illimités