Définition 3Calculabilité

Machines à registres

Énoncé

Une machine à registres dispose de registres $R_0, R_1, R_2, \dots$ , contenant chacun un entier. Un programme est une suite finie $I_0, \dots, I_{L-1}$ d'instructions de deux sortes :

$\mathrm{INC}(i)$ ajoute $1$ au contenu de $R_i$ et passe à l'instruction suivante ;

$\mathrm{DEC}(i, j)$ , si $R_i$ contient un entier non nul, lui retire $1$ et passe à l'instruction suivante ; sinon, elle passe à l'instruction de numéro $j$ .

Une configuration est un couple $(\ell, r)$ formé d'un numéro d'instruction $\ell \in {\mathbb N}$ et d'une application $r : \mathbb N \to \mathbb N$ nulle sauf en un nombre fini de points, $r(i)$ étant le contenu de $R_i$ . Elle est terminale si $\ell \geqslant L$ ; sinon, l'instruction $I_\ell$ la transforme comme on vient de le dire en une configuration suivante.

Soit $n \geqslant 1$ . Le calcul de $P$ sur $x \in {\mathbb N^n}$ est la suite des configurations issue de $(0, r_x)$ , où $r_x(i) = x_i$ pour $1 \leqslant i \leqslant n$ et $r_x(i) = 0$ sinon. S'il atteint une configuration terminale $(\ell, r)$ , on pose $f_P^{(n)}(x) = r(0)$ ; sinon, $f_P^{(n)}(x)$ n'est pas défini. Une fonction partielle est calculable par machine si elle est l'une des $f_P^{(n)}$ .

Remarque

Le programme suivant calcule l'addition. Le registre $R_3$ reste nul, si bien que $\mathrm{DEC}(3, j)$ est un saut inconditionnel vers l'instruction $j$ : $\begin{array}{ll} I_0 = \mathrm{DEC}(1, 3) & I_3 = \mathrm{DEC}(2, 6) \\ I_1 = \mathrm{INC}(0) & I_4 = \mathrm{INC}(0) \\ I_2 = \mathrm{DEC}(3, 0) & I_5 = \mathrm{DEC}(3, 3) \end{array}$ La première boucle vide $R_1$ dans $R_0$ , la seconde vide $R_2$ dans $R_0$ , et le calcul s'arrête au numéro $6 = L$ .

Le programme de l'addition : les flèches grises mènent à l'instruction suivante, après un incrément ou quand le registre testé est non nul, et les flèches rouges sont les sauts pris quand il est nul. Les deux sauts inconditionnels, en pointillé, ramènent au début de chaque boucle, dont l'effet est indiqué en bleu.

L'exécution sur

x = (2, 1)

: chaque ligne donne le numéro de l'instruction à exécuter et le contenu des registres après

t

étapes. Le registre

R_0

, en rouge, reçoit une unité à chaque passage par

I_1

I_4

, et la machine s'arrête au bout de

11

étapes avec

R_0 = 3

Une vérification exhaustive pour $x, y \leqslant 5$ montre que le calcul s'arrête toujours, en $3x + 3y + 2$ étapes, avec $R_0 = x + y$ .

Remarque

Ce modèle est volontairement pauvre : deux instructions, aucune mémoire autre que des entiers. Les machines de Turing, introduites par Alan Turing (« On computable numbers, with an application to the Entscheidungsproblem », Proceedings of the London Mathematical Society 42, 1936-1937), lisent et écrivent des symboles sur un ruban ; elles calculent exactement les mêmes fonctions, mais l'équivalence demande un codage plus long. L'erreur serait de croire que la pauvreté du modèle limite ce qu'il calcule : le nœud Kleene montre qu'il calcule toutes les fonctions récursives, et rien de plus.

Repose sur

Fonctions récursives partielles

Sert à

Les fonctions récursives sont calculables par machine