Peut-on écrire un programme qui détecte tous les programmes qui tournent en boucle infinie ?
Turing a démontré en 1936 qu'aucun programme ne peut décider, pour tout programme et toute entrée, s'il s'arrête. Si un tel programme « arrete » existait, on construirait un programme « paradoxe » qui boucle quand arrete dit qu'il s'arrête : appliqué à lui-même, il mène à une contradiction.
Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.
Pourquoi cette question : un modèle d'introduction
Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.
Il m'est souvent arrivé d'écrire en NSI une boucle qui ne s'arrêtait jamais, et je devais interrompre le programme. Je me suis demandé pourquoi l'éditeur ne me prévenait pas à l'avance. J'ai découvert qu'Alan Turing avait démontré, avant même l'existence des ordinateurs, qu'un tel détecteur universel est impossible. La preuve, par l'absurde, tient en quelques lignes et m'a fasciné.
L'enjeu et les notions du programme
Démontrer par l'absurde une limite fondamentale de l'informatique, en utilisant un raisonnement autoréférent.
Mathématiques
- Raisonnement par l'absurde (seconde)
- Logique : implication, négation (seconde)
- Fonctions : un programme vu comme une fonction (seconde)
Numérique et sciences informatiques
- Calculabilité, décidabilité, problème de l'arrêt (terminale)
- Programme en tant que donnée (terminale)
Le plan de l'exposé en 9,5 min
1. Introduction
1 minUn programme peut s'arrêter ou tourner indéfiniment selon son entrée. Problématique : peut-on écrire un programme « arrete(P, x) » qui renvoie Vrai si le programme P s'arrête sur l'entrée x, et Faux sinon, pour tous les programmes ?
2. NSI : un programme est une donnée
2,5 minUn programme est un texte : on peut le donner en entrée à un autre programme. C'est ce que font un compilateur, un antivirus ou un correcteur automatique. On peut donc imaginer appeler arrete(P, P) : le programme P s'arrête-t-il quand on lui donne son propre code en entrée ?
Pour certains programmes, la question est facile (une boucle « tant que Vrai » sans sortie ne s'arrête jamais). La question de Turing est de savoir si une méthode unique fonctionne pour tous.
3. Mathématiques : la preuve par l'absurde
4,5 minSupposons qu'un programme arrete existe et réponde toujours correctement. On écrit le programme paradoxe(P) : si arrete(P, P) renvoie Vrai, alors boucler indéfiniment ; sinon, s'arrêter.
Que fait paradoxe(paradoxe) ? Premier cas : il s'arrête. Alors arrete(paradoxe, paradoxe) renvoie Vrai, donc paradoxe boucle : contradiction. Second cas : il ne s'arrête pas. Alors arrete renvoie Faux, donc paradoxe s'arrête : contradiction.
Les deux cas sont impossibles, donc l'hypothèse est fausse : aucun programme arrete n'existe. Le problème de l'arrêt est indécidable.
La structure rappelle le paradoxe du menteur (« cette phrase est fausse ») et l'argument diagonal de Cantor : on construit un objet qui contredit ce qu'on dit de lui-même.
4. Conclusion
1,5 minAucun programme ne peut détecter toutes les boucles infinies : la supposition contraire mène à une contradiction. L'informatique a des limites démontrables, indépendantes de la puissance des machines. En pratique, les outils détectent beaucoup de cas particuliers. J'ouvre sur le théorème de Rice : aucune propriété non triviale du comportement des programmes n'est décidable en général.
Ce que j'écris au tableau
Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.
paradoxe(paradoxe) s'arrête ⇔ arrete renvoie Faux ⇔ paradoxe(paradoxe) ne s'arrête pas
Conclusion : la réponse à la question
Le problème de l'arrêt est indécidable : un raisonnement par l'absurde de quelques lignes le prouve pour toujours. C'est l'un des résultats fondateurs de l'informatique théorique.
Les questions probables du jury
Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.
Qu'est-ce qu'un raisonnement par l'absurde ?
On suppose le contraire de ce qu'on veut prouver et on aboutit à une contradiction.
Peut-on décider l'arrêt pour certains programmes ?
Oui, pour beaucoup de cas particuliers ; c'est la méthode générale, valable pour tous, qui est impossible.
Pourquoi un antivirus ne peut-il pas être parfait ?
Décider si un programme aura un comportement malveillant est indécidable en général, comme l'arrêt.
Quel lien avec le paradoxe du menteur ?
Les deux construisent un énoncé ou un programme qui parle de lui-même pour se contredire.
Une machine plus puissante changerait-elle le résultat ?
Non : la preuve ne dépend ni du temps ni de la mémoire disponibles.
Les pièges qui coûtent des points
- Croire que le résultat dit qu'on ne peut jamais savoir si un programme s'arrête.
- Oublier d'examiner les deux cas de la contradiction.
- Confondre « très long à calculer » et « indécidable ».
Revoir les notions
Autres questions : logique et calculabilité
- Existe-t-il des nombres qu'aucun programme ne pourra jamais calculer ?
- Combien de fonctions logiques différentes peut-on construire avec n entrées, et peut-on toutes les réaliser avec ET, OU, NON ?
- Pourquoi « non (a et b) » ne veut-il pas dire « non a et non b », et pourquoi cette erreur cause-t-elle tant de bugs ?
- Comment démontrer qu'un algorithme avec une boucle donne toujours le bon résultat ?
Préparer l'oral, pas seulement le contenu
Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.
Méthode : traiter une question de Grand oral →