Chapitre 0 - Un peu de théorie
En informatique une fonction est calculable s'il existe un algorithme permettant d'effectuer le calcul (pour toute entrée) de la fonction en un nombre fini d'étapes.
On dit également qu'un problème est décidable s'il existe un algorithme capable de résoudre le problème en un nombre fini d'étapes.
Pendant très longtemps les mathématiciens ont considérés (intuitivement) que tout problème avait une solution, et qu'il suffisait de trouver la méthode qui permettrait de résoudre le problème.
Puis la question s'est naturellement posée notamment lors de la publication des 23 problèmes (1900) de David Hilbert.
Certains d'entre eux ne sont toujours pas résolus comme la conjecture de Goldbach qui affirme que tout nombre entier pair supérieur à 3 peut s'écrire comme la somme de deux nombres premiers (12 = 5 + 7).
Depuis les travaux de Kurt Gödel (1931) et d' Alan Turing (1936), on sait maintenant qu'il existe une infinité de problèmes non décidables (de fonctions non calculables).
Ces travaux ont conduit à déterminer les contours de ce qui est faisable ce qui a permis à l'informatique de naître.
La machine de Turing
Alan Turing est l'un des grands esprits scientifiques du XXème siècle.
Peu d'autres ont abordé, avec autant de succès, des domaines aussi variés. Mathématicien, héros (longtemps oublié) de la Seconde Guerre mondiale, il contribue à la victoire des Alliés en cassant les codes allemands... Pionnier de l'informatique, il conçoit un des premiers programmes informatiques, la fameuse "machine de Turing".
Le problème de l'arrêt
La décidabilité est une notion fondamentale en logique et en informatique théorique, depuis longtemps, on croyait que tout problème mathématique est décidable jusqu'à la preuve d'Alan Turing avec le problème dit de l'arrêt.
le principe de la preuve
Supposons l'existence d'un algorithme AH qui permet de savoir si un algorithme A s'arrête ou pas
On considère alors l'algorithme B, qui n'existe que si AH existe.
B prend en entrée un algorithme A, puis exécute AH sur A.
Si A s'arrête alors B entre dans une boucle infinie
Sinon B s'arrête en affichant par exemple "stop"
B étant un algorithme on peut donc effectuer B(B)
Conclusion
B s'arrête si B ne s'arrête pas et B ne s'arrête pas si B s'arrête .
Ces contradictions prouve que B n'existe pas et donc que AH n'existe pas
Les théorèmes d'incomplétude de Gödel
Pour en savoir davantage sur les travaux de Kurt Gödel