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

Notions sur les fonctions récursives
   
ensemble récursivement énumérables

Les termes récursif, récursion, récursivité ont la même racine latine que récurrence : currere = courir, et par là : recurrere = courir en arrière qui a donné également recourir, recours = action de faire appel (en justice).

I - Les fonctions récursives en informatique :      

Une fonction ou procédure (ensemble de règles logiques) X est définie récursivement si sa définition est de la forme X = Φ(A, B, ..., X) où A, B, ... désignent des règles ou fonctions connues et Φ une fonction ou procédure combinant A, B, ... et X. C'est dire que X fait appel à elle-même pour se définir.

à cette relation générale, il faut associer une condition d'arrêt afin que la procédure ne boucle pas indéfiniment. Le propre d'une procédure récursive bien pensée est qu'elle généralement d'une admirable concision et n'utilise qu'un minimum de concepts extérieurs à sa définition comme dans la définition de la factorielle de n :

function factorielle(n)
{if (n<=1) return 1 else return n*factorielle(n-1)}

Il s'agit de distinguer récursion et récurrence. Définir une suite (un) par uo = 1, un = 3un-1, c'est écrire une relation récurrente. Pour calculer un en fonction de n, il faut "courir en arrière" : reculer jusqu'à uo (valeur initiale), en décrémentant n.

 un = 3un-1 = 33un-2 = 333un-3 = 3333un-4 = ... =  3nuo

Mais un n'est autre qu'une fonction de n : un = f(n). En écrivant :

nN*, f(0) = 1, f(n) = 3f(n-1)

on définit une fonction récursive dans l'ensemble des entiers naturels, dont f(0) = 1 est la condition d'arrêt. On est donc en présence d'une procédure récursive de type récurrent conduisant à la fonction exponentielle de base 3 restreinte à N.  La fonction factorielle décrite précédemment est également récursive de type récurrent.

  factorielle n , suite de Fibonacci , fonction d'Ackermann , Nombres de Fibonacci Nombres de Lucas

Le calcul du PGCD selon la méthode d'Euclide est une méthode récursive non récurrente :

PGCD(a,0) = a, PGCD(a , b) = PGCD(b , r)   avec r = a - b x Ent(a/b), reste de la division de a par b             

On réitère la formule jusqu'à r = 0 (condition d'arrêt). Le pgcd est le dernier reste non nul : par exemple, d(24,18) = d(18,6) = d(6,0) = 6.

On remarque que dans les deux méthodes, le cas "général" s'obtient en revenant au cas initial par un processus bien défini au bout d'un nombre fini d'itérations.

On parlera d'un algorithme itératif (du latin iterare = répéter) lorsqu'un résultat souhaité est obtenu en répétant (en réitérant) un même processus pn pour des valeurs croissantes de n. En termes de programmation, on parle de boucle (for ... do ..., while ...).

II - Les procédures récursives en informatique :      

Le traitement récursif des chaînes de caractères est très efficace et très instructif de la puissance de la récursion par la simplicité de mise en œuvre. On pourra consulter quelques exemples donnés dans ChronoMath :

  Inversion d'une chaîne , Tri d'une liste , Formule de Wallis (tableur) , Autres cas sur la page Ackermann

III - Les fonctions récursives en logique mathématique :      

C'est tout particulièrement à Gödel et Herbrand en 1930-31, puis Turing et Post, mais aussi Rózsa Péter et Kalmár en Hongrie, que l'on doit la mise en place du concept mathématique nouveau de fonction récursive dans leurs travaux relatifs aux fondements des mathématiques gravement ébranlés par les contradictions apparues dans la logique classique du tiers-exclu d'Aristote suite à l'apparition de la théorie des ensembles de Cantor.

Kronecker, qui affirmait « Dieu a créé les nombres entiers, le reste est l'œuvre de l'homme » avait prédit que la recherche mathématique devait s'appuyer exclusivement sur les propriétés des nombres entiers. Reconstruire les mathématiques à partir de N, ensemble des entiers naturels, source de toute la mathématique, nécessite donc une définition sans faille exempte de toute intuition susceptible de mettre à mal le futur édifice.

Les nombres réels, base de l'analyse, sont construits à partir des rationnels, quotients d'entiers, et les géométries reposent sur leurs métriques définies par des propriétés numériques, ce qui nous ramène encore aux entiers.

Ce principe de construction se rencontre par exemple dans la mise en place de la fonction exponentielle :

Construction de la fonction exponentielle :

La validité et la puissance du concept de fonction et d'énoncés récursifs défini par Gödel en 1931 (et, indépendamment, par Jacques Herbrand, 1908-1931) réside dans sa totale indépendance de toute théorie mathématique existante, aspect évidemment fondamental lorsque l'objectif est de fonder une logique nouvelle suite aux failles des systèmes de pensée précédents. La seule connaissance admise et utilisée fut l'ensemble des entiers naturels que von Neumann s'amusera à définir récursivement...

Ambiguïté d'un vocabulaire pléthorique... :    

