Machines de turing

Machines de Turing

Si votre navigateur affiche mal les symboles spéciaux de HTML, voici une version sans symbole spécial.

Introduction

Une machine de Turing se compose d'une partie de contrôle et d'une bande infinie sur laquelle se trouvent écrits des symboles. La partie de contrôle est constituée d'un nombre fini d'états possibles et de transitions qui régissent les calculs de la machine. Les symboles de la bandes sont lus et écrits par l'intermédiaire d'une tête de lecture.

Fig. 1 : machine de Turing

Les machines de Turing sont une abstraction des ordinateurs. La partie de contrôle représente le microprocesseur. Un élément essentiel est que le nombre d'états est fini. Ceci prend en compte que les microprocesseurs possèdent un nombre déterminé de registres d'une taille fixe et que le nombre de configurations possibles est fini. La bande représente la mémoire de l'ordinateur. Ceci comprend la mémoire centrale ainsi que les mémoires externes telles les disques durs. La tête de lecture représente la bus qui relie le microprocesseur à la mémoire. Contrairement à un ordinateur, la mémoire d'une machine de Turing est infinie. Ceci prend en compte qu'on peut ajouter des disques durs à un ordinateur de façon (presque) illimitée. Une autre différence entre une machine de Turing et un ordinateur est que l'ordinateur peut accéder à la mémoire de manière directe (appelée aussi aléatoire) alors que la tête de lecture de la machine de Turing se déplace que d'une position à chaque opération.

Le contrôle de la machine est constitué d'un nombre fini d'états { q₀, ..., q_n }. À chaque instant, la machine se trouve dans un de ces états. Au départ, la machine se trouve dans l'état q₀ qu'on appelle état initial. Le calcul d'une machine de Turing est formé d'une suite d'étapes de calcul qui sont effectuées par la machine. Chaque étape consiste à changer l'état de contrôle, écrire un symbole sous la tête de lecture et déplacer la tête de lecture. Les étapes de calcul possibles sont décrites par les transitions de la machine.

Définition

Nous donnons maintenant la définition précise d'une machine de Turing. De manière formelle, une machine de Turing M est un septuplet (Q, Sigma, Gamma, E, q₀, F, #) où

Q: est l'ensemble des états de contrôle. C'est un ensemble fini { q₀, ..., q_n }.
Sigma: est l'alphabet d'entrée. C'est un ensemble fini de symboles qui ne contient pas le symbole blanc #. Cet alphabet est utilisé pour écrire la donnée initiale sur la bande.
Gamma: est l'alphabet de bande. C'est un ensemble fini qui comprend tous les symboles qui peuvent être écrits sur la bande. Ceci inclut bien sûr l'alphabet d'entrée Sigma et le symbole blanc #.
E: est un ensemble fini de transitions de la forme (p, a, q, b, x) où p et q sont des états, a et b sont des symboles de bande et x est un élément de {L, R}. Une transition (p, a, q, b, x) est aussi notée p, a -> q, b, x.
q₀: est l'état initial. C'est un état particulier de Q dans lequel se trouve machine au début d'un calcul.
F: est l'ensemble des états finaux appelés aussi états d'acceptation
#: est le symbole blanc qui, au départ, remplit toutes les positions de la bande autres que celles contenant la donnée initiale.

Une machine de Turing est déterministe si pour tout état p et tout symbole a, il existe au plus une transition de la forme p, a -> q, b, x. Lorsque la machine est déterministe, l'ensemble E de transitions est aussi appelé fonction de transition et est noté delta. La fonction delta associe à chaque paire (p, a) l'unique triplet (q, b, x), s'il existe, tel que p, a -> q, b, x soit une transition. Lorsque la machine n'est pas déterministe, l'ensemble E peut encore être vu comme une fonction delta. Dans ce cas, la fonction delta associe à chaque paire (p, a) l'ensemble des triplets (q, b, x) tels que p, a -> q, b, x soit une transition.

À la place de L et de R, on utilise parfois les flèches <- et -> pour désigner les déplacements de la tête de lecture. C'est en particulier le cas sur certaines figures.

Description

Une machine de Turing est décrite en donnant explicitement les sept éléments Q, Sigma, Gamma, E, q₀, F et #. Afin de rendre plus simple l'énumération des transitions de E, celles-ci sont souvent données sous la forme d'un tableau ou sous la forme d'un diagramme similaire à celui d'un automate.

Lorsque E est décrit sous la forme d'un tableau, ce tableau possède une ligne pour chaque état et une colonne pour chaque symbole. La case à l'intersection de la ligne de l'état p et de la colonne du symbole a contient tous les triplets (q,b,x) tel que p, a -> q, b, x est une transition. Si la machine est déterministe, chaque case du tableau contient au plus un triplet. Lorsque E est décrit sous la forme d'un diagramme, ce dernier représente un graphe dont les sommets sont les états de la machine. Le graphe possède une arête de l'état p à l'état q étiquetée par a, b, x si p, a -> q, b, x est une transition de la machine.

