Table des matières
Machines de Turing
Machine de Turing
La machine est constituée :
- d'une liste de symboles autorisés,
- d'une bande potentiellement infinie
des symboles sont écrits sur la bande au début, mais sur une zone finie de la bande - une tête de lecture/écriture qui permet de lire le symbole en cours et si on le souhaite d'en écrire un autre
- à chaque cycle, la machine est dans un certain état.
Il y a l'état initial, l'état final, et d'autres états, autant que l'on veut mais en nombre fini - un programme, de taille finie
Le programme de la machine ci-dessus est constitué de 5 lignes :
| S:état | L:Lu | E:écrire | M:mouvement | N:nouvel état |
|---|---|---|---|---|
| 0 | 1 | X | >:droite | 0 |
| 0 | _:vide | *:rien | <:gauche | 1 |
| 0 | *:tous | 0 | > | 0 |
| 1 | _ | * | > | H:halt |
| 1 | * | * | > | 1 |
La première ligne signifie : Si la machine est dans l'état 0 et qu'on lit le caractère 1, alors il faut écrire le caractère X puis aller à droite (la tête de lecture/écriture va à droite, donc la bande va à gauche…) et on reste dans l'état 0.
À quoi sert cette machine ?
La machine de Turing fait penser à un ordinateur primitif. Mais elle ne sert pas à fabriquer un ordinateur. La machine de Turing est une machine abstraite que l'on n'essaie même pas de fabriquer. Elle sert seulement à réfléchir sur les algorithmes, à dire ce qui est possible et ce qui ne l'est pas.
Tout algorithme, peut trouver un équivalent sous forme d'une machine de Turing. Cette machine est peut-être énorme, chère, pas efficace… ou encore trop grosse pour être réalisée avec ce dont on dispose sur Terre. Mais l'important est qu'elle soit théoriquement réalisable.
Si un problème n'est pas faisable avec une machine de Turing, alors aucun algorithme fini n'en viendra à bout, quelque soit la technologie utilisée.
La machine permet de donner une nouvelle définition de la calculabilité : Un fonction est calculable s'il est possible de réaliser une machine de Turing exécutant cette fonction.
Turing - complet : un langage est dit ou une machine est dit Turing - complet s'il permet de réaliser la même chose qu'une machine de Turing. Un ordinateur moderne est Turing complet.
Des exemples le machines de Turing
Exercice 3
| État en cours | Symbole lu | Écrire | Mouvement | État suivant |
|---|---|---|---|---|
| init | 1 | 0 | droite | init |
| init | 0 | 1 | droite | init |
| init | _ | _ | gauche | retour |
| retour | 1 | 1 | gauche | retour |
| retour | 0 | 0 | gauche | retour |
| retour | _ | _ | droite | fin |
Supposons que sur la bande magnétique, on ait écrit [1]10010010.
[] représente la position de la tête de lecture.
- Qu'est-il écrit sur la bande à la fin de l'exécution ?
- Simuler l'exécution sur le site http://morphett.info/turing/
- On utilise le symbole
*pour dire, dans la colonne lecture, n'importe quel caractère et, dans la colonne écriture, ne rien changer - En général, on fait commencer la machine au début du mot écrit sur la bande et on fait en sorte que la machine revienne à la même position quand elle s'arrête.
Exercice 4
Les symboles écrits sur la bande forment un mot. Ce mot peut être compris comme un nombre. Par exemple 110010 est l'écriture binaire de 50.
- Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $2\cdot n$
- Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $2\cdot n + 1$
- Concevez la machine qui, partant de l'écriture binaire d'un nombre $n$, termine avec l'écriture binaire de $n + 1$. C'est plus difficile !
Les machines évoquées ci-dessus semblent n'avoir besoin que des symboles 0 et 1. Toutefois, on a le droit d'insérer des symboles en plus, dans le déroulement de l'exécution. Par exemple, il est courant d'utiliser le symbole #. Dans le déroulement, # est écrit. Avant la fin, il est effacé.
Exercice 5
Concevez un programme qui commence avec un nombre binaire $u$ et qui termine avec $u$ écrit à l'envers.
Par exemple 11010 termine avec 01011.
Définition théorique
Ce qui est dit là sort largement du programme de NSI
Comme on l'a dit, les machines de Turing sont des concepts abstraits. Quand on veut les utiliser pour prouver des choses, on a besoin d'une formalisation très rigoureuse qui a tout d'une formalisation mathématique. Ainsi, on définira une machine par :
- un ensemble fini $\Sigma$ contenant les symboles nécessaires pour représenter les données traitées par la machine 0 et 1 dans les exemples précédents ;
- un ensemble fini $\Gamma$, l'alphabet de ruban, qui contient $\Sigma$ et d'autres symboles dont au moins le symbole vide
_; - un ensemble fini $Q$, les états ;
- un élément $i \in Q$, l’état initial ;
- un élément $f \in Q$, l’état final ;
- une fonction $\delta : (Q \setminus \lbrace f \rbrace) \times \Gamma \to \Gamma \times \{-1, 0, +1\} \times Q$, la table de transition.