Modèles de calcul, TD numéro 2

Natacha Portier mardi 1er février 2000

Rappel : Une RAM sur l’alphabet A_{k} est un ensemble infini de registres R_{1}, R2, ... pouvant chacun contenir un mot, un ensemble de noms de lignes N_{1}, N2, ... et une suite finie d’instructions du type :

1j) X add j Y (ajoute a_{j} à la droite du registre)

2) X del Y (efface la lettre la plus à gauche du registre si elle existe)

3) X clr Y (met le mot vide dans le registre Y)

4) X Y←Z (copie le mot de Z dans Y en le laissant aussi dans Z)

5) X jmp X’ (va à la ligne X’ la plus proche, a avant ou b après)

6j) X Y jmp j X’(si la première lettre du mot dans Y est a_{j}, va à la ligne X’ la plus proche, a avant ou b après)

7) X continue (ne fait rien) où X est un nom de ligne ou rien, Y et Z des noms de registres et X’ un nom de ligne suivi par a pour avant ou b pour après. En fait, les règles 1j, 2, 6j et 7 forment un ensemble minimal suffisant pour les fonctions calculables par RAM.

Question 1

Nous allons montrer que toute fonction calculable par une RAM est calculable par une machine de Turing.

Une SRM (machine à un seul registre) sur A_{k} est une machine qui n’a qu’un seul registre qui peut contenir n’importe quel mot de A_{k}^{∗}. Ses instructions sont de trois sortes :

1j) X add j (ajoute a_{j} à la droite du registre)

2) X del (efface la lettre la plus à gauche du registre si elle existe)

3) X jmp j X’ (va à X’ si le registre commence par a_{j}) où X est un nom de ligne ou rien et X’ un nom de ligne suivi par a pour avant ou b pour après.

Si Φ est une fonction partielle de A_{k}^{∗} alors un programme P qui est une SRM sur A_{k+1} = A_{k} ∪ {, } calcule Φ si quand le registre contient x_{1}, ..., x_{n} alors P s’arrête et le registre contient Φ(x_{1}, ..., x_{n}).

Question 1,1

Donner une SRM qui sur l’entrée x_{1}, ..., x_{n} calcule x_{2}, ..., x_{n}, x_{1}.

Question 1,2

Montrer que toute fonction calculable par une RAM est calculable par une SRM.

Question 1,3

Montrer que toute fonction calculable par une SRM est calculable par une machine de Turing.

Question 2

Une RAM sur l’ensemble des entiers est un ensemble infini de registres R_{1}, R2, ... pouvant chacun contenir un entier, un ensemble de noms de lignes N_{1}, N2, ... et une suite finie d’instructions du type :

1) X R_{i} := 1

2) X R_{i} := R_{j} + R_{k}

3) X R_{i} := R_{j} − R_{k}

4) X R_{i} := ⌊R_{i}/2⌋

5) X R_{i} := R_{R_{j}}

6) X R_{R_{i}} := R_{j}

7) X aller à la ligne m si M_{i} > 0.

8) arrêt où X est un nom de ligne.

Question 2,1

Donner une RAM qui sur l’entrée n calcule n!. Question 2,2

Donner une RAM qui, lorsqu’on lui donne une suite de n entiers suivie de 0, écrit les n entiers dans l’ordre. Question 2,3

Donner une RAM qui, si on lui donne en entrée les entiers x et i, calcule le ie bit de l’écriture binaire de x. Question 2,4

Donner une RAM qui, si on lui donne en entrée les entiers x et y, calcule le produit xy en un temps proportionnel à la longueur des entrées. Question 2,5

Donner une RAM qui, si on lui donne en entrée les entiers x et y, calcule le quotient de la division euclidienne de x par y en un temps proportionnel à la longueur des entrées. Question 2,3

Donner une RAM qui accepte les entrées de la forme 1^{n}2^{n^{2}}0