Question transversaleMathsNSILogique et calculabilité

Comment une fonction définie par trois lignes peut-elle produire des nombres de 20 000 chiffres ?

Q: Calculez A(1, 1) à partir de la définition.

$A(1,1)=A(0,A(1,0))=A(0,A(0,1))=A(0,2)=3$.

Q: Démontrez A(2, n) = 2n + 3 par récurrence.

$A(2,0)=3$ ; si $A(2,n-1)=2n+1$, alors $A(2,n)=A(1,2n+1)=2n+3$.

Q: Comment compter les chiffres de 2⁶5 536 ?

$lfloor65 536log₁₀2rfloor+1=lfloor19 728,3rfloor+1=19 729$.

Q: Que vaudrait A(4, 3) ?

$A(3,A(4,2))=2^(2^(65 536))-3$ : son nombre de chiffres a lui-même 19 729 chiffres. Aucun ordinateur ne pourra jamais l'écrire.

La fonction d'Ackermann est définie par une récursion double. On démontre par récurrence que A(1, n) = n + 2, A(2, n) = 2n + 3 et A(3, n) = 2ⁿ⁺³ − 3. Puis A(4, 1) = 65 533 et A(4, 2) = 2⁶⁵ ⁵³⁶ − 3, un nombre de 19 729 chiffres. Elle est calculable, mais croît plus vite que toute fonction écrite avec de simples boucles « pour ».

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.

En NSI, mon professeur nous a donné une fonction récursive de trois lignes en nous mettant au défi de calculer A(4, 2). Mon programme a planté. J'ai voulu comprendre ce qui se passait, et j'ai découvert qu'en calculant les premières valeurs, on reconnaît une addition, puis une multiplication, puis une exponentielle, chaque étage itérant le précédent. Des récurrences de terminale permettent de le démontrer.

L'enjeu et les notions du programme

Conjecturer puis démontrer par récurrence des formules explicites pour une fonction définie récursivement, et mesurer sa croissance.

Mathématiques

Raisonnement par récurrence (terminale)
Suites arithmétiques, géométriques et arithmético-géométriques (première)
Puissances, logarithme décimal pour compter les chiffres (terminale)

Numérique et sciences informatiques

Récursivité, pile d'appels (terminale)
Calculabilité (terminale)

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

1. Introduction
1 min
La fonction d'Ackermann est définie par : $A (0, n) = n + 1$ A(0,n)=n+1 ; $A (m, 0) = A (m - 1, 1)$ A(m,0)=A(m-1,1) ; $A (m, n) = A (m - 1, A (m, n - 1))$ A(m,n)=A(m-1,A(m,n-1)). Problématique : quelles valeurs prend-elle, et pourquoi devient-elle impossible à calculer en pratique ?
2. Mathématiques : une suite d'étages
4,5 min
Étage $m = 1$ m=1 : $A (1, 0) = A (0, 1) = 2$ A(1,0)=A(0,1)=2 et $A (1, n) = A (0, A (1, n - 1)) = A (1, n - 1) + 1$ A(1,n)=A(0,A(1,n-1))=A(1,n-1)+1. Suite arithmétique de raison 1 : $A (1, n) = n + 2$ A(1,n)=n+2.
Étage $m = 2$ m=2 : $A (2, 0) = A (1, 1) = 3$ A(2,0)=A(1,1)=3 et $A (2, n) = A (1, A (2, n - 1)) = A (2, n - 1) + 2$ A(2,n)=A(1,A(2,n-1))=A(2,n-1)+2. Suite arithmétique de raison 2 : $A (2, n) = 2 n + 3$ A(2,n)=2n+3.
Étage $m = 3$ m=3 : $A (3, 0) = A (2, 1) = 5$ A(3,0)=A(2,1)=5 et $A (3, n) = 2 A (3, n - 1) + 3$ A(3,n)=2A(3,n-1)+3. Suite arithmético-géométrique : en posant $v_{n} = A (3, n) + 3$ vₙ=A(3,n)+3, $v_{n} = 2 v_{n - 1}$ vₙ=2vₙ₋₁, donc $v_{n} = 8 \times 2^{n}$ vₙ=8×2ⁿ et $A (3, n) = 2^{n + 3} - 3$ A(3,n)=2ⁿ⁺³-3. On vérifie : $A (3, 4) = 125$ A(3,4)=125.
Étage $m = 4$ m=4 : $A (4, 0) = A (3, 1) = 13$ A(4,0)=A(3,1)=13, $A (4, 1) = A (3, 13) = 2^{16} - 3 = 65533$ A(4,1)=A(3,13)=2¹⁶-3=65 533, $A (4, 2) = A (3, 65533) = 2^{65536} - 3$ A(4,2)=A(3,65 533)=2^(65 536)-3. Nombre de chiffres : $⌊ 65536 lo g_{10} 2 ⌋ + 1 = 19729$ lfloor65 536log₁₀2rfloor+1=19 729.
Chaque étage itère le précédent : addition, multiplication, exponentiation, puis tour d'exponentielles.
3. NSI : calculable mais pas en pratique
2,5 min
La fonction termine toujours : on le prouve par une récurrence sur le couple $(m, n)$ (m,n) ordonné lexicographiquement. Elle est donc calculable. Mais le nombre d'appels et la profondeur de la pile explosent : Python dépasse sa limite de récursion dès $A (4, 1)$ A(4,1).
Ackermann l'a construite en 1928 pour montrer qu'il existe des fonctions calculables qui ne s'écrivent pas avec des boucles « pour » dont le nombre de tours est connu à l'avance (fonctions « primitives récursives ») : elle les dépasse toutes. Il faut des boucles « tant que » ou une récursion générale.
4. Conclusion
1,5 min
Trois lignes de récursion suffisent à empiler addition, multiplication et exponentiation : $A (3, n) = 2^{n + 3} - 3$ A(3,n)=2ⁿ⁺³-3, et $A (4, 2)$ A(4,2) a 19 729 chiffres. Des récurrences de terminale démontrent ces formules. J'ouvre sur le castor affairé, qui croît plus vite encore et n'est même plus calculable.

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.

