novembre
2010
Un article de gnuvince
Ce billet est le premier d’une série dans lequel je vais décrire l’implantation d’un simulateur simple de machines de Turing dans le langage OCaml. De billet en billet, nous verrons comment améliorer le code pour obtenir un simulateur plus rapide.
Commençons tout d’abord par définir une machine de Turing; si vous ouvrez un livre d’informatique théorique, vous y trouverez une définition très formelle et un peu intimidante des machines de Turing avec des lettres grecques:
MT = (Q, Σ, Γ, δ, q0, qa, qr)
Qu’est-ce que c’est ce charabia? Commençons par décrire plus informellement une machine de Turing et son fonctionnement:
+----------+
| |
| CONTRÔLE |----
| | |
+----------+ | TÊTE
|
v
+---+---+---+---+---+---+---+---+---
| | | a | b | c | b | a |
+---+---+---+---+---+---+---+---+---
RUBAN
La machine de Turing possède trois partie:
- Le contrôle: cette partie contient une seule information: l’état actuel de la machine de Turing. C’est le programmeur qui décide de l’état qui va dans le contrôle.
- Le ruban: un ruban infini vers la gauche et vers la droite où se trouve dans chaque cellule un caractère ou un blanc.
- La tête: la tête pointe vers un caractère dans le ruban. La tête peut se déplacer à gauche ou à droite d’une seule cellule et elle ne peut pas rester sur place.
Si on reprend la définition formelle de la machine de Turing, voici ce que signifie chacune des 7 composantes du tuple:
- Q: un ensemble fini d’états (ceux-ci iront dans le contrôle)
- Σ: l’alphabet d’entrée: un ensemble fini et non-vide de caractères acceptés pour l’entrée.
- Γ: l’alphabet du ruban: un sur-ensemble de Σ qui décrit les caractères acceptés sur le ruban. Au minimum, Γ = Σ plus le caractère blanc.
- δ: la fonction de transition: elle prend la configuration actuelle de la machine de Turing (l’état actuel, et le caractère pointé par la tête) et donne le nouvel état, le caractère à écrire sur le ruban et la direction dans laquelle la tête de lecture doit se déplacer.
- q0: l’état initial
- qa: l’état acceptant: nous utiliserons toujours le mot « ACCEPTE »
- qr: l’état rejetant: nous utiliserons toujours le mot « REJETTE »
Voici un exemple d’une machine de Turing qui accepte si le mot donné en entrée possède un nombre pair de ‘a’ et rejette si l’entrée possède un nombre impair de ‘a':
pair, a, pair, a, D pair, b, impair, b, D pair, _, ACCEPTE, _, D impair, a, impair, a, D impair, b, pair, b, D impair, _, REJETTE, _, D
Chaque ligne possède 5 informations séparées par des virgules: les deux premières sont les configurations possibles: est-ce qu’on est dans l’état « pair » et que le caractère sous la tête de lecture est ‘a’? Si oui, le nouvel état est « pair », on écrit ‘a’ sur le ruban et on déplace la tête de lecture vers la droite.
Ce programme va lire tous les caractères de l’entrée et les réécrire sur le ruban. Quand il lit un ‘b’, il change l’état du contrôleur de pair à impair et vice-versa. Quand on lit le caractère blanc, cela indique la fin de l’entrée et on accepte si on est dans l’état pair et on rejette si on est dans l’état impair.
Nous allons concevoir un simulateur qui prendra en entrée un tel fichier, un état de départ et une chaîne d’entrée et qui simulera la machine sur cet entrée. La machine affichera à la fin si on accepte ou rejette l’entrée et en combien d’étapes:
$ ./tm pair.tm aaaba pair ACCEPTE (6)