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
Dédidabilité
Problème décidable en informatique : Il existe un algorithme de longueur finie et de temps d'exécution fini qui répond oui ou non à la question posée.
Exercice 1
- Le problème de savoir si 442 est pair est-il décidable ?
- Le problème de savoir si 443 est premier est-il décidable ?
On parle aussi d'ensemble décidable. Un ensemble est décidable quand la question de savoir si tel élément appartient à l'ensemble est un problème décidable.
Exercice 2
- L'ensemble des nombres pairs est-il décidable ?
- L'ensemble des nombres premiers est-il décidable ?
On utilise parfois le terme ensemble récursif au lieu de ensemble décidable. Dans ce sens, récursif n'a absolument rien à voir avec l'idée de fonction récursive qui s'appelle elle-même. Ces termes sont très utilisés dans la théorie des langages informatiques qui est à la base de notions importantes comme les expressions régulières ou encore la conception de langages de programmation.
Calculabilité
Dans les années 1930, Alonzo Church (1903 - 1995) invente le $\lambda$-calcul. C'est un langage informatique théorique ou tout est fonction. Les langages de programmation Lisp, Haskell, oCaml sont influencés par le $\lambda$-calcul.
Church et son équipe étudient la calculabilité. Une fonction $f$ est calculable si le calcul de $f(x)$ se termine en un nombre fini d'étape.
Calculabilité et décidabilité
La notion est liée à la décidabilité. En effet, soit $E$ un ensemble. On peut toujours définir la fonction $f_E$ telle que $f_E(x) = V \Leftrightarrow x \in E$. Si $f_E$ est calculable, alors on peut décider si $x \in E$ et alors $E$ est décidable.
Les travaux de Church précèdent de peu ceux de Turing mais ils finiront par travailler ensemble.
Nous allons poursuivre avec les machines de Turing bien que historiquement, les résultats qui nous intéressent ont d'abord été formulés dans le cadre du $\lambda$-calcul de Church. Les deux approches sont équivalentes.
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.