Quand le fini engendre l'infini : récursion et vertige de l'illimité

Un programme tient en quelques lignes ; son exécution peut ne jamais s'arrêter. Ce simple constat cristallise l'un des problèmes les plus profonds à la croisée de l'informatique, des mathématiques et de la philosophie : comment une description finie peut-elle engendrer un comportement infini ? La récursion, cette opération par laquelle une procédure s'invoque elle-même, constitue le pont conceptuel entre ces deux rives. De Zénon d'Élée au lambda-calcul d'Alonzo Church, des fractales de Mandelbrot au problème de l'arrêt de Turing, l'histoire de la pensée n'a cessé de buter sur cette tension fondamentale entre le fini et l'infini, et la récursion en est à la fois l'instrument et la métaphore.

Cet article propose un parcours à travers ces connexions, en montrant comment la structure récursive irrigue aussi bien les paradoxes classiques de l'infini que les fondements de l'informatique théorique, et comment, aujourd'hui encore, elle soulève des questions métaphysiques irrésolues.

Les paradoxes de Zénon, ou la récursion avant la lettre

Vers 450 avant notre ère, Zénon d'Élée formulait ses célèbres paradoxes pour défendre la métaphysique de Parménide. Le plus connu, celui d'Achille et la tortue, possède une structure exactement récursive : Achille donne une avance à la tortue ; lorsqu'il atteint le point de départ de celle-ci, elle a progressé ; lorsqu'il atteint ce nouveau point, elle a encore avancé, et ainsi de suite, ad infinitum. Chaque étape engendre le même problème à une échelle réduite. Aristote rapporte dans la Physique (VI, 9, 239b15) : « Dans une course, le plus rapide ne peut jamais rattraper le plus lent, car le poursuivant doit d'abord atteindre le point d'où le poursuivi est parti. »

La dichotomie est plus révélatrice encore : avant de parcourir une distance, le coureur doit en parcourir la moitié ; avant cette moitié, le quart ; avant le quart, le huitième, à l'infini. Dans sa forme régressive, le paradoxe pose le problème d'une récursion sans cas de base : il n'existe pas de premier pas, pas de point d'ancrage à partir duquel le mouvement pourrait s'initier. Simplicius rapporte que Zénon affirmait : « Il est impossible de traverser un nombre infini de choses en un temps fini. » Bertrand Russell reconnaissait en 1914 que « les arguments de Zénon, sous une forme ou une autre, ont fourni les fondements de presque toutes les théories de l'espace, du temps et de l'infini qui ont été construites depuis son époque jusqu'à la nôtre » (Our Knowledge and the External World).

Ce que Zénon avait identifié sans le nommer, c'est le problème fondamental de toute récursion : la décomposition d'un processus en sous-processus identiques peut-elle jamais s'achever ? La réponse mathématique moderne, la convergence des séries géométriques, ne dissout pas entièrement le vertige philosophique. Elle montre qu'une somme infinie peut avoir une valeur finie (1/2 + 1/4 + 1/8 + ... = 1), mais elle présuppose que l'on puisse légitimement considérer cette somme infinie comme un tout achevé.

De l'infini potentiel à l'infini actuel : la grande fracture

C'est précisément sur ce point que s'est jouée la plus profonde querelle philosophique sur l'infini. Aristote, dans le livre III de la Physique (206a18-19), pose la distinction fondatrice : l'infini « a une existence potentielle ». Il distingue l'infini potentiel (δυνάμει ἄπειρον) — un processus toujours extensible d'un pas supplémentaire, mais jamais achevé — de l'infini actuel (ἐνεργείᾳ ἄπειρον), une totalité infinie existant comme un tout. Le premier est légitime ; le second, pour Aristote, n'existe pas. « L'infini ne persiste pas mais devient » (Physique III.7, 207b14).

Cette position a dominé la pensée occidentale pendant plus de deux millénaires. Elle trouve un écho direct en informatique : un programme récursif qui engendre les entiers naturels (n → n+1) est potentiellement infini au sens aristotélicien. Pour tout nombre atteint, un autre peut toujours être engendré. Mais l'ensemble ℕ tout entier, considéré comme totalité achevée — c'est une tout autre affaire.

