Les fonctions récursives constituent une manière de définir ce qu’est un calcul par le seul langage des nombres entiers. L’idée consiste à partir de quelques fonctions extrêmement simples, considérées comme évidemment calculables, puis à autoriser un petit nombre de procédés pour en fabriquer de nouvelles à partir des anciennes. Parmi ces procédés figure la récursion proprement dite, qui définit la valeur d’une fonction pour un nombre donné en s’appuyant sur sa valeur pour le nombre précédent, un peu comme on gravirait un escalier en calculant chaque marche à partir de celle d’en dessous. En combinant ces briques élémentaires et ces règles de construction, on parvient à définir une immense famille de fonctions sur les entiers, censée coïncider avec tout ce qui est réellement calculable.
Cette approche s’est élaborée dans les années 1930 sous l’impulsion de plusieurs logiciens, notamment Kurt Gödel, qui s’appuya sur des idées antérieures de Dedekind et d’autres, ainsi que Stephen Kleene qui en développa la théorie. Il fallut cependant enrichir la définition initiale, dite récursion primitive, car elle laissait échapper certaines fonctions pourtant calculables. On y ajouta un procédé supplémentaire, la recherche du plus petit nombre satisfaisant une condition, donnant naissance aux fonctions récursives générales. Le résultat majeur fut de constater que cette famille coïncide exactement avec les fonctions calculables par une machine de Turing et avec celles définissables en lambda-calcul, trois routes distinctes menant au même sommet.
L’intérêt de ce modèle tient à sa proximité avec les mathématiques ordinaires et à la manière dont il éclaire la notion de calcul par la seule idée de construction progressive. La récursion qu’il met en avant est d’ailleurs devenue un concept fondamental de la programmation, où une fonction peut s’appeler elle-même pour résoudre un problème en le ramenant à des cas plus petits, technique omniprésente pour parcourir des structures ou décomposer des tâches complexes. Cette convergence entre fonctions récursives, machines de Turing et lambda-calcul reste l’un des arguments les plus forts en faveur de la thèse de Church-Turing, en montrant que la notion de calculable ne dépend pas de la façon particulière dont on choisit de la formaliser.
Laisser un commentaire