Depuis la méthode de Newton, on sait comment résoudre rapidement certaines équations : On les met sous la forme x=f(x) et on itère f. Par exemple, si f(x)=1-x²/4, on peut calculer f(x) avec cet algorithme :

• élever x au carré ;
• diviser le résultat par 4 ;
• lui soustraire 1 ;
• prendre l’opposé.

On peut vérifier avec ce petit programme sofus :

La convergence vers un nombre proche de 0,828 est assez rapide. En fait ce nombre est un point fixe de f, c’est-à-dire un nombre x tel que f(x)=x : En résolvant l’équation du second degré 1-x²/4=x, on trouve que la solution positive est √8-2 qui vaut environ 0,828.

En fait, en dimension 2, il y a des phénomènes similaires, ici en multipliant un vecteur de dimension 2 par 0,4 avant de lui additionner le vecteur (0,1), les abscisses tendent vers 0 et les ordonnées vers 5/3 :

L’idée générale est que si une application est contractante (comme c’est le cas ici), ses itérées convergent vers un point fixe. Ce qui fournit un moyen de calculer des valeurs approchées du point fixe. Topologiquement, ce résultat a mené au théorème du point fixe de Brouwer ; Les applications en sont très nombreuses notamment pour la résolution de certaines équations intégrales à noyau, en itérant un opérateur de Fredholm. On peut penser aussi à la construction de fractales par système de fonctions itérées.

Le théorème de récursion de Kleene est un peu la même histoire mais pour les suites d’entiers : Une suite d’entiers qui est croissante et bornée est constante à partir d’un certain rang, et on peut obtenir cette constante en faisant boucler l’algorithme définissant la suite suffisamment longtemps.

En λ-calcul, on travaille non sur des fonctions sur entiers, mais sur des fonctionnelles (fonctions portant sur des fonctions, voire ici, sur elles-mêmes). Un exemple de fonctionnelle est la dérivation, qui, à une fonction f, associe sa dérivée f’, qui est aussi une fonction. Chercher un « point » fixe de la dérivée, c’est chercher une fonction égale à sa dérivée, c’est-à-dire résoudre une équation différentielle. Mais le λ-calcul va plus loin que ça, parce qu’on ne peut pas dériver la dérivation, on travaille donc sur d’autres fonctionnelles que la dérivation.

En λ-calcul, un combinateur est une λ-expression sans variable libre. Graphiquement, c’est une famille d’alligators dans laquelle tout œuf est surmonté d’un alligator de même couleur, il est donc facile de reconnaître visuellement des combinateurs. Certains exemples classiques sont

• les booléens.
• les entiers.

Mais il y a des combinateurs particulièrement intéressants :

• λx.x noté I (comme « identité ») ;
• λx.λy.x noté K (comme « constante » : C’est la fonctionnelle qui transforme x en la fonction constante égale à x). On note que c’est le booléen « true » en λ-calcul ;
• λx.λy.λz.x z (y z) noté S (comme « substitution »). Il se dessine ainsi comme famille d’alligators :

Sa « recette » dans le jeu est

λa.λb.λc.a c (b c)

(on a remplacé les x,y,z par des a,b,c).

Ces combinateurs sont intéressants parce qu’ils permettent, à eux trois, de faire du λ-calcul avec des règles de réécriture sur les chaînes de caractères écrites sur le vocabulaire S, K, I. Le jeu des alligators permet de faire cela, par exemple si on veut calculer SKSK, on copie S dans la console du jeu, puis K, le tout deux fois, à partir du tableau ci-dessous. Puis on joue pour voir ce que ça donne.

On constate qu’à la fin du jeu il ne reste plus que K : SKSK se réduit en K. Quelques combinateurs intéressants peuvent être construits avec S, K et I :

• « false » (λa.λb.b) qui se construit comme SK
• « not » également noté C par Curry, qui se construit comme S (S (K (S (K S) K)) S) (K K) ;
• λc.(λb.(λf.(c (b f)))) noté B par Curry combinateur de composition) , qui se construit comme S(KS)K ;
• λc.(λf.(c f f)) noté W, qui se construit comme SS(SK).
• le combinateur U ou ω qui se construit comme SII.

Comme tout le λ-calcul peut être mené uniquement à l’aide de B, C, K et W (thèse de Curry), et que ces 4 combinateurs sont définissables dans SKI, on en déduit que le λ-calcul est réductible à SKI, donc à un traitement sur les chaînes de caractères (grammaire générative et transformationnelle). Et même avec S et K seuls puisque SKK se réduit à I :

Après avoir copié-collé S dans la console puis cliqué daux fois sur « true » (qui est K), on a cette population :

(λa.λb.λc.a c (b c))  (λa.λb.a) (λa.λb.a)

Une famille plutôt grande :

Mais le premier K est à la portée de S, et va donc se faire ingurgiter pour ressusciter en bas à gauche (avec changement de couleur) :

L’expression est alors légèrement simplifiée :

λb.(λc.(λd.(λe.(d)) c (b c ))) λa.(λb.(a))

C’est donc le tour du second K de se faire manger :

L’expression s’est encore simplifiée :

λc.(λd.(λe.(d)) c (λa.(λf.(a)) c))

L’alligator gris passe à table :

ce qui simplifie encore l’expression :

λc.(λe.(c) (λa.(λf.(a)) c))

Mais toute une famille se trouvant à portée de bouche de l’alligator vert, une simplification plus considérable est prévisible :

C’est I qui a été produit :

λc.(c)

