Existe-t-il des nombres qu'aucun programme ne pourra jamais calculer ?

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.

En NSI, nous avons écrit des programmes qui calculent les décimales de √2 ou de π, aussi loin qu'on veut. Je me suis demandé si tout nombre pouvait être calculé ainsi. J'ai découvert que non, et la preuve combine deux idées : un programme est un texte, donc on peut les compter, et les réels sont « trop nombreux » pour être comptés, comme l'a montré Cantor.

L'enjeu et les notions du programme

Comparer deux ensembles infinis par une numérotation, et démontrer par l'argument diagonal qu'ils n'ont pas la même taille.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Un réel est calculable s'il existe un programme qui, pour tout $n$n, affiche ses $n$n premières décimales. $\sqrt{2}$sqrt2, $\pi$π et $e$e sont calculables. Problématique : tous les réels le sont-ils ?

2. 2. NSI : on peut numéroter les programmes

   3 min

   Un programme est un texte fini écrit avec un alphabet fini, par exemple les caractères du clavier. Avec un alphabet de $k$k caractères, il y a $k^n$kⁿ textes de longueur $n$n, un nombre fini.

   On range tous les textes par longueur croissante, puis par ordre alphabétique à longueur égale : d'abord ceux de longueur 1, puis 2, etc. Chaque texte reçoit un numéro, et donc chaque programme aussi. L'ensemble des programmes est « dénombrable » : on peut en faire une liste numérotée $P_1,P_2,P_3,\dots$P₁,P₂,P₃,…, même si elle est infinie.

3. 3. Mathématiques : l'argument diagonal de Cantor

   4 min

   Supposons qu'on puisse numéroter tous les réels de $[0;1[$[0;1[ : $x_1,x_2,x_3,\dots$x₁,x₂,x₃,…. On construit un réel $y=0,d_1{d}_2{d}_3\dots$y=0,d₁d₂d₃… : sa $n$n-ième décimale $d_n$dₙ vaut 5 si la $n$n-ième décimale de $x_n$xₙ n'est pas 5, et 4 sinon.

   Pour chaque $n$n, $y$y diffère de $x_n$xₙ à la $n$n-ième décimale : $y$y n'est aucun des $x_n$xₙ. Contradiction : la liste ne contenait pas tous les réels. (Le choix de 4 et 5 évite les écritures du type $0,0999\cdots =0,1$0,0999…=0,1.)

   Conclusion : les réels ne sont pas dénombrables. Comme chaque programme calcule au plus un réel, les réels calculables forment un ensemble dénombrable. Il reste donc des réels qu'aucun programme ne calcule. Et même, en un sens précis, « presque tous » les réels sont non calculables : ceux que nous savons nommer sont une infime exception.

4. 4. Conclusion

   1,5 min

   Il existe des nombres qu'aucun programme ne calculera jamais : les programmes se numérotent, les réels non. L'argument diagonal de Cantor, de 1891, fonde ainsi une limite de l'informatique. J'ouvre sur un exemple explicite de nombre non calculable, la constante de Chaitin, liée au problème de l'arrêt.

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.

Conclusion : la réponse à la question

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.

Les pièges qui coûtent des points

• Croire que tous les ensembles infinis ont la même taille.
• Oublier que la liste des programmes est infinie mais numérotable.
• Construire y avec des chiffres 0 et 9, qui créent des doubles écritures.

Revoir les notions

• Nombres et calculs (Seconde) →
• Combinatoire et dénombrement (Terminale spé maths) →

Autres questions : logique et calculabilité

• Peut-on écrire un programme qui détecte tous les programmes qui tournent en boucle infinie ?
• 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 ?

Toutes les questions maths-nsi →