Le Y du λ : plus qu’une symétrie centrale, un paradoxe

mercredi 27 mai 2015
par  Alain BUSSER

En mettant un λ à l’envers, on a un Y. D’où le titre de cet article, mais ce titre est trompeur puisqu’il ne s’agira nullement de symétrie centrale appliquée à des lettres mais de théorèmes du point fixe.

Mouvement vers point fixe

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.

Combinateurs

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

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.

Lettres λ-équivalents
I (λa.a)
K (λa.λb.a)
S (λa.λb.λc.a c (b c))

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.

auto-référence

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 :

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

Télécharger

Si maintenant on essaye

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

Télécharger

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

Alors on essaye avec une « vraie » fonction :

  1. U = (f) -> f f
  2. affiche U cos

Télécharger

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 :

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

Télécharger

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...

Points fixes en λ-calcul

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 :

Le combinateur Y de Curry est dit

  • paradoxal (pour des raisons exposées plus bas) ;
  • ou de point fixe : En effet, si on essaye de l’appliquer à une fonction g (l’œuf saumon), on a successivement :

qui peut se résumer en Yg=g(Yg) :

  • Yg est un point fixe de g.
  • Lequel ?
  • Un point fixe.
  • Oui mais si g n’a pas de point fixe ?
  • Yg est un point fixe de g, puisqu’on vous le dit !
  • Même s’il n’y en a pas ?
  • Même s’il n’y en a pas.

Y not ? Pourquoi pas ?

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 :

En fait, grâce à « leq » on peut définir des fonctions pour lesquelles la boucle induite par Y s’arrête, et ceci permet de définir par exemple la factorielle en λ-calcul.

Curry Y va au paradoxe

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 :

Paradoxe de Curry

Si cette phrase est vraie, alors 2+2=5

On rappelle que la fausseté de a⇒b équivaut à a∧¬b

  • Si la phrase ci-dessus était fausse, alors
    • elle serait vraie
    • (et 2+2 ne serait pas égal à 5)
  • Alors qu’elle soit vraie ou fausse, en définitive elle est vraie. Bon, c’est simple finalement, la phrase « si cette phrase est vraie alors 2+2=5 » ne peut pas être fausse, donc elle est vraie.

Oui, mais c’est une implication dont la prémisse est vraie (puisque la prémisse est la phrase même). Donc sa conclusion est vraie aussi : 2+2=5 cqfd

2+2=5 ???
Quoi ? C’est quoi cette histoire ?
Curry peut démontrer que 2+2=5 ?
Ah avec ces expériences nucléaires ils ont tout déréglé les saisons. Où va-t-on Mâme Michu ? Voilà que maintenant 2+2=5...

On l’aura compris, le paradoxe est autoréférentiel et provient du fait que s’il suffit qu’une implication suppose sa propre prémisse pour que la conclusion soit vraie, le résultat est paradoxal chaque fois que la conclusion est fausse, soit dans la moitié des cas.

Maintenant on remarque qu’à un moment du raisonnement ci-dessus, se trouve l’affirmation « si elle n’est pas fausse, c’est qu’elle est vraie ». Le paradoxe de Curry perd donc son caractère paradoxal en logique intuitionniste puisque cette partie du raisonnement est basée sur le principe du tiers exclu qui n’est pas adopté par la logique intuitionniste. Autre boucle autoréférentielle : La logique intuitionniste est de Brouwer, le célèbre auteur du théorème du point fixe : La boucle est bouclée !

Une autre présentation du paradoxe

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...


[1un interpréteur en ligne a été écrit en Javascript.

[2en fait on obtient le résultat 2 en appliquant la fonction constante 2 à n’importe quelle fonction, que ce soit elle-même ou une autre.

[3ce que JavaScript exprimait avec son « too much recursion »


Commentaires