Ainsi, le λ-calcul peut se faire à l’aide des deux seuls combinateurs S et K. En fait on même le définir à l’aide d’un seul combinateur : iota [1] Ce mystérieux combinateur, appliqué à lui-même, donne l’identité. Il s’écrit λx.(x S K) soit

(λx.x (λa.λb.λc.a c (b c)) (λa.λb.a))

Voici son portrait :

On peut vérifier qu’il donne bien l’identité lorsqu’on l’applique à lui-même, en entrant

(λx.x (λa.λb.λc.a c (b c)) (λa.λb.a))(λx.x (λa.λb.λc.a c (b c)) (λa.λb.a))

puis en laissant évoluer la population ; il faut 9 étapes pour arriver à l’identité. Par ailleurs

• ιI (iota suivi de I) se réduit en « false »
• ι(ι I) se réduit en K ;
• et ιK se réduit en S.

On peut donc faire du λ-calcul avec un seul combinateur (résultat à comparer avec l’opérateur de Sheffer en logique propositionnelle).

Mais un combinateur est particulièrement intéressant : Le combinateur U ou ω qui dans SKI se construit comme SII et qu’on va voir de façon plus approfondie dans ce qui suit.

La λ-expression λa.a a est particulièrement fascinante, parce qu’elle ne se réduit pas, mais aussi parce qu’elle a pour effet d’appliquer une fonction (ou une fonctionnelle) à elle-même. Ce qui, on peut le dire, n’est pas d’un usage très courant en mathématiques... Par exemple, si on essaye de définir cette fonctionnelle en CoffeeScript on écrit simplement (ici dans alcoffeethmique :

U = (f) -> f f
affiche U

Si maintenant on essaye

U = (f) -> f f
affiche U 2

on a un message d’erreur disant que 2 n’est pas une fonction.

Alors on essaye avec une « vraie » fonction :

U = (f) -> f f
affiche U cos

Mais cette fois-ci on a « NaN » qui n’est guère mieux. En fait on peut appliquer une fonction à elle-même si c’est une fonction constante :

U = (f) -> f f
affiche U (x)->2

Là on a 2 qui est le résultat qu’on obtient en appliquant la constante 2 à elle-même [2].

En fait on peut appliquer U à un entier de Chuch, ce qui a pour effet de l’élever à sa propre puissance. Mais on peut aussi l’appliquer à « false » par exemple ce qui donne l’identité, ou à « IF » ce qui donne « IF » lui-même. Mais en l’appliquant à « OR » on a une expression qui ne se réduit pas, puisqu’on arrive à cette population qui, au bout de 4 générations, redevient elle-même :

Les expressions sont

λq.(λa.(λb.(a a b)) λa.(λb.(a a b)) q)


λq.(λb.(λc.(λd.(c c d)) λc.(λd.(c c d)) b) q)


λq.(λc.(λd.(c c d)) λc.(λd.(c c d)) q)

λq.(λd.(λa.(λb.(a a b)) λa.(λb.(a a b)) d) q)

Le plus amusant c’est qu’on peut appliquer ce combinateur à lui-même ; mais le résultat ne se réduit jamais [3]. Cette fois-ci, la période est 2 :

Le combinateur obtenu ressemble à une quine (informatique) : Un programme qui s’affiche lui-même...

D’autres combinateurs donnent lieu à des populations d’alligators qui ne se stabilisent jamais, soit parce qu’elles oscillent, soit parce qu’elles grossisent sans cesse : Les combinateurs de point fixe. En particulier

• (λx. λy. x y x) (λy. λx. y (x y x)) que voici (elle fait un peu peur non ?) :

• λf.(( λx.( f (x x)) λx.(f (x x)))) noté Y (le héros de cet article) que voici :

• (λx. λy. (y (x x y))) (λx. λy. (y (x x y))) (combinateur de Turing) que voici :

En appliquant Y à not et en essayant de réduire l’expression obtenue, on a une population intéressante. Voir le portfolio en bas de cet article pour les étapes successives de son évolution et les arbres correspondants.

Il faut dire que « not » de par sa définition, échange ses deux entrées. Or chercher un point fixe de la négation, c’est chercher une proposition équivalente à sa négation, on risque de chercher longtemps...

Comme le λ-calcul autorise qu’on applique une fonction à elle-même, rien n’empêche d’appliquer Y ... à Y lui-même ! La structure évolue vers une sorte d’arbre fractal :

On peut réduire l’implication à

λx.(λy.(y y λa.(λb.(x b a))))

(en entrant λx.λy.(or y not(x) et en fermant les parenthèses, puis en réduisant on obtient le dessin ci-dessus ; on peut le tester en l’appliquant à toutes les combinaisons de true et false et en vérfiant qu’on construit ainsi la table de vérité de l’implication). Cette implication permet de définir une fonctionnelle qui, à a, associe la valeur de vérité de a⇒b :

En appliquant le combinateur Y à cette fonctionnelle, on affirme que sa vérité implique celle de b. Et ceci, quelle que soit la vérité de b. C’est le paradoxe de Curry :

Voici une série d’articles présentant le paradoxe de Curry par une progression allant d’une pseudo-preuve ontologique de l’existence de Dieu à une apologie de la logique intuitionniste, et ressemblant par certains aspects à la démonstration des théorèmes d’incomplétude de Gödel présentée en bas de cet article. Ils sont destinés à être lus un par un, en laissant le temps de réfléchir à chacun avant de lire le suivant : Un feuilleton...