Pour illustrer ces deux méthodes, nous allons décrire la même machine très simple à l'aide des deux méthodes. Soit M la machine ({0}, {a, b}, {a, b, #}, E, 0, {0}, #). La machine M possède donc un unique état 0 qui est initial et final. Son alphabet d'entrée Sigma contient les deux symboles a et b et son alphabet de bande Gamma contient en plus le symbole blanc #. L'ensemble E contient les trois transitions

0, a -> 0, #, R 0, b -> 0, #, R 0, # -> 0, #, L.

Ces trois transitions sont aussi décrites par le tableau suivant. Ce tableau a une seule ligne qui correspond à l'unique état et trois colonnes qui correspondent à chacun des symboles de l'alphabet de bande.

Tableau des transitions.
E	a	b	#
0	0, #, R	0, #, R	0, #, L

Ces trois transitions sont aussi décrites par le diagramme de la figure ci-dessous. Les petites flèches entrante et sortante de l'état 0 marquent qu'il est respectivement initial et final.

Fig. 2 : Diagramme des transitions

Configurations et calculs

Le principe global de fonctionnement d'une machine de Turing est le suivant. Une entrée, c'est-à-dire un mot fini sur l'alphabet d'entrée, est écrit sur la bande la machine. Le reste de la bande est rempli avec le symbole blanc. La tête de lecture est placée sur le premier symbole du mot d'entrée. Ensuite, la machine commence son calcul jusqu'à arriver éventuellement dans un état où elle accepte l'entrée.

Pour décrire le fonctionnement précis d'une machine de Turing, il est nécessaire d'introduire la notion de configuration. Une configuration d'une machine de Turing est l'état global de la machine à un instant donné. Elle comprend

l'état de contrôle qui est un élément de Q,
le contenu de la bande,
la position de la tête de lecture sur la bande.

Si la machine se trouve dans un état q, la configuration est écrite uqv où u est le contenu de la bande (strictement) à gauche de la tête de lecture et v est le contenu de la tête à droite de la tête de lecture (cf. la figure ci-dessous). Le symbole sous la tête de lecture est donc le premier symbole de v. Quand on décrit une configuration de la machine, les symboles blancs qui se trouvent dans la partie infinie à droite de la bande sont omis. Ceci permet de décrire une configuration de façon finie. Si par exemple, la machine de la figure 1 se trouve dans l'état q, sa configuration est abAaaBAbqabbbBA parce que le contenu de la bande avant la tête de lecture est abAaaBAb et que le contenu après la tête de lecture est abbbBA suivi de symboles blancs. Tous les symboles # à droite sont sous-entendus et ne sont pas écrits.

Fig. 3 : Configuration abAaaBAbqabbbBA

Au départ, la bande contient la donnée initiale et la tête de lecture se trouve sur la première position de la bande. La configuration initiale s'écrit donc q₀w où q₀ est l'état initial et w est la donnée initiale.

Un calcul d'une machine de Turing se décompose en étapes. Une étape d'un calcul consiste à passer d'une configuration à une autre configuration en appliquant une des transitions de l'ensemble E. Une étape de calcul comprend les trois actions suivantes.

changer l'état de contrôle
écrire un symbole à la place du symbole sous la tête de lecture
déplacer sa tête de lecture d'une position vers la gauche ou la droite

Une transition de la forme p, a -> q, b, x peut uniquement être appliquée si la machine se trouve dans l'état p et si le symbole sous la tête de lecture est a. Après application de cette transition, la machine se trouve dans l'état q, le symbole a est remplacé sur la bande par b et la tête de lecture se déplace d'une position vers la gauche si x = L (Left) ou d'une position vers la droite si x = R (Right).

On note C => C' une étape de calcul qui fait passer la machine d'une configuration C à une configuration C' en appliquant une transition de E. On alors les étapes de calcul suivantes où u et v sont des mots quelconques sur l'alphabet de bande.

ucpav => uqcbv si p, a -> q, b, L est une transition
upav => ubqv si p, a -> q, b, R est une transition

Il faut noter qu'une transition de la forme p, a -> q, b, L (avec déplacement de la tête de lecture vers la gauche) peut uniquement être appliquée si la tête de lecture ne se trouve pas sur le premier symbole de la bande.

Le fait que la présence de symboles blancs est implicite à la fin de la configuration implique que l'on a aussi les étapes de calcul suivantes où u est un mot quelconque sur l'alphabet de bande.

ucp => uqcb si p, # -> q, b, L est une transition
up => ubq si p, # -> q, b, R est une transition

Ces relations concernent les cas où la tête de lecture se trouve sur un des symboles blancs implicites à la fin de la configuration.

Un calcul de la machine de Turing est une suite C₀, ..., C_n de configurations telles que

C₀ => C₁ => C₂ => ... => C_n-1 => C_n.

Ceci signifie que la machine peut passer de la configuration C_i à la configuration C_i+1, c'est-à-dire C_i => C_i+1 pour tout 0 <= i < n. Ceci est noté C₀ =>^* C_n en abrégé (la relation =>^* est en fait la clôture réflexive et transitive de la relation =>).