La révolution survient avec Georg Cantor dans les années 1870-1890. Dans ses Beiträge zur Begründung der transfiniten Mengenlehre (1895-1897), Cantor ose ce qu'Aristote interdisait : traiter les totalités infinies comme des objets mathématiques à part entière. Son argument diagonal de 1891 démontre l'existence de plusieurs tailles d'infini : les nombres réels sont « plus nombreux » que les naturels. L'argument lui-même possède une structure récursive — on construit un nouvel élément en modifiant systématiquement le n-ième élément de la n-ième entrée d'une liste supposée exhaustive. « L'essence des mathématiques réside dans leur liberté », proclamait Cantor dans ses Grundlagen (1883).

Parallèlement, Richard Dedekind proposait en 1888 dans Was sind und was sollen die Zahlen? une définition de l'infini elle-même récursive : un ensemble est infini s'il peut être mis en bijection avec l'une de ses parties propres (les naturels se mettent en bijection avec les pairs via n ↦ 2n). Son théorème de définition par récursion (§126) justifie rigoureusement que pour tout ensemble Ω, tout élément initial ω₀ et toute fonction θ, il existe une unique fonction récursive ψ satisfaisant les conditions de base et de récurrence. C'est le fondement formel de toute computation récursive.

Hegel, de son côté, avait proposé dans la Science de la logique (1812) une distinction différente mais éclairante : la mauvaise infinité (schlechte Unendlichkeit) — la progression sans fin 1, 2, 3, ... qui ne s'accomplit jamais — contre la vraie infinité, autoréférentielle et contenant le fini en elle-même. La mauvaise infinité correspond à une boucle récursive sans terminaison ; la vraie infinité, à un point fixe — une structure qui se retrouve elle-même à travers sa propre transformation.

La récursion formalisée : du lambda-calcul aux limites du calculable

Les années 1930 voient la formalisation rigoureuse de la récursion. En 1936, Alonzo Church publie son lambda-calcul — un système formel d'une simplicité extrême (variables, abstraction λx.M, application M N) mais d'une puissance universelle. La même année, Alan Turing conçoit sa machine abstraite. Stephen Kleene démontrera dans son « Theorem XXX » que les fonctions partielles récursives, les fonctions Turing-calculables et les fonctions λ-définissables coïncident exactement — c'est la thèse de Church-Turing.

Le joyau conceptuel du lambda-calcul est le combinateur Y, découvert par Haskell Curry :

Y = λf.(λx.f(x x))(λx.f(x x))

Dans le lambda-calcul pur, les fonctions sont anonymes : aucune ne peut se référer à elle-même par son nom. Le combinateur Y résout ce problème en réalisant l'autoréférence par auto-application. Pour toute fonction F, Y(F) est un point fixe de F : F(Y(F)) = Y(F). Autrement dit, le combinateur Y transforme une description non récursive en processus récursif — il « noue la boucle » de l'autoréférence.

Ce mécanisme illustre une thèse philosophique profonde : l'autoréférence n'est pas une propriété primitive mais un effet émergent. Elle naît de la structure même du calcul, sans qu'il soit nécessaire de la postuler.

Sans ce cas de base, la récursion devient indécidable — et c'est exactement ce que Turing a démontré. Son théorème d'indécidabilité de 1936 (« On Computable Numbers, with an Application to the Entscheidungsproblem ») prouve qu'aucun algorithme ne peut déterminer, pour tout programme arbitraire, s'il s'arrêtera ou tournera indéfiniment. Le problème de l'arrêt est, fondamentalement, la question de savoir si un processus récursif est fini ou infini — et cette question est, en général, insoluble.

Autoréférence, boucles étranges et les limites du fini

L'argument diagonal de Cantor, le problème de l'arrêt de Turing et les théorèmes d'incomplétude de Gödel (1931) partagent une structure commune, identifiée par Haim Gaifman dans « Naming and Diagonalization, from Cantor to Gödel to Kleene » (Logic Journal of the IGPL, 2006) : la diagonalisation. Dans chaque cas, on construit, par un procédé récursif, un objet qui échappe à tout système supposé exhaustif.

Gödel, dans « Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I » (Monatshefte für Mathematik, 1931), utilise un codage récursif (le numérotage de Gödel) pour traduire les énoncés méta-mathématiques en énoncés arithmétiques. Il définit 45 fonctions primitives récursives pour manipuler ces codes, puis construit une proposition G qui affirme, essentiellement, « je ne suis pas démontrable dans ce système ». Si le système est cohérent, ni G ni sa négation ne sont démontrables. L'autoréférence, rendue possible par la récursion, révèle les limites intrinsèques de tout système formel suffisamment puissant.