A (1, n) = n + 2 A (2, n) = 2 n + 3 A (3, n) = 2 A (3, n - 1) + 3 \Rightarrow A (3, n) = 2^{n + 3} - 3 A(1,n)=n+2 A(2,n)=2n+3 A(3,n)=2A(3,n-1)+3\Rightarrow A(3,n)=2ⁿ⁺³-3 A (4, 1) = 2^{16} - 3 = 65533 A (4, 2) = 2^{65536} - 3 (19729 chiffres) A(4,1)=2¹⁶-3=65 533 A(4,2)=2^(65 536)-3 (19 729 chiffres )

Conclusion : la réponse à la question

La fonction d'Ackermann montre qu'une définition récursive très courte peut produire une croissance vertigineuse. Les récurrences sur les suites permettent de comprendre chacun de ses étages.

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.

Calculez A(1, 1) à partir de la définition.

$A (1, 1) = A (0, A (1, 0)) = A (0, A (0, 1)) = A (0, 2) = 3$ A(1,1)=A(0,A(1,0))=A(0,A(0,1))=A(0,2)=3.

Démontrez A(2, n) = 2n + 3 par récurrence.

$A (2, 0) = 3$ A(2,0)=3 ; si $A (2, n - 1) = 2 n + 1$ A(2,n-1)=2n+1, alors $A (2, n) = A (1, 2 n + 1) = 2 n + 3$ A(2,n)=A(1,2n+1)=2n+3.

Comment compter les chiffres de 2^65 536 ?

$⌊ 65536 lo g_{10} 2 ⌋ + 1 = ⌊ 19728, 3 ⌋ + 1 = 19729$ lfloor65 536log₁₀2rfloor+1=lfloor19 728,3rfloor+1=19 729.

La fonction termine-t-elle toujours ?

Oui : à chaque appel, soit m diminue, soit m reste égal et n diminue ; cet ordre ne permet pas de descente infinie.

Pourquoi Python plante-t-il ?

La profondeur de récursion dépasse la limite autorisée, bien avant que le calcul ne soit fini.

Que vaudrait A(4, 3) ?

$A (3, A (4, 2)) = 2^{2^{65536}} - 3$ A(3,A(4,2))=2^(2^(65 536))-3 : son nombre de chiffres a lui-même 19 729 chiffres. Aucun ordinateur ne pourra jamais l'écrire.

Les pièges qui coûtent des points

Confondre calculable en théorie et calculable en pratique.
Oublier la règle A(m, 0) = A(m − 1, 1).
Croire que la fonction ne termine pas.

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 →