Calculabilité, décidabilité et programme en tant que donnée
Complétez de mémoire, puis vérifiez avec la page de corrigé.
Un ordinateur peut-il tout calculer ? Peut-on écrire un programme qui détecte si n'importe quel autre programme va boucler à l'infini ? Alan Turing a montré en 1936 que la réponse est non : il existe des problèmes qu'aucun algorithme ne peut résoudre.
Un programme est une donnée
Règle
Calculabilité
Définition — fonction calculable :
Règle
Le problème de l'arrêt
Définition — problème de l'arrêt :
Règle
Exemple
Pourquoi un antivirus ne peut-il pas détecter à coup sûr tout comportement malveillant ?
6.
7.
8.
Résultat :
Piège
Croire qu'indécidable signifie très long à calculer.
Distinguer « difficile » et « impossible ».
Raisonner par l'absurde sur l'arrêt
10.
11.
12.
13.
Ai-je défini le vocabulaire ?
Mon code est-il testé sur un exemple ?
Ai-je traité les cas limites ?
Ai-je justifié la complexité ou le résultat ?
Corrigé · à détacher
Calculabilité, décidabilité et programme en tant que donnée
1.Un programme est un texte, donc une donnée qu'un autre programme peut lire, analyser ou exécuter : c'est ce que font un interpréteur (Python), un compilateur, un antivirus ou un système d'exploitation qui lance une application.
2.Fonction qu'un algorithme peut calculer en un nombre fini d'étapes, quelle que soit l'entrée.
3.Ce qui est calculable ne dépend pas du langage de programmation : Python, C ou une machine de Turing calculent les mêmes fonctions (thèse de Church-Turing).
4.Déterminer, pour tout programme P et toute entrée e, si P s'arrête sur e. Turing a démontré en 1936 qu'aucun programme ne peut le résoudre : il est indécidable.
5.Idée de la preuve : si un programme arret(P, e) existait, on construirait un programme paradoxe(P) qui boucle quand arret(P, P) répond vrai et s'arrête sinon ; paradoxe(paradoxe) mène alors à une contradiction.
6.Prévoir le comportement d'un programme quelconque revient à des problèmes comme celui de l'arrêt.
7.Ces problèmes sont indécidables en général.
8.L'antivirus utilise donc des signatures et des heuristiques, sans garantie absolue.
9.L'indécidabilité impose des limites théoriques aux outils qui analysent des programmes.
10.Supposer qu'un programme arret existe.
11.Construire paradoxe qui fait l'inverse de ce que prédit arret.
12.Appliquer paradoxe à lui-même.
13.Conclure à la contradiction : arret n'existe pas.