Dans les années 1930, un des objectifs était d'étudier la consistance des théories mathématiques et de la décidabilité de propositions énoncées en leur sein : dans une théorie T, une proposition p est décidable si l'on peut prouver, au moyen des axiomes de T, soit p soit non p.

Prouver p c'est établir au moyen de la logique de T (définie par ses axiomes et son langage) que non p est contradictoire en ce sens qu'elle impliquerait la la négation d'un axiome ou d'un énoncé (formule, proposition) déjà établi.

La validité de p consiste alors à exhiber une méthode effective de preuve, c'est à dire un algorithme aboutissant à p par l'usage d'un nombre fini « d'opérations » fondamentales. Les langages informatiques ayant emprunté les terme récursif (adjectif), récursivité (substantif associé) récursion (action récursive au sein d'un programme récursif) on préfère, en logique mathématique, parler aujourd'hui de fonction calculable ou, plus précisément, de fonction effectivement calculable, pour signifier qu'il existe une méthode permettant de la calculer en un nombre fini d'opérations fondamentales. C'est le cas, par exemple,  de la définition du PGCD défini par Euclide.

Kleene qualifia de primitives (on dit aussi fondamentales) les premières fonctions récursives introduites par Skolem (1923). Augmentées des fonctions obtenues par son opération de minimum, dites μ-récursives ( ci-après), on parla de fonctions récursives partielles. Après les travaux de Gödel et Herbrand et les résultats décisifs de Turing (1936) apportés par sa fameuse « machine à penser », on parla, avec Gödel, de fonctions récursives générales pour exprimer des définitions récursives composées de fonctions récursives primitives au sens de Kleene.

En 1936-37, Church et Kleene prouvent, au moyen de leurs fonctions λ-définissables et  μ-récursives (respectivement) clôturent le chapitre en prouvant que :

Les fonctions calculables sont les fonctions récursives générales lesquelles coïncident 
avec les fonctions calculables au sens de Turing.

En logique, les fonctions calculables sont désormais les fonctions récursives générales, ou récursives (tout court) : fonctions construites et obtenues au moyen d'un nombre fini d'étapes en utilisant les fonctions récursives primitives décrites ci-dessous. Après six années de recherches, il apparaissait donc que la calculabilité au sens de la pensée logique, sans rapport à l'informatique, inexistante à l'époque, coïncide avec la calculabilité "mécanique" ! C'est là un résultat à la fois remarquable et bouleversant auquel ne s'attendait certes pas Gödel dans un contexte philosophique du mécanisme de la pensée, ni Hilbert qui énonçait, au tout début du 20 siècle, ses célèbres 23 problèmes pour le (les ?) siècle(s) à venir.

Au fait, existe-t-il des fonctions non calculables ? Oui, mais elles sont "rares" pour ne pas dire tirées par les cheveux... On pourra consulter la référence 8 et l'exemple dit du castor affairé, (busy biver problem) qui empile les 1 (plutôt que les branchages...), une fonction qui boucle indéfiniment sur une machine de Turing

Les fonctions récursives primitives, récursives élémentaires et récursives générales :

On suppose ici que l'ensemble N des entiers naturels est construit ou accepté dans son sens intuitif. Selon Kleene, les fonctions de Np dans N, p ≥ 1, établies comme effectivement calculables depuis les premiers travaux de Skolem et Gödel sur le sujet, dites récursives primitives (appellation du à Skolem) sont les suivantes :

  1. La fonction successeur (incrémentation) Incr qui à tout entier naturel x associe l'entier immédiatement supérieur x+. C'est donc x + 1, mais tant que l'addition n'est pas définie...
  2. Les fonctions constantes Fc(x l, ..., xp) = c (entier) dont la fonction nulle.
  3. Les fonctions projections Pi(x l, ..., xp) = xi.
    Pour deux variables : P2(x1,x2) = x2, pour une variable : P1(x1) = x1, c'est l'application identique.
  4. Les fonctions obtenues par récurrence simple sur une des variables entières, par exemple x1 : on suppose g récursive primitive, alors f définie par l'algorithme ci-dessous l'est aussi :
        a/ initialisation : f(
    0, x 2, ..., xp) = k, k donné dans N      Raisonnement par induction
        b/ hérédité (ou induction) :
    f(n+1, x 2, ..., xp) = g(f(n, x2, ..., xp), x2, ..., xp)
  5. Les fonctions obtenues par composition (on dit aussi par superposition) : si f et g sont récursives primitives, alors la fonction composée h définie par h(x l, ..., xp) = f(x l, ...,g(x l, ...,  xp),...,  xp) l'est aussi.
  6. Les fonctions obtenues par l'opération de minimum (dû à Kleene) : si R(x l, ...,  xp) entre éléments de N, on désigne par (µx)R(x l, ...,  xp), mu comme minimum, le plus petit entier naturel x réalisant R(x l, ...,  xp), ce qui permet de construire de nouvelles fonctions.

La nature récursive de ces fonctions (au sens usuel de fonction se définissant en faisant appel à elle-même) n'apparaît peut-être pas clairement. Étudions les à travers des exemples plus concrets, fonctions récursives élémentaires :

La fonction prédécesseur Dec (décrémentation, antécedent) :     

Si x est un entier naturel, son antécédent est 0 s'il est nul, sinon, c'est x - 1. Or, (x + 1) - 1 = x. On peut donc la définir très simplement au moyen de la fonction successeur par :

Decr0) = N(x)  (i.e. = 0, initialisation)
Decr(Incr(x)) = P1(x)
  (= x, récurrence simple).

