Machines de Turing

Ce modèle de calcul date de 1936 et est du à Turing. Historiquement, c'est le premier modèle "plutôt nformatique", et sûrement le modèle le plus connu. Une machine de Turing est constituée d'une ou plusieurs bandes de lecture/écriture et d'une unité de contrôle finie (une sorte d'automate fini). Chaque bande est divisée en cases, chaque case contenant un symbole d'un alphabet fini, fixé à priori. Les bandes sont infinies des deux côtés, dans le sens où il y a un nombre infini de cases à gauche et à droite de toute case. 0n dispose des têtes de lecture et écriture, permettant comme leur nom l'indique de lire le contenu d'une case et écrire des symboles de l'alphabet dans cette case.

La machine obtenue est une sorte d'automate, mais disposant de mérnoire infinie (par écriture sur les bandes). Donnons une définition formelle des machines de Turing:

Définition: une machine de Turing à k bandes est décrite par un septuplet (Q,T,I,,b,q_O,q_f). Les composantes de ce septuplet sont:

Q - un ensemble fini d'états de la machine.

T - un ensemble fini de symboles qu'on peu utiliser sur les bandes.

I - un sous-ensemble de l'ensemble des symboles, les symboles de données.

- la fonction de transition: c'est une fonction de QT^k vers Q(T {G,D,S})^k

b - un symbole, désignant le blanc, appartenant à T-I

q₀ - l'état initial

q_f - l'état final

Notes:

La fonction de transition décrit en fait le fonctionnement de la machine. En cas de lecture d'une certaine suite de données, on écrit sur les bandes ce qui correspond à la fonction de transition et on déplace les têtes de lecture/écriture de manière correspondante sur les différentes bandes. Ainsi G, D et S dénotent des déplacements à gauche, à droite ou stationnaire (pas de déplacement).

On impose que la fonction de transition soit définie partout. Dans l'état d'arrêt la machine accepte ou non (rejet) le mot d'entrée suivant que le ruban 'resultat' comporte (par exemple) 1(VRAI, accepte) ou 0(FAUX,rejet).

La machine accepte un langage si pour tout mot du langage, l'exécution de la machine atteint l'état d'arrêt avec 1 sur le ruban 'resultat'. Pour les mots qui ne sont pas du langage l'exécution peut être infinie ou atteindre l'état d'arrêt, dans ce dernier cas 'resultat' contient 0.

La machine décide le langage si elle atteint toujours l'état d'arrêt, le ruban 'resultat' contient 1 pour les mots du langage, 0 sinon.

 

Le temps de calcul d'une machine de Turing est une fonction de complexité T(n), qui dépend de n, la longueur des données en bits (cases). Formellement on définit T(n) comme le nombre maximum de transitions avec une entrée de longueur n.

Avant de continuer, nous donnons un exemple de machine de Turing. Il s'agit d'une machine à 3 bandes, ayant deux nombres sur les bandes 1 et 2 et écrivant leur somme sur la troisième bande (pour raison de simplicité, tout sera en base 2). On aura

Q={q₀ ,q₁,q_f}

T={0,1,b}

I={0,1}

La table de transitions est comme suit:

Etat	lecture	écriture	déplacement	nouvel état	remarques
q0	b1 b2 b3  0 0   0 1   1 0   1  1 0 b   1 b   b 0   b 1   b b	b1 b2 b3  b b 0 b b 1 b b 1 b b 0  b b 0 b b 1 b b 0 b b 1 b b b	b1 b2 b3  G G G G G G G G G G G G G S G G S G S G G S G G S S S	q0 q0 q1 q0 q0 q0 q0 q0 qf	sans retenue
q1	b1 b2 b3  0 0   0 1   1 0   1 1   0 b   1 b   b 0   b 1   b b	b1 b2 b3  b b 1 b b 0 b b 0 b b 1 b b 1 b b 0 b b 1 b b 0 b b 1	b1 b2 b3  G G G G G G G G G G G G S S G G S G S G G S G G S S G	q0 q1 q1 q1 q0 q1 q0 q1  qf	avec retenue

On n'a pas précisé la lecture sur la troisième bande, car il s'agit de la bande résultat, supposée vide (que des blancs) au départ.

Pour finir de décrire le fonctionnement de cette machine, il faut préciser qu'au début les têtes se trouvent sur le bit le plus à droite (la moins significative) des deux nombres, et qu'après l'exécution, les deux bandes sont vidés et la troisième bande contient le résultat, avec la tête de lecture/écrirure à gauche du résultat.

En ce qui conceme la complexité de cette rnachine, T(n), elle est en (n). En effet il suffit de lire les données pour finir l'exécution. On peut remarquer que cette complexité est optimale, car on ne peut pas avoir une complexité inférieure.

Variante de la machine de Turing

Dans la littérature on trouve plusieurs variantes de la machine de Turing. Ces modèles sont équivalents du point de vue de leur puissance de calcul. Les différents modèles se distinguent surtout selon les trois critères suivants:

- le nombre de bandes

- la nature des bandes

- le déterminisme ou non-déterminisme de la machine

Le nombre de bandes: on distingue les machines selon le nombre de bandes utilisés. Principalement on distinguera entre les rnachines à une bande et celles à plusieurs bandes.

La nature des bandes: on distingue les machines utilisant des bandes infinies des deux côtés et celles utilisant une bande infinie d'une côté seulement.

Le déterminisme ou non-déterminisme de la machine: le déterminisme de la machine est défini par le nombre de choix qu'on peut avoir dans la table de transitions. Dans le cas déterministe il s'agit bien sûr d'un choix unique. En ce qui concerne le cas non-déterministe divers auteurs considèrent plusieurs modèles, en permettant plusieurs transitions. Il existe une différence entre ces modèles, selon que l'on permet d'avoir plusieurs transitions sans aucune relation entre elles ou si on impose (dans le cas le plus restrictif) que deux transactions peuvent différer seulement en ce qui concerne le nouvel état. Nous adopterons cette version comme définition d'une machine non-deterministe. Cette version est aussi puissante que les autres, car en introduisant un nombre suffisant de nouveaux états, on peut transformer toute autre machine non-déterministe en une de ce type.

Dans la littérature on trouve d'autres distinctions aussi. Ainsi par exemple il existe un modèle de machine à plusieurs bandes, où les déplacements sont les mêmes sur toutes les bandes. Ce modèle encore a la mêrne puissance que les autres, car de façon évidente il est au moins aussi puissant que le modèle de la machine à une bande, et au plus aussi puissant que le modèle avec les déplacements indépendants et comme on prouver que ces deux modèles sont équivalent.

Une autre différence entre les modèles concerne le résultat. Comme on a vu au début de ce cours, on a plusieurs manières de définir des fonctions et en conséquence on a plusieurs modèles de machine. Ainsi on peut parler de machines qui "calculent", comme celle de l'exemple précédent. On peut aussi parler de machines qui reconaissent un langage. Comme ces deux approches sont fondamentalement équivalentes, on utilisera les deux en alternance.

Exercice:

Reconnaissance de palindrome.

Philippe Rolland : 21/03/98