ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges
 ACKERMANN Wilhelm,
allemand, 1896-1962 |
Élève de Hilbert à Göttingen, Ackermann obtient son doctorat en 1925. Sa thèse et ses recherches portent sur la logique mathématique et la consistance des systèmes formels, une des questions mathématiques majeures du début du 20è siècle.
Il s'agit de rechercher si un système d'axiomes d'une théorie ne contient pas des règles contradictoires et de développer un nouveau langage mathématique échappant au domaine trop intuitif de la logique traditionnelle du tiers exclu héritée d'Aristote.
Cette logique qui avait fait preuve de grave insuffisance depuis l'apparition des premières contradictions nées de la théorie des ensembles de Cantor. Pour qualifier ces travaux sur les fondements des mathématiques, s'attachant à une théorie de la démonstration, on parle de métamathématique (terme initié par Hilbert).
Métamathématique : » Aristote et la logique du tiers exclu : »
Nonobstant le théorème d'incomplétude de Gödel, Ackermann prouva, dans le cadre de la métamathématique, la consistance de l'arithmétique en 1940. En prouvant la consistance de la théorie des nombres réels, rappelons que Hilbert (1900) prouva la consistance de la géométrie euclidienne en la ramenant à la géométrie analytique de Descartes : on voit finalement là le lien étroit entre géométrie dite "pure" et l'analyse. A ce sujet, rappelons aussi que Dedekind avait établi (1872) la bijection de la droite géométrique sur la droite réelle.
| Axiomes d'Hilbert-Ackermann de la logique propositionnelle déductive : |
Il s'agit d'une logique basée sur 4 axiomes
faisant appel à la disjonction et l'implication
logiques sous la forme suivante. Cette logique est équivalente à celle de
Frege. P, Q et R désignant des propositions :
(P ou P) ⇒ P
➔ On peut remplacer ces 4 axiomes (ou ceux de Frege ou de Russel) par un seul comme le fit Marcel Boll (1886-1958), savant français, philosophe, physicien et historien des sciences qui s'intéressa de fort près à la logique :
Axiome de Boll :
[P ⇒ (Q et R)] ⇒ [(P ou S) ⇒ (Q ou S)]
On voit ainsi que la logique propositionnelle d'Aristote peut se réduire par cet artifice à un seul axiome et un seul connecteur !
| Fonction d'Ackermann : |
Dans ses travaux Ackermann exhibe (1925) une fonction récursive de N3 dans N, notée ici A(m,n,p) et montre qu'elle n'est pas récursive primitive. à la main ou automatisé, le calcul est très lourd car contenant deux appels récursifs imbriqués (récursivité du second ordre) : l'appel récursif appelle un second appel récursif, ce qui complique bigrement le calcul. En comparaison, le calcul récursif du PGCD est une récursivité de N2 dans N du premier ordre moins gourmand en mémoire et en temps de calcul.
On rencontre souvent cette fonction sous une forme simplifiée privée de la récurrence sur p que donna Rósza Peter :
Les deux premières lignes de la définition de A sont les deux points d'arrêt de la récursion (double récurrence). En programmation effective sur ordinateur, le calcul de A(m,n) sature "très vite" la capacité de la pile de ce dernier car "il" est obligé d'empiler les résultats partiels successifs tant que les conditions d'arrêts ne sont pas atteintes :
function A(m,n)
{
if (m!= 0 && n!= 0) {return A(m-1,A(m,n-1))}
else
{
if (m= = 0) {return n+1} // cette instruction traite le cas m = n = 0 : A(0,0) = 1 l'instruction suivante n'est pas lue
// compte tenu du return.
if (n= = 0) {return A(m-1,1)}
}}
Au-delà de m = 3, avec par exemple A(3,1) = 13, A(3,2) = 29, A(3,0) = 5, A(3,5) = 253, les valeurs s'envolent très vite : A(4,0) = 13 mais A(4,1) = 65533 = et A(4,2) = 265536 - 3 !
Plus précisément :
A(0,n) = n + 1 ; A(1,n) = n + 2 ; A(2,n) = 2n + 3 ; A(3,n) = 2n+3 - 3
Prouver les 3 derniers résultats. En panne ? cliquez sur l'ampoule pour obtenir la solution ☼
Programmation JavaScript de la fonction d'Ackermann : »
♦ Gabriel Sudan, un autre élève de Hilbert de nationalité roumaine, exhiba (1927) une fonction similaire, récursive non primitive de N3 dans N :
S(m,n,0) = m + n; S(m,0,k) = m;n ≥ 1, k ≥ 1
S(m,n,k) = S(S(m,n-1,k), S(m,n-1,k) + n, k-1).
En savoir plus sur Sudan et cette fonction : » Récursion et suite de Fibonacci : »
| Quelques autres algorithmes récursifs dans ChronoMath : |
La notion générale de fonction récursive : » Récursion et tableur : »
➔ Pour en savoir plus :
Alexandrov