Exemple

Les notions précédentes sont illustrées à l'aide de la machine de Turing M = ({0}, {a, b}, {a, b, #}, E, 0, {0}, #) avec les trois transitions suivantes.

0, a -> 0, #, R 0, b -> 0, #, R 0, # -> 0, #, L

Cette machine est simplissime et ne calcule rien de très intéressant. Son seul objectif est d'illustrer la notion de calcul.

Soit w = aba la donnée fournie à la machine. La configuration initiale est donc C₀ = 0aba. Les configurations suivantes sont données dans le tableau ci-dessous.

Calcul avec l'entrée aba.
Configuration	Commentaire
C₀ = 0aba	Configuration initiale
C₁ = #0ba	après application de la transition 0, a -> 0, #, R
C₂ = ##0a	après application de la transition 0, b -> 0, #, R
C₃ = ###0	après application de la transition 0, a -> 0, #, R
C₄ = ##0	après application de la transition 0, # -> 0, #, L
C₅ = #0	après application de la transition 0, # -> 0, #, L
C₆ = 0	après application de la transition 0, # -> 0, #, L

On obtient alors le calcul suivant.

0aba => #0ba => ##0a => ###0 => ##0 => #0 => 0

qui est constitué de six étapes. La dernière configuration est bloquante. Aucune transition ne peut plus être appliquée. La tête de lecture se trouve sur le premier symbole de la bande et la seule transition qui lit le symbole # donnerait un déplacement de la tête de lecture vers la gauche.

Calculs acceptants

Une configuration C est dite bloquante s'il n'existe pas de configuration C' telle que C => C'. Ceci signifie qu'aucune transition ne peut être appliquée sur la configuration C pour passer à une configuration C'. Une configuration uqv est dite acceptante si l'état q est acceptant (final). Un calcul C₀ =>^* C_n est dit acceptant si la première configuration C₀ est de la forme q₀w et si la dernière configuration C_n est acceptante.

Lorsqu'on considère une suite de configurations

C₀ => C₁ => C₂ => C₃ => ...

qui constituent le début d'un calcul, trois situations peuvent survenir.

Le calcul atteint une configuration acceptante. Il est alors acceptant.
Le calcul atteint une configuration bloquante. Il n'est alors pas acceptant.
Le calcul se poursuit de manière infinie sans jamais atteindre ni une configuration acceptante ni une configuration bloquante. Il n'est alors pas acceptant.

Exemple

Soit la machine M = ({0, 1, 2}, {a, b}, {a, b, #}, E, 0, {2}, #) avec les transitions données à la figure ci-dessous.

Fig. 4 : une autre machine de Turing

Le mot d'entrée w = abba conduit aux différents calculs suivants.

0abba => a1bba => ab1ba => abb1a => abba0: Ce calcul se bloque dans configuration abba0 et n'est pas acceptant
0abba => a1bba => 1abba => a0bba => ab0ba => abb0a => abba1 => abba#2: Ce calcul atteint l'état 2 et est donc acceptant
0abba => a1bba => ab1ba => a1bba => ab1ba ...: Ce calcul ne termine pas et n'est donc pas acceptant.

Le mot abba est donc accepté par la machine puisqu'au moins un de ces calculs est acceptant. Par contre le mot aa n'est pas accepté car le seul calcul possible est 0aa => a1a => aa0 qui n'est pas acceptant.

Utilisation

Il y a deux modes d'utilisation des machines de Turing. Le premier mode est d'utiliser une machine comme accepteur et le second est d'utiliser une machine comme un calculateur.

Dans le mode accepteur, on fournit un mot d'entrée à la machine et celle-ci répond par oui ou par non. Quand la machine répond oui, on dit que le machine accepte le mot. La machine définit alors l'ensemble des mots qui sont acceptés. Par convention, on dit que la machine accepte un mot w s'il existe au moins un calcul acceptant avec w comme entrée, c'est-à-dire qui commence avec la configuration q₀w. L'élément important de cette définition est qu'un seul calcul acceptant suffit pour que la machine accepte même si d'autres calculs bloquent ou n'atteignent jamais une configuration acceptante.

Dans le mode calculateur, on fournit un mot d'entrée à la machine et celle-ci retourne un ou plusieurs mots de sortie. Quand la machine ne donne toujours qu'un seul mot de sortie, elle calcule une fonction qui associe le mot de sortie au mot d'entrée. Les mots de sortie sont par convention les contenus de la bande des dernières configurations des calculs acceptants. On met donc le mot d'entrée sur la bande, la machine effectue un calcul jusqu'à ce qu'elle atteigne un état final et le contenu de la bande constitue alors un des mots de sortie. Comme il peut y avoir plusieurs calculs acceptants, il peut y avoir plusieurs mots de sortie. Dans le cas d'une machine déterministe, il y a au plus un seul calcul acceptant et donc au plus un seul mot de sortie.