Par O. Bailleux, Maître de conférences HDR à l'université de Bourgogne.

TP2

Le but de ce TP est de réaliser un simulateur de machine de Turing en langage C.

1. La machine de Turing à réaliser

La machine que nous allons simuler est constituée :

• d’une bande comportant des cases contenant des symboles,
• d’une variable d’état contenant un entier positif ou nul,
• d’une tête de lecture / écriture qui se situe en face d’une des cases de la bande,
• d’un programme.

La bande comporte 32 cases. Chaque case contient un symbole parmi trois possibles : #, 0 et 1. Le symbole # a pour rôle de délimiter les données placées sur la bande. Ces données sont codées avec les symboles 0 et 1.

La variable d’état peut prendre une valeur entre 0 et 7. L’état 0 est appelé état initial. C’est l’état de la machine au début de l’exécution d’un programme. L’état 7 est appelé état final. On le note STOP Il indique la fin de l’exécution du programme de la machine.

La tête est représentée par une variable dont la valeur, comprise entre 0 et 31, représente la position sur la bande.

Voici une représentation schématique de la machine juste avant l’exécution de son programme. Sa tête de lecture est en position 0 (visualisée par le point sous la première case). Son état est 0. Sa bande contient des valeurs qui représentent la donnée d’entrée du programme. Le programme n’apparait pas sur le dessin.

