Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
En informatique et en mathématiques, le terme fonction récursive ou fonction calculable désigne la classe de fonctions dont les valeurs peuvent être calculées à partir de leurs paramètres par un processus mécanique fini. En fait, cela fait référence à deux concepts liés, mais distincts. En théorie de la calculabilité, la classe des fonctions récursives est une classe plus générale que celle des fonctions récursives primitives, mais plus restreinte que celle des fonctions semi-calculables (ou partielles récursives). En informatique, les fonctions récursives sont des fonctions dont le calcul nécessite d'invoquer la fonction elle-même, c'est-à-dire que dans ce deuxième cas, on insiste plutôt sur la façon dont le calcul est mis en œuvre que sur la classe de fonctions.
Logique mathématique (calculabilité)
Fonction récursive
En théorie de la calculabilité, une fonction récursive est une fonction à un ou plusieurs arguments entiers, qui peut se calculer en tout point par une procédure mécanique[1],[2]. Il est plus cohérent de définir les fonctions semi-calculables avant les fonctions récursives, car les fonctions récursives n'en sont qu'un cas particulier[2] : formellement, une fonction récursive est alors une fonction semi-calculable définie en tout point[De quoi ?]. On trouve de plus en plus souvent le terme de « fonction calculable » pour désigner une fonction récursive, qui est le terme historique ; or il y a plusieurs définitions équivalentes des fonctions « calculables » ; l'une d'elles est : « fonctions calculables pour toute entrée par une machine de Turing en un nombre fini d'opérations[3] » (ces fonctions sont a priori partielles[pas clair]).
Historiquement, on a d'abord introduit dans les années 1920 la classe des fonctions récursives primitives, dont on s'est rapidement rendu compte qu'elle ne recouvrait pas toutes les fonctions calculables (en un sens encore intuitif). Le schéma de définition par récurrence utilisé pour définir ces fonctions est bien récursif au premier sens du terme : une fonction est définie en fonction d'elle-même.
Jacques Herbrand décrivit, dans une lettre adressée à Kurt Gödel en 1931, un modèle de calcul des systèmes d'équations[4] avec un mécanisme d'évaluation symbolique « par valeur », comme on dirait[style à revoir] maintenant[Quand ?]. Ce modèle fut précisé par Gödel lors d'exposés à Princeton en 1934. Les fonctions ainsi calculées furent appelées fonctions récursives générales. Les systèmes d'équations de Herbrand-Gödel utilisent de façon libre des appels récursifs de fonction au premier sens de ce terme. L'équivalence démontrée, par Stephen Cole Kleene, de cette définition avec celle des fonctions λ-calculables et des fonctions calculables par machine de Turing fournit des arguments pour la thèse de Church-Turing, qui énonce que ces modèles capturent effectivement la notion intuitive de fonction calculable[5].
On utilise parfois plus spécifiquement le terme de fonctions récursives pour les fonctions récursives au sens de Kleene, ou fonction μ-récursives, l'une des définitions possibles de fonctions calculables, introduite par Kleene en 1936 qui laisse le calcul implicite. Cette définition généralise celle des fonctions récursives primitives[6].
Enfin, le théorème du point fixe de Kleene est lié à son théorème de récursion, qui permet entre autres de justifier l'utilisation des définitions récursives de fonctions (au sens premier de ce terme).
Exemples
- Les programmes informatiques qui s'arrêtent (lors de leur exécution sur n'importe quelle entrée) sont des fonctions calculables.
- Le calcul d'un PGCD est une fonction calculable.
- La fonction qui prend en entrée une machine de Turing (représentée par un entier) et une entrée pour cette machine, et leur associe 1 si cette machine s'arrête sur cette entrée, rien sinon, est une fonction semi-calculable. Seule une application du principe du tiers exclu permet d'étendre cette fonction en une fonction totale qui donne 0 si la machine considérée ne s'arrête pas sur l'entrée considérée, mais cette fonction n'est alors pas calculable (pour plus d'informations voir l'article Problème de l'arrêt).
- Les fonctions constantes sont calculables. Une conséquence du principe du tiers exclu est alors que la fonction constante qui à un entier associe 1 si la conjecture de Goldbach est vraie et 0 si elle est fausse est calculable, bien qu'on ne sache pas aujourd'hui si la conjecture est vraie. Ceci montre comment l'application de ce principe détruit toute notion intuitive de calculabilité.
Ensemble récursif
De façon cohérente avec la définition précédente, un ensemble récursif est un ensemble d'entiers naturels ou de n-uplets d'entiers naturels dont la fonction caractéristique est récursive. Cela signifie que l'on peut décider mécaniquement de l'appartenance ou non à cet ensemble. On dira également ensemble décidable, le problème de décision de l'appartenance ou non d'un entier, ou n-uplet d'entiers, à cet ensemble étant décidable. Un ensemble récursivement énumérable est un ensemble qui est l'ensemble de définition, ou de façon équivalente (à l'ensemble vide près), l'ensemble image, d'une fonction récursive partielle. L'équivalence se démontre en faisant intervenir le calcul de la fonction.
Via des codages à la Gödel, on peut généraliser ces notions aux langages formels. On parle par exemple de langage récursif ou décidable. En logique mathématique, une théorie récursive, ou théorie décidable est une théorie dont l'ensemble des théorèmes est récursif. Une théorie récursivement axiomatisable est une théorie pour laquelle on peut trouver un ensemble d'axiomes récursif, ou de façon équivalente, dont l'ensemble des théorèmes est récursivement énumérable.
Logique informatique (programmation)
Du point de vue de la programmation, une fonction récursive est une fonction, au sens informatique de ce terme, qui s'appelle elle-même dans sa définition ; on parle également de définition récursive ou d'appel récursif de fonction.
Notes et références
- Cet article est partiellement ou en totalité issu de l'article intitulé « fonction calculable » (voir la liste des auteurs).
- Depuis l'avènement de l'informatique, on dirait un programme.
- (en) G. Boolos et R. Jeffrey, Computability and Logic, Cambridge University Press, (réimpr. 2002, 4e éd) (ISBN 0-521-00758-5), « Recursive functions are abacus computable », p. 70-88
- M. Minsky, Computation: Finite and infinite Machines, Englewood Cliffs, Prentice Hall, (réimpr. 1972), 317 p. (ISBN 0131654497)
- Michel Bourdeau et Jean Mosconi, Anthologie de la calculabilité, Paris, Cassini, 816 p. (ISBN 284225094X), « Note introductive à la correspondance entre Jacques Herbrand et Kurt Gödel ».
- P. Vollat, Calculabilité effective et algorithmique théorique Broché, Eyrolles, , 186 p. (ISBN 2212081685)
- Boolos et Jeffrey, op. cit., chap. 8 Turing computable functions are recursive, conclusion, p. 93.
Bibliographie
- Introduction à la calculabilité, Pierre Wolper Chapitres 5 et 6, 3ème édition.
- (en) Alan Turing, On Computable Numbers, with an Application to the Entscheidungsproblem : Proceedings of the London Mathematical Society, London Mathematical Society, (DOI 10.1112/PLMS/S2-42.1.230, lire en ligne) et « [idem] : A Correction », Proc. London Math. Soc., 2e série, vol. 43, , p. 544-546 (DOI 10.1112/plms/s2-43.6.544, lire en ligne)