Douglas Hofstadter a consacré deux ouvrages majeurs — Gödel, Escher, Bach (1979) et I Am a Strange Loop (2007) HAL — à explorer ces connexions. Sa notion de boucle étrange (strange loop) désigne « une structure cyclique qui traverse plusieurs niveaux dans un système hiérarchique » et où « en ne se déplaçant que vers le haut ou vers le bas, on se retrouve au point de départ ». Pour Hofstadter, la conscience elle-même émerge de telles boucles autoréférentielles dans le cerveau : « Au bout du compte, nous, mirages autoperceptifs et auto-inventifs, emprisonnés en nous-mêmes, sommes de petits miracles d'autoréférence » (I Am a Strange Loop, p. 363). La récursion devient ici non plus seulement un mécanisme de calcul, mais une hypothèse sur la nature de l'esprit.

Fractales et structures autosimilaires : l'infini dans le fini

Si la récursion engendre l'infini dans le temps (processus sans fin), elle l'engendre aussi dans l'espace. Les fractales, formalisées par Benoît Mandelbrot dans The Fractal Geometry of Nature (1982), sont des objets géométriques définis par des règles récursives simples mais exhibant une complexité infinie. Le triangle de Sierpiński, la courbe de Koch, l'ensemble de Cantor — chacun se construit par l'application répétée d'une même transformation à des échelles de plus en plus fines.

L'autosimilarité — la propriété qu'une partie reproduit la structure du tout — est la signature géométrique de la récursion. Chaque zoom révèle la même structure, indéfiniment. Cela pose une question philosophique aiguë : comment une règle exprimable en quelques symboles peut-elle « contenir » une complexité infinie ? Pour un platonicien, la règle récursive décrit un objet infini préexistant. Pour un constructiviste, elle le construit — et l'objet n'existe qu'en tant que processus de construction, jamais comme totalité achevée.

Les langages à évaluation paresseuse comme Haskell offrent une réalisation computationnelle fascinante de cette tension. On y définit des structures de données infinies — listes infinies, flots — qui se comportent comme des infinis actuels tout en n'étant calculées que sur demande :

Cette définition est circulaire en apparence — fibs apparaît dans sa propre définition. Elle fonctionne parce que l'évaluation paresseuse construit la liste élément par élément, à la demande. C'est l'infini potentiel d'Aristote rendu opérationnel : le processus peut toujours se poursuivre d'un pas, mais n'est jamais achevé. Le fondement mathématique en est le théorème du point fixe de Kleene : toute fonction continue sur un ordre partiel dirigé-complet possède un plus petit point fixe, calculé comme la limite de la chaîne ⊥ ⊑ f(⊥) ⊑ f(f(⊥)) ⊑ ...

Les débats contemporains : la récursion peut-elle atteindre l'infini ?

La question de savoir si le calcul peut véritablement « atteindre » l'infini alimente des débats vifs en philosophie de l'informatique. Une machine de Turing possède un programme fini mais opère sur un ruban potentiellement infini et peut fonctionner un temps potentiellement illimité. Martin Davis soulignait : « Un aspect crucial et souvent ignoré est que la théorie abstraite implique essentiellement l'infini mathématique, tandis que les ordinateurs physiques sont nécessairement des objets finis. »

Le débat sur l'hypercalcul pousse cette tension à son paroxysme. Jack Copeland, dans « Hypercomputation » (Minds and Machines 12, 2002), défend la possibilité théorique de machines qui dépasseraient les limites de Turing— par exemple des « machines de Zeus » qui effectueraient une infinité d'opérations en temps fini en divisant par deux la durée de chaque étape. Martin Davis a répliqué dans « The Myth of Hypercomputation » (2004) que ces modèles « reviennent à la remarque évidente que si des entrées non calculables sont admises, alors des sorties non calculables sont atteignables ».

Ce débat renvoie aux supertâches en philosophie. La lampe de Thomson (1954) — allumée puis éteinte à des intervalles de plus en plus courts (1 min, 1/2 min, 1/4 min...) — est-elle allumée ou éteinte après 2 minutes ? Paul Benacerraf a montré en 1962 que l'état final n'est pas logiquement déterminé par la séquence précédente d'états : la description est simplement incomplète. Le paradoxe se dissout en sous-détermination plutôt qu'en contradiction.

