séquence 209_5

2. La machine de Turing

2.1. Présentation

En 1936, Alan Turing (1912-1954), dans [Turing36], présente sa machine (appelée depuis machine de Turing). Elle est composée :

d'une unité centrale se trouvant dans un état q_i, pris parmi l'ensemble fini de ses états internes, noté Q={q₁, q₂, ..., q_n}. Parmi les états, on distingue un état initial (état au lancement de la machine) et des états finaux (états de la machine en situation de terminaison). Le comportement de l'unité centrale est déterminé par son programme.
d'un ruban de taille illimitée divisé en cases, contenant au départ les données à traiter, et à l'arrivée les résultats des calculs. Les données de départ tout comme les résultats sont représentés sur le ruban à l'aide de symboles pris dans un alphabet A={a₀, a₁, a₂, ..., a_m}. Chaque case ne contient qu'un symbole.
d'une tête de lecture-écriture qui assure la communication entre l'unité centrale et le ruban. Cette tête n'agit que sur une case à la fois. Elle peut remplacer le symbole lu par un autre symbole et déplacer le ruban d'une case vers la gauche ou vers la droite.

Schéma structureMachine de Turing
Structure d'une machine de Turing

Le rôle du programme consiste à déterminer, pour un état q_i de la machine et pour un symbole a_j situé devant la tête de lecture-écriture, le nouvel état dans lequel passe la machine ainsi que l'opération effectuée sur le ruban. On représente un programme par un ensemble fini de quintuplets, appelé fonction de transition. Celle-ci définit les règles d'évolution, appelées règles de transition, de la forme (q_i,a_j, q_k, a_l, d_m) ou μ(q_i,a_j) = (q_k, a_l, d_m) où :

q_i ∈Q est l'état initial ;
a_j ∈ A le symbole lu ;
q_k ∈ Q le nouvel état ;
a_l ∈ A ∪ {ε} le caractère à écrire (ε n'écrit rien, c'est-à-dire laisse le caractère a_j sur le ruban) ;
d_m ∈ {D, G, C} le sens du déplacement de la tête avec respectivement D pour aller d'une case vers la droite, G d'une case vers la gauche et C pour ne pas se déplacer.

Parmi les états de la machine, il en existe un particulier : l'état initial (q_I). C'est le premier état pris par la machine. Il existe aussi un ensemble d'états appelés états finaux.

Configuration
Configuration initiale
Configuration finale (terminale)

On appelle configuration tout couple symbole / état. Une règle détermine donc pour une configuration courante, l'action à effectuer et donc la prochaine configuration.

On appelle configuration initiale tout couple symbole / état où l'état est un état initial.

On appelle configuration finale tout couple symbole / état où l'état est un état final.

Si la machine de Turing est telle qu'il n'existe pas de règle μ(q_i,a_j)=(x,y,z) pour l'état q_i et le symbole a_j de la configuration courante alors le ruban est dit terminal. Si l'état courant est un état final alors l'exécution est réussie et le programme s'est déroulé normalement. Le cas contraire est une situation d'échec.

La suite de symboles S du ruban terminal est une chaîne dite terminale (la disposition de départ étant appelée chaîne initiale). Dans cette configuration S(q), la machine de Turing s'arrête. Par ailleurs, le symbole ε permet aussi souvent d'arrêter la machine, c'est-à-dire qu'il n'existe pas de transition de la forme μ(q,ε).

Machine de Turing déterministe

La machine de Turing est dite déterministe si pour toute configuration, il n'existe qu'une seule fonction de transition applicable, c'est-à-dire si et seulement si pour μ(x,y)=(z₁,t₁) et μ(x,y)=(z₂,t₂) deux règles, alors z₁=z₂ et t₁=t₂. Dans le cas contraire, la machine est dite non déterministe (pour une configuration donnée, plusieurs règles sont applicables).

Machine de Turing

Une machine de Turing est définie par un quintruplet (A, Q, I, F, μ) tel que :

A est l'alphabet (fini, non vide) ;
Q est l'ensemble des états possibles pour la machine (fini et non vide) ;
I ∈ Q l'état initial ;
F ⊆ Q l'ensemble des états finaux ;
μ la fonction de transition telle que μ : Q × A → Q × A × {D, G, C}. μ(q_i,a_j)=(q_k,a_l,d_m) signifie qu'on effectue les actions de remplacement, de déplacement et de changement d'état en q_k pour la configuration courante d'état et de symbole.

La suite S₁(q₁), ..., S_n(q_m) d'états (configurations) successifs du ruban et du programme lors de l'exécution d'une machine de Turing T_μ, est appelée calcul. Si S₁ est la chaîne initiale et S_n une chaîne terminale alors S_n est aussi appelée résultat du calcul de S₁ par la machine T_μ.

2.2. Cas particuliers de machine de Turing

Les différents types d'automates sont des cas particuliers de la machine de Turing. Parmi ceux-ci, on trouve les automates : linéairement bornés, à pile, finis...

Les automates finis sont des machines de Turing très spécifiques. Leurs caractéristiques, leur manipulation et leurs applications sont présentés en détail dans la suite du chapitre.

2.3. Machine de Turing et la théorie des langages

La machine de Turing manipule des symboles. Ceci n'est pas restrictif car tous les problèmes calculables (pour lesquels il existe un algorithme permettant de les résoudre dans un temps fini) peuvent se ramener à la manipulation de symboles et donc peuvent être programmés sur une machine de Turing.

Dans le cadre de la théorie des langages, la correspondance est évidente. Les machines de Turing sont alors appelées accepteurs ou reconnaisseurs [Aho et al. 91] [Ginzburg 68].

Soit A un alphabet et A* l'ensemble des mots que l'on peut construire avec les symboles de A. Une chaîne (mot) awb (a et b ∈ A et w ∈ A*), écrite sur le ruban et entourée de caractères ε, est acceptée si la machine part de la position gauche (i.e. dans la configuration initiale (I,a)) et s'arrête avec la tête de lecture placée après le caractère le plus à droite différent de ε dans un état final (i.e. dans la configuration finale (q_f,b) avec q_f ∈ F). Si elle s'arrête dans un état n'étant pas final alors la chaîne est refusée.

Le langage défini par un accepteur est l'ensemble des chaînes (mots) qu'il accepte. Il existe donc une correspondance entre les grammaires (et les langages) et les machines de Turing (cette correspondance sera étudiée en détail plus loin). Une machine de Turing (ou un automate) est donc alors vue comme l'implémentation d'une fonction f telle que :
f : A* → {Accepté, Refusé}.

vendredi, 19/09/03 21:42