On appelle situation le couple $(v,e)$ où $v$ est la valeur de la case désignée par la tête et $e$ l’état courant de la machine. La machine représentée ci-dessus est dans la situation (valeur : #, état : 0).

Le programme associe une action à chaque situation. Une action indique ce que doit faire la machine à la prochaine étape d’exécution du programme. Elle consiste en trois ordres :

• Une valeur à écrire sur la bande à l’emplacement actuel de la tête (qui peut être identique ou différente de la valeur actuelle).
• Un sens de déplacement de la tête : gauche ou droite. Le déplacement sera réalisé après l’écriture de la valeur.
• La valeur du nouvel état de de la machine (qui peut être identique ou différente de celle de l’état actuel)

Voici un exemple de programme…

…qui peut être représenté graphiquement comme ci-dessous :

Pour exécuter ce programme, on regarde la situation actuelle, qui est (valeur : #, état : 0). D’après le programme, l’action à réaliser qui est #, droite, 1. La valeur # est placée dans la case désignée par la tête, qui contenait déjà cette valeur, le nouvel état est 1 et la tête se déplace à droite.

On regarde la nouvelle situation, (valeur : 0, état : 1). D’après le programme, l’action à réaliser est 0, droite, 1.

Continuez à exécuter le programme à la main. Vous devriez obtenir la donnée #0100# en début de bande lorsque l’état final est atteint.

2. Conception d’un programme de simulation

Nous sommes face à un problème d’ingénierie logicielle. Nous devons réaliser un programme qui simule la machine de Turing présentée dans le section précédente. La première étape consiste à déterminer comment la machine et son programme seront représentés. Ensuite, il faudra implémenter les fonctions permettant de simuler l’exécution du programme.

Représentation de la machine

Dans le cadre de ce TP, nous utiliseront la représentation suivante de la machine sans son programme :

• La bande est représentée par un mot binaire de 64 bits placé dans une variable globale de type uint64_t.
• La position de la tête est représentée par une variable de type int.
• L’état est représenté par une variable de type int.

uint64_t Tape = 0;
int Head = 0;
int State = 0;

Chaque case de la bande est représentée par 2 bits consécutifs avec la convention suivante :

• 00 représente la valeur 0,
• 01 représente la valeur 1,
• 10 représente la valeur #.

Voici la manière d’initialiser la bande avec l’exemple présenté dans la section précédente.

Tape = 0b1000000101100000000000000000000000000000000000000000000000000000;
//        # 0 0 1 1 # 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Il est crucial, en ingénierie logicielle, de bien distinguer les données représentées et les représentations de ces données utilisées par un programme. Ici, par exemple, la valeur 0 d’une case de la bande est représentée par la séquence de deux bits 00, la valeur 1 est représentée par la séquence 01, la valeur # par la séquence 10.

Représentation du programme

Représentation d’une action

Les actions sont représentées par des octets (type uint8_t) avec la convention suivantes :

• Les bits de rangs 0 à 2 représentent le nouvel état.
• Le bit de rang 3 représente le sens de déplacement de la tête (1 pour droite, 0 pour gauche).
• Les bits de rangs 4 et 5 représentent la valeur à écrire sur la bande.
• Les bits de rangs 6 et 7 ne sont pas utilisés.

À titre d’exemple, voici le codage de l’action #, droite, 3 :

Pour faciliter le codage d’une action, on utilise les masques suivants, définis sous forme de constantes :

#define BLANK 0b100000 // Valeur #
#define ZERO 0b000000 // Valeur 0
#define ONE 0b010000 // Valeur 1

#define LEFT 0b000000 // Déplacement à gauche
#define RIGHT 0b001000 // Déplacement à droite

Par exemple, l’action #, droite, 3 se code :

uint8_t action = BLANK | RIGHT | 3;

Vous pouvez le vérifier en combinant les masques à l’aide du ou bitwise |.

Exercice

Essayez de coder de cette manières chacune des actions suivantes et donnez le mots binaire correspondant.

1. 1, gauche, 2
2. 0, droite, 4

uint8_t action = ONE | LEFT | 2; // 00010010

uint8_t action = ZERO | RIGHT | 4; // 00001100

Représentation du programme de la machine

Le programme de la machine de Turing est représenté par un tableau d’actions. Voici le programme d’exemple donné dans la section 1 :

uint8_t Prog[] =
{
ZERO|RIGHT|STOP, ONE|RIGHT|STOP, BLANK|RIGHT|1, // Si état 0
ZERO|RIGHT|1, ONE|RIGHT|1, BLANK|LEFT|2, // Si état 1
ONE|LEFT|3, ZERO|LEFT|2, BLANK|LEFT|STOP, // Si état 2
ZERO|LEFT|3, ONE|LEFT|3, BLANK|LEFT|STOP // Si état 3
};

Les trois premières actions du tableau sont celles à réaliser dans les situations ou l’état est 0 et la valeur lue sur la bande respectivement 0, 1 et #.

Les trois suivantes sont celles à réaliser dans les situations ou l’état est 1 et la valeur lue sur la bande respectivement 0, 1 et #.

Etc.

D’une manière plus générale, si l’état courant est etat et la valeur lue sur la bande est val, alors l’action à réaliser est Prog[(3 * etat) + val].

Exemple : Si la situation est (valeur : 0, état : 1), alors l’action à réaliser est Prog[3], c’est à dire ZERO|RIGHT|1 : écriture d’un 0 sur la bande, déplacement à droite, le nouvel état est 1.

Exercice

Quelle est l’action à réaliser, d’après le programme d’exemple, si la situation est (valeur : 1, état : 2) ?

Constantes et variables globales

Voici le début du programme de simulation avec les constantes et variables globales que nous avons déjà présentées, plus la constante STOP qui représente la valeur de l’état final de la machine (celui qui termine l’exécution du programme).

#include
#include
#include

#define BLANK 0b100000
#define ZERO 0b000000
#define ONE 0b010000

#define LEFT 0b0000
#define RIGHT 0b1000

#define STOP 7

int Head = 0;
uint64_t Tape = 0;
int State = 0;
uint8_t Prog[] =
{
ZERO|RIGHT|STOP, ONE|RIGHT|STOP, BLANK|RIGHT|1, // Si état 0
ZERO|RIGHT|1, ONE|RIGHT|1, BLANK|LEFT|2, // Si état 1
ONE|LEFT|3, ZERO|LEFT|2, BLANK|LEFT|STOP, // Si état 2
ZERO|LEFT|3, ONE|LEFT|3, BLANK|LEFT|STOP // Si état 3
};

Fonctions à définir

Lecture d’une valeur sur la bande

int read(int i);

Lit la valeur située en position i sur la bande. La valeur de retour peut être 0, 1 ou 2 (qui représente la valeur #).

Affichage

void print();

Affiche la bande, la tête de lecture et l’état courant. Avec les valeurs des variables données précédemment, les lignes…

Tape = 0b1000000101100000000000000000000000000000000000000000000000000000;
print();

…doivent produire l’affichage suivant :

# 0 0 1 1 # 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 [0]
T

La lettre T représente la position de la tête (ici au début de la bande). La valeur entre crochet est celle de l’état courant, donnée par la variable State.

Cette fonction appelle la fonction read.

Écriture d’une valeur sur la bande

void write(int i, int val);

Écrit la valeur val (0, 1 ou 2) en position i sur la bande. La valeur 2 se représente aussi 0b10 et correspond à la valeur notée #.

Exécution du programme

uint8_t nextAction();

Retourne la prochaine action à réaliser qui dépend :

• de l’état courant (variable State),
• de la valeur désignée par la tête de lecture sur la bande
• et du programme.

void operate(uint8_t action);

Réalise l’action désignée par le paramètre action. Cette fonction écrit une valeur sur la bande, modifie la position de la tête (variable Head), et met à jour la valeur de l’état courant (variable State).

Si la tête de lecture est en début de bande et si l’action suppose un déplacement à gauche alors la tête doit garder sa position. Si la tête est en fin de bande et si l’action impose un déplacement à droite alors la tête doit garder sa position.

Ces deux fonctions sont appelées par la fonction run, définie ci-dessous, qui assure l’exécution du programme.

void run()
{
print();
State = 0;
while(State != END_STATE)
{
uint8_t action = nextAction();
operate(action);
print();
getchar(); // Il faut presser la touche entrée pour continuer
}
printf("Exécution terminée\n");
}

Travail à réaliser

Vous devez définir les fonctions dont le code n’a pas été donné précédemment, les tester séparément, puis tester l’exécution du programme d’exemple. Ce programme réalise une incrémentation de la valeur en base 2 située en début de bande entre les 2 symboles #.

Modifications du simulateur

À ce stade, vous devez avoir un simulateur fonctionnel et comprendre les moindres détails de son implémentation et des représentations des données utilisées. Les modifications à réaliser devront être testées avec des programmes de machine de Turing conçus à cette fin.

Augmentation du nombre d’états

La machine simulée précédemment peut admettre au plus 7 états, numérotés de 0 à 6, plus l’état final qui arrête le programme.

Vous devez modifier le simulateur, en réutilisant au maximum le code existant et les principes et représentation utilisés, pour que le nombre maximum d’états soit égal à 32 (états 0 à 30 plus l’état final codé par l’entier 31). Dans la nouvelle version, tous les bits des octets représentant les actions seront utilisés, ce qui permettra de représenter les états sur 5 bits.

Augmentation de la taille de la bande

La machine simulée précédemment a une bande de 32 cases représentée par un seul entier de type uint64_t.

Vous devez réaliser une version dans laquelle la taille de la bande, multiple de 32, est définie par une constante SIZE_TAPE. Le nombre de cases de la bande sera égal à SIZE_TAP * 32 et la bande sera représentée par le tableau :

uint64_t Tape[SIZE_TAPE] = {0};

Le codage du programme de la machine de Turing simulée doit être identique et vous devez réutiliser autant que possible les principes et la structures du simulateur précédent en modifiant certaines fonctions.

L’affichage doit être modifié de manière à que la tête apparaisse au milieu de l’écran et que seules les parties de la bande située autour, dans la limite de 16 cases de chaque coté, soient affichées.