récursivité
Théorie destinée à fournir un cadre rigoureux à l'étude des notions intuitives de calculabilité et de décidabilité effectives. (Church a montré [1936] que la récursivité est l'équivalent mathématique de la calculabilité effective : la fonction récursive est une fonction rigoureusement calculable.)
Les procédures effectives sont des opérations familières : additionner deux ou plusieurs nombres entiers, diviser un entier par un autre plus petit que lui, diviser successivement un premier entier par un second (plus petit), le second par le reste de la première division, ce reste par celui de la seconde division et ainsi de suite jusqu'à un reste égal à 0 ou à 1 (recherche du plus grand commun diviseur par l'algorithme d'Euclide).
On voit qu'une procédure effective consiste en la répétition un nombre fini de fois de certaines opérations, en nombre fini, données initialement. Le concept mathématique correspondant à cette description est celui de fonction récursive.
Utilisé par R. Dedekind dès 1888, ce concept s'est imposé, dans le premier tiers du xxe s., grâce à certains travaux logiques liés au fameux problème de la décidabilité. Diverses approches en sont faites par K. Gödel et J. Herbrand, par A. Church et S. Kleene, par A. Turing, par E. Post, par A. Markov. Une convergence remarquable s'établit, car on peut montrer que chacune des différentes définitions équivaut à l'autre.
La définition la plus pratique et la plus intuitive (relativement aux moyens techniques modernes) est certainement celle qui détermine la classe des fonctions « calculables par programme » en s'inspirant de l'informatique. Une fonction est calculable par programme s'il existe un programme tel que si, au début du calcul, on met en mémoire la valeur des variables de la fonction dans des registres numérotés de 1 à n selon le nombre de variables et la valeur 0 dans les autres registres, alors ou bien le programme s'arrête avec la valeur de la fonction dans le registre 1, ou bien il ne s'arrête jamais, selon que la fonction est calculable ou non.
On démontre que toute fonction récursive est calculable par programme. La réciproque est généralement admise en vertu de la « thèse de Church », énoncé non démontré mais justifié par l'expérience : chaque fois qu'on a défini des mécanismes de calcul (machines de Turing, algorithmes de Markov, processus combinatoires finis de Post, etc.), on a pu démontrer qu'ils définissaient des fonctions récursives.
Les applications des fonctions récursives sont nombreuses, aussi bien en logique qu'en mathématiques. Un exemple récent est la solution négative du dixième problème de Hilbert. Celui-ci cherchait s'il existait un procédé effectif pour décider, pour tout polynôme à coefficients entiers, s'il a des solutions entières. I. Matijasevič a démontré en 1970 qu'un tel procédé n'existait pas, en utilisant les notions d'ensemble récursif et d'ensemble récursivement énumérable dont les définitions sont dérivées de celle de fonction récursive.