La fonction addition Add :     

Additionner y à x, c'est incrémenter x en décrémentant y jusqu'à obtenir 0. On peut la définir par récurrence :

Add(x,0) = P1(x)  (i.e. = x, condition d'arrêt)
Add(x,y) = Incr(Add(x,Decr(y))

Et on pose plus simplement : Add(x,y) = x + y.

La fonction soustraction Sous :     

La soustraction dans N définie par : S(x,y) = x - y si x ≥ y et 0 sinon, peut être définie par :

        Sous(x, 0) = x et Sous(x,y) = Decr(Sous(x,Decr(y))

La fonction multiplication M :    

M(x,y) = xy. Elle sera définie par :

M(x,0) = N(x)  (= 0, fonction nulle : condition d'arrêt)
M(x,y) = A(M(x,D(y)),P1(x,y)) , c'est à dire x(y - 1) + x : appel récursif 

On définira alors facilement la fonction puissance entière.

Ensembles récursifs ou récursivement énumérables :

En simplifiant : une partie X de N, et plus généralement de Np, est dite récursive ou décidable pour signifier qu'il existe un algorithme permettant d'affirmer en un nombre fini d'étapes qu'un élément x de X appartient ou non à cet ensemble. Cela revient à dire que sa fonction caractéristique (égale à 1 dans X, 0 sinon) est calculable.

X est dit récursivement énumérable ou semi-décidable (définition due à Kleene), s'il existe une fonction récursive ( calculable) dont l'image est cet ensemble. Plus intuitivement : s'il existe un algorithme capable d'établir la liste de tous les éléments de X.

Cette nouvelle vision permet d'exhiber sans ambiguïté, dans un contexte constructiviste, des objets mathématiques en un nombre fini d'étapes et conduisent au concept d'ensembles et de théories axiomatisables et décidables. Ces idées novatrices permettront de résoudre négativement le 10ème problème de Hilbert.

  Turing , Rózsa Péter , Ackermann , Church

Pour en savoir plus :

  1. Techniques récursives en programmation, D.W. Barron, Éd. Dunod, Paris - 1970
  2. Les bases de la programmation, Jacques Arsac, Éd. Dunod, Paris - 1982
  3. Les Algorithmes par Patrice Hernert, Que sais-je n° 2928, Éd. P.U.F., Paris - 1995
  4. par Douglas Hofstadter, Ed. InterEditions - Paris 1985
  5. Logique mathématique, tome 2 : Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles
    par
    René Cori, Daniel Lascar. Éd. Dunod, Paris, 2003.
  6. Fonctions récursives, ensembles récursivement énumérables, effectivité par Andrzej Grzegorczyk
    Collection logique mathématique Série A, Paris Gauthier-Villars, 1961
  7. Itération et récursivité par Jacques Arsac :
    http://hal.archives-ouvertes.fr/docs/00/35/91/90/PDF/d14p081.pdf
  8. La théorie des fonctions récursives et ses applications, par D. Lacombe (Bulletin de la SMF,1960)
    http://archive.numdam.org/article/BSMF_1960__88__393_0.pdf
  9. Fonctions récursives et Machines de Turing , cours et exercices de Nhan Le Tanh (Univ. Nice) :
    http://www.i3s.unice.fr/~nlt/cours/licence/it/s5_itdut_poly.pdf
  10. Algorithmique et Calculabilité (Université de Liège) : http://www.discmath.ulg.ac.be/cours/main_calcul.pdf
  11. Ensembles récursivement énumérables et 10è problème de Hilbert
    http://www.mathkang.org/cite/confC01.html
  12. Ensembles récursivement énumérables et théorème de Gödel : cours de Jean Betrema : http://www.labri.fr/perso/betrema/MC/MC4.html
  13. Théorie de la démonstration : Wikipédia, Portail de la logique :
    http://fr.wikipedia.org/wiki/Th%C3A9orie_de_la_dC3%A9monstration
  14. ABRÉGÉ D'HISTOIRE DES MATHÉMATIQUES, 1700-1900, Jean Dieudonné, Ch.11, §5, par Marcel Guillaume. Ed. Hermann, Paris, 1978-1992.
  15. La machine de Turing, théorie des nombres calculables, fonctions récursives, suivie d'une application au problème de la décision, Les machines peuvent-elles penser ? par Alan Turing (traduit de l'anglais).
  16. Un livre superbe, à lire dans le calme... : Gödel, Escher, Bach, les Brins d'une Guirlande Eternelle
     


© Serge Mehl - www.chronomath.com