Les machines RAM sont des machines abstraites qui ressemblent aux microprocesseurs. Elles sont constituées d'un programme formé d'une suite d'instructions et d'une suite infinie de registres. Les seules données que manipulent ces machines sont des entiers qui peuvent être arbitrairement grands. Les entrées et les sorties sont faites à travers une bande d'entrée et une bande de sortie sur lesquelles sont lus et écrits des entiers.
Il existe aussi une variantes de ces machines appelées machines RAST. Dans ces machines RAST, le programme est stocké dans les premiers registres de données de la machine. Il peut donc être manipulé comme tout autre donnée. Il n'est pas très difficile de montrer que ces machines sont en fait équivalentes aux machines RAM.
Une machine RAM est constituée
Les registres et l'accumulateur contiennent les données manipulées par la machine. On suppose que chacun des registres ainsi que l'accumulateur peut contenir un entier positif ou nul. Les entiers contenus dans les registres peuvent être arbitrairement grands. Au lancement du programme tous les registres sont initialisés à la valeur zéro.
Les instructions des machines RAM se divisent en quatre catégories qui sont les suivantes.
Les deux instructions de manipulation de registres sont les instructions load et store. L'instruction load permet de charger une valeur dans l'accumulateur à partir d'un registre ou d'une valeur explicite donnée en paramètre. L'instruction store permet de charger une valeur dans un registre à partir de l'accumulateur. L'instruction load admet les trois syntaxes suivantes.
L'instruction store admet les deux syntaxes suivantes.
Les machines RAM ne possèdent que les deux opérations arithmétiques incr et decr. Ces deux instructions ne prennent pas de paramètre. L'instruction incr augmente d'une unité le contenu de l'accumulateur. L'instruction decr diminue d'une unité le contenu de l'accumulateur si ce contenu est strictement positif. Sinon, elle laisse le contenu de l'accumulateur inchangé.
Il est possible d'ajouter d'autres opérations arithmétiques aux machines RAM comme l'addition, la soustraction ou même la multiplication mais nous avons fait le choix de limiter au maximum le jeu d'instructions sans pour autant limiter la puissance de calcul. Il n'est pas difficile de voir que les deux seules instructions d'incrémentation et de décrémentation suffisent pour effectuer toutes les autres opérations arithmétiques.
Les machines RAM ne possèdent que les trois instructions de rupture de séquences jump, jz et stop. Les deux instructions de saut jump et jz prennent en paramètre un entier qui désigne le numéro d'une instruction dans le programme. L'instruction stop ne prend pas de paramètre. L'instruction jump est appelée saut inconditionnel. Après l'exécution de cette instruction, le fonctionnement du programme se poursuit à l'instruction dont le numéro est donné en paramètre. L'instruction jz est appelée saut conditionnel. Après l'exécution de cette instruction, le fonctionnement du programme se poursuit à l'instruction dont le numéro est donné en paramètre si le contenu de l'accumulateur est zéro et à l'instruction suivante sinon. L'instruction stop provoque l'arrêt de la machine.
Les machines RAM ne possèdent que les deux instructions d'entrées/sorties read et write. Ces deux instructions ne prennent pas de paramètre. L'instruction read provoque la lecture d'un entier sur la bande d'entrée et le résultat est placé dans l'accumulateur. Chaque lecture avance la tête de lecture de façon que des instructions read successives lisent séquentiellement les données sur la bande. L'instruction write provoque l'écriture du contenu de l'accumulateur sur la bande de sortie.
Le déroulement du programme de la machine RAM consiste à exécuter en séquences les instructions du programme en commençant à l'instruction de numéro zéro. Après l'exécution d'une instruction autre qu'une instruction de rupture de séquence, c'est l'instruction suivante qui est exécutée. Une instruction de saut indique directement quelle est l'instruction suivante à exécuter. Ce processus se poursuit jusqu'à l'exécution d'une instruction stop ou la rencontre de la fin du programme. On suppose qu'il y a implicitement une instruction stop à la fin du programme.
Les machines RAM que nous avons introduites ressemblent aux microprocesseurs mais il y a quelques différences. Certaines sont superficielles alors que d'autres sont plus essentielles.
La différence la plus importante est que le nombre de registres d'une RAM est illimité alors que la mémoire à laquelle accède un microprocesseur est limitée. De même, chaque registre de la RAM peut contenir un entier arbitrairement grand alors qu'un véritable microprocesseur manipule des mots mémoire ayant un nombre fixé de bits.
Le jeu d'instructions que nous avons choisi pour nos machines RAM est beaucoup plus limité que celui qu'on trouve en général dans un microprocesseur. Dans un certain sens, nos machines RAM se rapprochent des microprocesseurs RISC qui ont un jeu d'instructions plus réduit que les microprocesseurs classiques. En particulier, elles ne possèdent pas d'opérations arithmétiques comme l'addition ou d'autres plus compliquées. Il n'est pas difficile de voir que ces opérations peuvent être effectuées en utilisant uniquement l'incrémentation et la décrémentation. Les exemples suivants de programmes montrent que l'addition et la multiplication peuvent être faites par des programmes.
Le programme suivant lit deux entiers, calcule leur somme et l'écrit sur la bande de sortie.
0 read // Lecture du premier entier x 1 store 0 // Sauvegarde de x dans R0 2 read // Lecture du second entier y 3 store 1 // Sauvegarde de y dans R1 4 load 0 // Début de la boucle de calcul 5 jz 12 // Test de sortie de boucle 6 decr // À chaque itération de la boucle, 7 store 0 // R0 est décrémenté et R1 est incrémenté. 8 load 1 // La boucle s'arrête quand R0 contient 0. 9 incr // R1 contient alors la somme de x et y. 10 store 1 11 jump 4 // Fin de la boucle de calcul 12 load 1 13 write // Affichage de la somme 14 stop
Le programme suivant lit deux entiers, calcule leur produit et l'écrit sur la bande de sortie.
0 read 1 store 2 // Entier x 2 read 3 store 3 // Entier y 4 load #0 5 store 4 // Résultat 6 load 2 7 jz 25 8 decr 9 store 2 10 load 3 11 store 0 12 load 4 13 store 1 14 load 0 15 jz 22 16 decr 17 store 0 18 load 1 19 incr 20 store 1 21 jump 14 22 load 1 23 store 4 24 jump 6 25 load 4 26 write 27 stop
Le programme suivant utilise une indirection pour remplir chaque registre Rn avec la valeur n pour n ≥ 1. Le registre zéro sert d'indirection. C'est un programme qui ne s'arrête pas.
0 load #0 2 incr 3 store 0 4 store (0) 5 jump 2
Afin de réutiliser une partie d'un programme déjà écrit, il est souvent nécessaire de s'assurer qu'un programme n'utilise pas certains registres. Afin de libérer certains registres, on décale tous les registres du programme d'un certain nombre k de positions. Pour les indirections, il faut utiliser trois registres supplémentaires et le décalage réellement nécessaire est de k+3 positions. Les transformations suivantes décalent de k+3 positions les registres d'un programmes et assurent alors que les registres de 3 à k+2 ne sont plus utilisés.
Les instructions load <n> et store <n> sont respectivement remplacées par les instructions load <n+3> et store <n+3>. Ces transformation suffisent si le programme n'utilise pas d'indirection. Sinon, chaque instruction load (<n>) est remplacée par
load <n+3>
store 0
load #k+3 // Décalage à ajouter pour l'indirection
store 1
--> load 1
| jz ... --
| decr |
| store 1 |
| load 0 |
| incr |
| store 0 |
-- jump ... |
load (0) <--
et chaque instruction store (<n>) est remplacée par
store 2 // Sauvegarde du contenu de A
load <n+3>
store 0
load #k+3 // Décalage à ajouter pour l'indirection
store 1
--> load 1
| jz ... --
| decr |
| store 1 |
| load 0 |
| incr |
| store 0 |
-- jump ... |
load 2 <-- // Restitution du contenu de A
store (0)
Lorsque l'entier k est petit, les boucles qui servent à ajouter k+3 au contenu du registre Rn peuvent être remplacées par des incrémentations. Le registre R1 qui servait à la boucle n'est plus nécessaire. Il suffit alors de décaler de trois registres pour en libérer un. Si on applique à cette méthode au programme qui remplit chaque registre Rn avec la valeur n, on obtient le programme suivant.
0 load #0 2 incr 3 store 3 4 store 2 // Sauvegarde du contenu de A 5 load 3 // Inutile 6 incr // Décalage de trois positions 7 incr 8 incr 9 store 0 // Le registre R0 sert à faire l'indirection 10 load 2 // Restitution du contenu de A 11 store (0) 12 jump 2
Nous allons voir que les machines RAM sont équivalentes aux machines de Turing. Ceci signifie que toute fonction calculée par une machine RAM peut aussi l'être par une machine de Turing et qu'inversement toute fonction calculée par une machine de Turing peut aussi l'être par une machine RAM.
L'idée de la simulation est assez simple. La bande de machine de la Turing va être stockée dans les registres à partir de R1. Chaque symbole de la bande est mis dans un registre. Le premier symbole sur la bande est mis dans le registre R1, le second dans le registre R2 et ainsi de suite. Le registre R0 contient la position de la tête de lecture, c'est-à-dire le numéro du registre qui contient le symbole sous la tête de lecture. On associe un code entier à chacun des symboles de Γ. On suppose que le code du symbole blanc # est zéro.
L'initialisation de la machine RAM consiste à lire le contenu initial de la bande de la machine de Turing et à le mettre dans les registres correspondants. Ceci est fait par le morceau de programme suivant.
0 load #1 // R1 est le premier registre pour la bande 1 store 0 // Position de la tête de lecture 2 read // Lecture d'un symbole 3 jz 9 // Arrêt sur un # codé par 0 4 store (0) // Mise en place dans le registre correspondant 5 load 0 6 incr // Déplacement vers la droite 7 store 0 8 jump 2 9 load #1 // Mise en place de la tête de lecture 10 store 0 // au début de la bande 11 jump q0 // Saut à l'état initial
Ensuite,pour chacun des états de la machine de Turing, on écrit un morceau de programme qui simule les transitions de la machine de Turing lorsqu'elle est dans cet état. Supposons par exemple que la machine de Turing possède les trois transitions suivantes : q0, a → q1, b, R, q0, b → q1, c, L et q0, # → q0, #, R. On suppose que les codes des symboles #, a, b et c sont 0, 1, 2 et 3. Voici le morceau de code correspondant à ces transitions possibles de la machine de Turing dans l'état q0. Au lieu d'écrire explicitement les numéros des instructions, on leur donne des noms symboliques appelés labels. Le label q0 est par exemple le numéro de la première instruction correspondant à ce morceau de code. De même, les labels q1 et q2 sont les numéros des premières instructions des morceaux qui simulent les transitions de la machine de Turing dans les états q1 et q2.
q0: load (0) // Lecture du symbole sous la tête
jz q0# // Ce symbole est #
decr
jz q0a // Ce symbole est a
decr
jz q0b // Ce symbole est b
stopl: stop // Arrêt de la simulation
q0#: load 0
incr // Déplacement à droite de la tête
store 0
jump q0
q0a: load #2 // Code de b
store (0) // Écriture du b
load 0
incr // Déplacement à droite de la tête
store 0
jump q1
q0b: load #3 // Code de c
store (0) // Écriture du c
load 0
decr
jz stopl // La tête était sur la première position
store 0
jump q2
Si un état q est final, le morceau de code de l'état q se contente d'écrire sur la bande de sortie le contenu de la bande la machine de Turing au moment où elle atteint l'état q. Cette opération est effectuée par le morceau de programme suivant.
q: load #1
store 0 // Position de la tête de lecture
qcont: load (0) // Lecture du symbole sous la tête
jz stopl
write // Écriture sur la bande sortie
load 0
incr // Déplacement vers la droite
store 0
jump qcont
En écrivant un morceau de programme similaire pour chacun des états de la machine, on obtient en tout un programme qui simule globalement le fonctionnement de la machine de Turing.
L'idée de la simulation est relativement simple. La machine RAM est simulée par une machine de Turing à deux bandes. La première bande contient le contenu de tous les registres de la machine RAM y compris l'accumulateur. Les entiers contenus dans les registres sont écrits en binaire sur l'alphabet {0, 1}. Le contenu de l'accumulateur est mis en premier sur la bande, suivi du contenu du registre R1, puis du registre R2 et ainsi de suite. Les écritures binaires des contenus sont séparés par le caractère ','. À un instant donné, la bande ne contient que les valeurs d'un nombre fini de registres. Les contenu des autres est par convention leur valeur initiale qu'on suppose être zéro.
À chaque instruction du programme, on va associer une partie de la machine de Turing qui sera chargée de simuler le fonctionnement de l'instruction donnée. Ces parties sont ensuite mises bout à bout pour constituer une machine de Turing globale.
Les manipulations de registres nécessitent de savoir retrouver le contenu d'un registre. Pour ce faire, la machine de Turing écrit le numéro du registre sur la seconde bande. Elle parcourt ensuite la première bande en incrémentant l'entier sur la seconde bande à chaque passage sur le séparateur ',' sur la première bande. Si la machine ne trouve pas assez de virgules sur la première bande, elle en ajoute en les séparant par 0 qui est le contenu initial d'un registre. Ensuite, les manipulations consistent à recopier le contenu du registre dans l'accumulateur pour load ou le contenu de l'accumulateur dans le registre pour store. Dans le cas d'une indirection (adressage indirect), la machine copie d'abord le contenu du registre sur la seconde bande puis recherche à nouveau le registre correspondant avant de copier les contenus.
Simuler les instructions arithmétiques est facile puisqu'il s'agit simplement de modifier le contenu de l'accumulateur qui se trouve au début de la première bande.
Les instructions de saut ne sont pas vraiment simulées. Elles influent sur la façon dont les différentes parties sont combinées pour former la machine de Turing globale.