Sudan Gabriel

ChronoMath, une chronologie des MATHÉMATIQUES
à l'usage des professeurs de mathématiques, des étudiants et des élèves des lycées & collèges

SUDAN Gabriel, roumain, 1899-1977

! On ne confondra Gabriel Sudan avec Madhu Sudan (1966-), mathématicien et informaticien indo-américain, diplômé de l'université de Berkeley, chercheur au MIT (Massachusetts Institute of Technology, Cambridge, USA) et au Microsoft Research, dont on pourra consulter quelques éléments biographiques sur le site du MIT. Prix Gödel 2001.

Gabriel Sudan étudia à Göttingen et obtint son doctorat (1925) portant sur les ensembles ordonnés (problématique du bon ordre en particulier) sous la direction de Hilbert. Il quitta l'Allemagne lors de la seconde guerre mondiale pour enseigner en Roumanie à l'université de Bucarest.

En logique mathématique, il contribua comme son collègue Ackermann, également "élève" de Hilbert, à l'étude des fonctions récursives, un sujet nouveau lié au problème de la calculabilité suite au bouleversement des fondements des mathématiques produit par les insuffisances apparues dans la logique classique d'Aristote suite à l'apparition, alors récente, de la théorie des ensembles de Cantor (1883).

Fonctions récursives et calculabilité : »

Fonction de Sudan :

La fonction de Sudan est la fonction récursive non primitive, analogue à celle d'Ackermann, définie de N³ dans N par :

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).

On a, par exemple :

S(1,1,1) = S(S(1,1,0), S(1,1,0) + 1,0) = S(1,1,0) + S(1,1,0) + 1 = 1 + 1 + 3;
S(1,2,1) = S(S(1,1,1), S(1,1,1) + 2, 0) = 2S(1,1,1) + 2 = 6 + 2 = 8;
S(2,1,1) = S(S(2,0,1), S(2,0,1) +1, 1) = S(2,3,0) = 2 + 3 = 5.

Programmation JavaScript récursif de la fonction :

<SCRIPT LANGUAGE=JavaScript>

function sudan()
{
m=3;m=eval(prompt("S(m,n,k), donnez m : ",m))
n=2;n=eval(prompt("S("+m+",n,k), donnez n : ",n))
k=1;k=eval(prompt("S("+m+","+n+",k), donnez k : ",k))
alert("S("+m+","+n+","+k+") = "+S(m,n,k))
}

function S(m,n,k)
{
if (k!=0 && n!=0)
{return S(S(m,n-1,k), S(m,n-1,k) + n, k-1)}
else
{
if (k==0) {return m+n}
if (n==0) {return m}
}
}
</SCRIPT>

Commentaires :

➔ Ce programme ne contrôle pas les entrées qui devront être entières ! La structure récursive de la fonction S(m,n,k) présente une programmation identique à sa définition mathématique. C'est là l'élégance et la concision des définitions récursives comme celle, plus simple, du PGCD.

! Le programme sature très vite ! C'est le problème général des programmes récursifs devant "empiler" en mémoire les résultats intermédiaires. Un micro-ordinateur, quoique doté d'un compilateur JavaScript relativement puissant, n'est pas "vraiment" adapté à ce type de calcul doublement récursif.

S(2,2,1) = 12 , S(3,2,1) = 16. S(2,2,2) = 15 569 256 417 est aussi calculé sans difficultés mais
S(1,2,3) est déjà très problématique...

➔ Pour en savoir plus :

Logique mathématique, tome 2 : Fonctions récursives, théorème de Gödel, ...
par René Cori, Daniel Lascar. Éd. Dunod, Paris, 2003.
Machines de Turing, Calculabilité et décidabilité, cours d'Alain Lecomte, univ. Grenoble :
http://lecomte.al.free.fr/ressources/LIC_MIASS/coursTuring.pdf
Techniques récursives en programmation par D.W. Baron, Éd. Dunod, Paris - 1970
Les bases de la programmation par Jacques Arsac, Éd. Dunod informatique, Paris - 1983
Les algorithmes par Patrice Hernert - Que sais-je n° 2928, Ed. P.U.F., Paris - 1995

Mandelbrot Szolem

Zariski