Chapitre 15 : Calculabilité, décidabilité.
🕐 Historique:
Alan Turing est souvent vu comme le père de l'informatique.
Quelques dates clés :
- 1912 : Naissance d'Alan Turing à Londres.
- 1936 : Publication de "On Computable Numbers", où il introduit la machine de Turing, posant les bases de l'informatique moderne.
- 1940-1945 : Travaille à Bletchley Park pendant la Seconde Guerre mondiale, où il contribue à décrypter la machine Enigma.
- 1950 : Propose le test de Turing dans un article sur l'intelligence artificielle, pour évaluer si une machine peut imiter l'intelligence humaine.
- 1952 : Condamné pour homosexualité et forcé à subir une castration chimique.
- 1954 : Mort d'Alan Turing, officiellement par suicide, bien que les circonstances restent débattues.
1. Tout programme peut être une donnée:
Tout programme peut être vu comme une donnée :
- On peut le stocker dans un fichier.
- Un programme dans un langage informatique est soit un langage interprété, soit un langage compilable.
- Un système d'exploitation est un programme qui manipule d'autres programme.
Cette précision est là pour bien mettre en avant que de nos jours qu'un algorithme est programmable et n'est donc pas induit dans la conception de la machine elle même. On fait ainsi la différence, par exemple, entre une horloge mécanique et une montre programmée informatiquement.
2. Church-Turing
Dans les années 1930, les travaux des mathématiciens Alonso Church et Alan Turing ont permis d'éclaircir ce qu'est un programme basés sur des calculs.
3.Machine de Turing
Une machine de Turing est une machine conceptualisée par Alan Turing. C'est une machine imaginaire que l'on peut représenter ainsi:
- Cette machine dispose d'un ruban composé de symboles (par exemple de 0 ou 1) .
- Cette machine dispose d'une tête de lecture et d'écriture et elle dispose d'un état qui est précisé ( par exemple 0 ou 1).
- La tête de lecture peut se déplacer vers la gauche ou vers la droite.
- La machine dispose d'une table de transition. Elle contient les instructions suivants les états de la tête de lecture et ce qui est lu sur le ruban où se trouve la tête de lecture.
4. Exercice
A faire dans le cahier.
On possède la table de transition suivante.
| Etat | Valeur lue | Ecriture | Direction | Nouvel état |
|---|---|---|---|---|
| 0 | vide | vide | gauche | 1 |
| 0 | 0 | 0 | droite | 0 |
| 0 | 1 | 1 | droite | 0 |
| 0 | 2 | 2 | droite | 0 |
| 0 | 3 | 3 | droite | 0 |
| 0 | 4 | 4 | droite | 0 |
| 0 | 5 | 5 | droite | 0 |
| 0 | 6 | 6 | droite | 0 |
| 0 | 7 | 7 | droite | 0 |
| 0 | 8 | 8 | droite | 0 |
| 0 | 9 | 9 | droite | 0 |
| 1 | 0 | 1 | gauche | 2 |
| 1 | 1 | 2 | gauche | 2 |
| 1 | 2 | 3 | gauche | 2 |
| 1 | 3 | 4 | gauche | 2 |
| 1 | 4 | 5 | gauche | 2 |
| 1 | 5 | 6 | gauche | 2 |
| 1 | 6 | 7 | gauche | 2 |
| 1 | 7 | 8 | gauche | 2 |
| 1 | 8 | 9 | gauche | 2 |
| 1 | 9 | 0 | gauche | 1 |
| 1 | Vide | 1 | STOP | |
| 2 | 0 | 0 | gauche | 2 |
| 2 | 1 | 1 | gauche | 2 |
| 2 | 2 | 2 | gauche | 2 |
| 2 | 3 | 3 | gauche | 2 |
| 2 | 4 | 4 | gauche | 2 |
| 2 | 5 | 5 | gauche | 2 |
| 2 | 6 | 6 | gauche | 2 |
| 2 | 7 | 7 | gauche | 2 |
| 2 | 8 | 8 | gauche | 2 |
| 2 | 9 | 9 | gauche | 2 |
| 2 | Vide | Vide | STOP |
Appliquer la table de transition ci-dessus sur le ruban suivant :
| 2 | 3 | 5 |
L'initialisation se fait sur la case 2 avec pour état 0.
5. Exercice
A faire dans le cahier.
Refaire l'exercice 4 avec le ruban suivant :
| 2 | 9 | 9 |
L'initialisation se fait sur la case 2 avec pour état 0.
6. Exercice
Refaire l'exercice 4 avec le ruban suivant :
A faire dans le cahier.
| 9 | 9 | 9 |
L'initialisation se fait sur le tout premier 9 avec pour état 0.
7. Exercice
A faire dans le cahier.
On considère le ruban suivant :
| 1 | 1 | 0 | 1 | 1 |
Ecrire une table de transition permettant de remplacer le 0 par un 1.
L'initialisation se fait sur la case vide la plus à gauche. Le programme s'arretera sur cette même case.
8. Exercice
A faire dans le cahier.
On considère le ruban suivant :
| 1 | 1 | 0 | 1 | 1 |
Ecrire une table de transition permettant de remplacer le 0 par un 1 et réciproquement puis de rajouter un 1 à l'avant dernière case.
L'initialisation se fait sur le tout premier 1 et le programme stoppera sur la case vide la plus à droite.
9. Thèse de Church-Turing
Tout traitement réalisable mécaniquement peut-être accompli par une machine de Turing.
10. Calculabilité
Un problème est dit calculable s'il existe une machine de Turing permettant de le résoudre.
La calculabilité d'un algorithme est donc indépendante du langage de programmation.
On peut par exemple calculer les décimales de \(\pi\) avec une machine de Turing
11. Décidabilité
Un problème est dit décidable s'il existe une machine de Turing permettant de le résoudre en un temps fini (même si c'est un milliard d'années...).
12. Le problème de l'arrêt
On peut se poser la question s'il est possible de savoir si un problème (un algorithme) s'arrêtera.
Est-il possible d'écrire un algorithme permettant de voir si n'importe quel autre algorithme s'arrête ou non?
Raisonnons par l'absurde :
Imaginons que ce programme que l'on appellera \(A\) existe.
Si on lui donne un programme \(P\) quelconque, alors \(A(P)=VRAI\) si le programme P s'arrête et \(A(P)=FAUX\) si le programme P ne s'arrête pas.
Regardons maintenant un programme \(B\) qui est définit de la manière suivante :
- Il prend un programme \(P\) puis évalue \(A(P)\).
- Si \(A(P)\) est \(VRAI\), il lance une boucle infinie.
- Si \(A(P)\) est \(FAUX\), il s'arrête.
Regardons \(B(B)\)
- Si \(B(B)\) s'arrête , c'est que \(A(P)\) était \(FAUX\) et donc il ne s'arrêtait pas.
- Si \(B(B)\) ne s'arrête pas , c'est que \(A(P)\) était \(VRAI\) et donc qu'il s'arrêtait.
\(B\) ne peut pas exister donc A non plus.