Ceci est une ancienne révision du document !
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
Warning: Undefined variable $ml_array in /home/goupillf/wiki.goupill.fr/lib/plugins/svgembed/syntax.php on line 264
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.
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.