Plus fondamentalement, les axiomes de Peano définissent les nombres naturels par récursion (0 est un nombre ; tout nombre a un successeur), mais la théorie des ensembles ZFC nécessite un axiome d'infini séparé pour garantir l'existence d'un ensemble clos sous l'opération de successeur. Comme l'a noté Joel David Hamkins, « il semble étrange qu'on doive postuler l'existence d'un ensemble inductif pour qu'un ensemble inductif existe ». La récursion seule ne fait pas surgir l'infini de nulle part : il faut un acte ontologique supplémentaire — un axiome, une décision philosophique — pour passer de l'infini potentiel à l'infini actuel.

C'est sur ce point que se séparent les grandes écoles. Pour les finitistes de l'école de Hilbert, seule la récursion primitive — qui termine toujours — est épistémologiquement sûre ; l'infini n'est qu'un « élément idéal » utile (« Personne ne nous chassera du paradis que Cantor a créé pour nous », déclarait Hilbert dans « Über das Unendliche », 1926). Pour les intuitionnistes de Brouwer, les objets mathématiques n'existent que s'ils sont mentalement constructibles ; les ensembles infinis « restent pour toujours en cours de création, mais ne forment pas un domaine clos de choses existant en soi » (Hermann Weyl, 1946). Pour les platoniciens structuralistes comme Stewart Shapiro (Philosophy of Mathematics, 1997), les structures récursives décrivent des positions dans des structures abstraites indépendantes de l'esprit — la récursion découvre plutôt qu'elle ne crée.

La régression infinie, ou le cauchemar du programme sans ancrage

Le problème de la récursion sans cas de base trouve un écho direct dans l'un des plus anciens problèmes philosophiques : la régression infinie. Le trilemme d'Agrippa (rapporté par Sextus Empiricus dans les Esquisses pyrrhoniennes) affirme que toute tentative de justification aboutit soit à une régression infinie, soit à un cercle, soit à un arrêt dogmatique. C'est exactement l'analogue épistémologique du choix entre récursion infinie, récursion mutuelle et cas de base.

Thomas d'Aquin utilisait cette structure dans la première voie de la Somme théologique (I, Q.2, Art.3) : toute cause a une cause, mais « il est impossible d'aller à l'infini dans la série des causes motrices ». Il faut donc un Premier Moteur — un cas de base métaphysique. Lewis Carroll, dans « What the Tortoise Said to Achilles » (Mind, 1895), montrait qu'appliquer le modus ponens requiert une règle justifiant son application, laquelle requiert elle-même une justification — une régression logique infinie. Le fondationnalisme en épistémologie correspond au cas de base ; le cohérentisme à la récursion mutuelle ; l'infinitisme de Peter Klein (2007) à l'assertion audacieuse qu'une chaîne infinie de raisons peut légitimement justifier une croyance.

Conclusion : la récursion comme pensée de l'entre-deux

La récursion n'est ni pleinement du côté du fini ni pleinement du côté de l'infini — elle est le mécanisme par lequel l'un engendre l'autre. Une règle finie produit un processus potentiellement infini ; un cas de base transforme cet infini potentiel en résultat fini ; l'absence de cas de base ouvre sur l'indécidable. Leibniz, qui anticipait la pensée computationnelle avec son calculus ratiocinator et son système binaire, et dont les monades — substances simples contenant chacune un reflet de l'univers entier — préfigurent l'autosimilarité fractale, avait peut-être pressenti cette vérité : le fini et l'infini ne s'opposent pas mais se co-constituent par la récursion.

Les questions ouvertes restent vertigineuses. Si la conscience est, comme le suggère Hofstadter, une boucle étrange — un processus récursif qui se prend lui-même pour objet — alors l'esprit humain est-il un programme fini contemplant sa propre infinité potentielle ? Si les théorèmes de Gödel et de Turing montrent que tout système formel assez puissant contient des vérités qu'il ne peut démontrer et des questions qu'il ne peut décider, alors la récursion révèle-t-elle les limites constitutives de la raison finie face à l'infini ? Et si l'axiome d'infini est nécessaire pour que l'infini « existe » — si la récursion seule ne suffit pas — alors que dit cette insuffisance sur la nature de l'infini lui-même ?

Ces questions traversent les siècles sans s'épuiser. C'est peut-être là le signe le plus sûr que la récursion et l'infini ne sont pas seulement des objets de pensée, mais les conditions mêmes de la pensée — cette activité finie qui, indéfiniment, se relance elle-même.