Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Fonction récursive
Résumé
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.
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. Il est plus cohérent de définir les fonctions semi-calculables avant les fonctions récursives. Formellement, une fonction récursive est alors une fonction semi-calculable définie . On trouve de plus en plus souvent le terme de fonction calculable pour désigner une fonction récursive, qui est le terme historique. Mais ce dernier est encore très utilisé. Il y a plusieurs définitions équivalentes de fonctions calculables, l'une d'elles étant que ce sont les fonctions calculées par une machine de Turing dont le calcul termine pour toute entrée.
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 avec un mécanisme d'évaluation symbolique « par valeur », .
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.