récursivité
Cet article est extrait de l'ouvrage Larousse « Dictionnaire de la philosophie ».
Terme apparu dans les années 1960.
Logique, Mathématiques
Se dit de toute procédure algorithmique permettant d'appréhender l'infini.
Ainsi peut-on caractériser la définition récursive de l'addition comme le fait d'ajouter une unité à un premier élément 0, puis d'itérer indéfiniment cette opération. Ce qui s'écrit :
1° – x + 0 = x
tab 2° – x + Sys20 = S(x + y).
La première équation introduit l'addition pour 0. La seconde l'introduit pour le successeur immédiat (noté S) de y. Comme y peut prendre n'importe quelle valeur, l'équation devient applicable au résultat obtenu. L'addition s'applique au résultat de l'addition.
En mathématiques, le principe de récurrence ou d'induction complète « Si s est une classe à laquelle 0 appartient ainsi que le successeur de chaque nombre appartenant à s, alors chaque nombre appartient à s » constitue depuis Euclide, Pascal et Fermat le raisonnement par excellence.
En 1936, Church proposa d'assimiler la notion intuitive d'effectivité au concept logique de récursivité (thèse de Church) et il prouva qu'il existait en arithmétique élémentaire des problèmes insolubles (théorème de Church)(1).
Denis Vernant
Notes bibliographiques
- 1 ↑ Kleene, S.C., Logique mathématique, Armand Colin, Paris, 1971, ch. v, pp. 231-261.