Question transversaleMathsNSILogique et calculabilité

Comment une question aussi simple que « combien de temps peut tourner un petit programme ? » peut-elle être impossible à résoudre ?

Parmi les machines de Turing à n états qui finissent par s'arrêter, combien d'étapes au maximum ? Les valeurs sont 1, 6, 21, 107, puis 47 176 870 pour n = 5, démontré en 2024. Cette fonction croît plus vite que toute fonction calculable : aucun programme ne peut la calculer pour tout n.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 10 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.

J'ai lu en 2024 qu'une collaboration internationale d'amateurs et de chercheurs venait de démontrer la valeur d'un nombre appelé « BB(5) », après des décennies d'efforts. Je me suis demandé pourquoi il était si difficile de savoir combien de temps peut tourner un minuscule programme. J'ai découvert que cette difficulté est mathématiquement inévitable.

L'enjeu et les notions du programme

Comprendre une fonction définie par un maximum sur un ensemble fini, et démontrer par l'absurde qu'elle n'est pas calculable.

Mathématiques

Maximum d'un ensemble fini (seconde)
Croissance des suites, comparaison (terminale)
Raisonnement par l'absurde (seconde)

Numérique et sciences informatiques

Calculabilité, machine de Turing, problème de l'arrêt (terminale)
Dénombrement des programmes (terminale)

Le plan de l'exposé en 10 min

1. Introduction
1 min
Une machine de Turing est un programme élémentaire : une tête lit et écrit sur un ruban, selon une table de règles à $n$ n états. Problématique : parmi toutes les machines à $n$ n états qui s'arrêtent, laquelle tourne le plus longtemps, et peut-on le calculer ?
2. Mathématiques : une fonction bien définie
3,5 min
Pour $n$ n fixé, il n'y a qu'un nombre fini de tables de règles : chaque règle a un nombre fini de choix. Parmi celles qui s'arrêtent sur un ruban vide, le nombre d'étapes a donc un maximum, noté $B B (n)$ BB(n) (pour « busy beaver », castor affairé). La fonction est parfaitement définie.
Valeurs connues : $B B (1) = 1$ BB(1)=1, $B B (2) = 6$ BB(2)=6, $B B (3) = 21$ BB(3)=21, $B B (4) = 107$ BB(4)=107, et $B B (5) = 47176870$ BB(5)=47 176 870, démontré en 2024 avec l'aide d'une preuve vérifiée par ordinateur. Pour $n = 6$ n=6, on sait seulement qu'il est gigantesque, bien au-delà de $1 0^{1 0^{10}}$ 10^(10¹⁰).
3. NSI : pourquoi elle n'est pas calculable
4 min
Supposons qu'un programme calcule $B B (n)$ BB(n) pour tout $n$ n. On pourrait alors résoudre le problème de l'arrêt pour toute machine à $n$ n états : on la lance pendant $B B (n)$ BB(n) étapes ; si elle ne s'est pas arrêtée, elle ne s'arrêtera jamais, puisque $B B (n)$ BB(n) est le maximum. Or le problème de l'arrêt est indécidable : contradiction. $B B$ BB n'est pas calculable.
On montre même que $B B$ BB finit par dépasser toute fonction calculable : exponentielle, tour d'exponentielles, fonction d'Ackermann… La difficulté pratique est réelle : pour $n = 5$ n=5, il a fallu examiner des dizaines de millions de machines et prouver une à une que celles qui semblaient tourner sans fin ne s'arrêteraient vraiment jamais.
4. Conclusion
1,5 min
$B B (n)$ BB(n) est bien défini comme un maximum sur un ensemble fini, mais aucun programme ne peut le calculer pour tout $n$ n, sinon il résoudrait le problème de l'arrêt. Ses valeurs explosent : 107 pour 4 états, 47 millions pour 5. J'ouvre sur les questions mathématiques ouvertes, comme la conjecture de Goldbach, qui se ramènent à l'arrêt de petites machines.

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.

B B (n) = max {\overset{e}{ˊ} tapes d’une machine \overset{a}{ˋ} n \overset{e}{ˊ} tats qui s’arr \overset{e}{ˆ} te} BB(n)=max{ étapes d'une machine à n états qui s'arrête } 1, 6, 21, 107, 47176870 B B calculable \Rightarrow arr \overset{e}{ˆ} t d \overset{e}{ˊ} cidable : contradiction 1, 6, 21, 107, 47 176 870 BB calculable \Rightarrow arrêt décidable : contradiction

Conclusion : la réponse à la question

Une fonction peut être parfaitement définie et pourtant incalculable. Le castor affairé relie un maximum fini, une croissance hors norme et le problème de l'arrêt.

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.

Pourquoi BB(n) existe-t-il ?

Il n'y a qu'un nombre fini de machines à n états ; parmi celles qui s'arrêtent, le nombre d'étapes a un maximum.

Pourquoi ne pas simplement lancer toutes les machines ?

Certaines ne s'arrêtent jamais, et on ne peut pas toujours savoir lesquelles : on ne saurait pas quand conclure.

Qu'est-ce qu'une machine de Turing ?

Un modèle abstrait de calcul : un ruban infini, une tête de lecture et une table de règles finie.

Une fonction croissante peut-elle ne pas être calculable ?

Oui : BB est croissante et pourtant non calculable.

Quel lien avec la conjecture de Goldbach ?

On peut écrire une petite machine qui cherche un contre-exemple et s'arrête si elle en trouve ; connaître BB pour sa taille trancherait la conjecture.

Les pièges qui coûtent des points

Confondre « non calculable » et « non défini ».
Croire qu'un ordinateur plus puissant calculerait BB pour tout n.
Oublier que la preuve repose sur l'indécidabilité de l'arrêt.

Revoir les notions

Autres questions : logique et calculabilité

Toutes les questions maths-nsi →

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 →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →