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 :

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

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

PDF - 108.8 ko
PDF - 68.8 ko
PDF - 100.6 ko
PDF - 104.9 ko
PDF - 121.3 ko

[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

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 8 février 2017, 14h-18h, campus du Tampon, amphi 120 B
- Mercredi 8 mars 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 12 avril 2017, 14h-18h, campus du Tampon
- Mercredi 3 mai 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mardi 13 juin 2017, 14h-18h, campus du Tampon
- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6

Semaine des mathématiques

Du 23 mars au 4 avril 2017 dans l’académie de la Réunion.


Brèves

Travailler à plusieurs

lundi 19 décembre 2016

Les enseignements d’exploration au lycée imposent aux enseignants de travailler ensemble. Chantal Tuffery-Rochdi a analysé dans sa thèse les pratiques des enseignants de MPS (méthodes et pratiques scientifiques). Elle répond aux questions des Cahiers pédagogiques.

Un document sur Eduscol

mardi 19 mai 2015

Un document clarifiant bien la façon dont les mêmes concepts vivent en mathématiques et dans les sciences « exactes » les utilisant, publié par Eduscol en octobre 2014. Citons-les :
« Le document proposé ci-dessous s’adresse aux professeurs de mathématiques, physique-chimie et sciences de l’ingénieur intervenant dans le segment [Bac-3 ; Bac+3]. Il vise à les informer des différences de présentation et d’interprétation qui sont faites de certains concepts mathématiques dans les autres disciplines. Ces éclaircissements peuvent contribuer à harmoniser et à clarifier l’utilisation de ces notions auprès des élèves. »

Les métiers des mathématiques et de l’informatique

dimanche 22 mars 2015

Une brochure de l’ONISEP réalisée à l’initiative des cinq sociétés savantes, Femmes & Mathématiques, Société informatique de France, Société française de statistique, Société de mathématiques appliquées et industrielles, Société mathématique de France, représentant l’ensemble de la communauté française d’informatique et de mathématiques.

Histoire de la comptabilité

vendredi 28 décembre 2012

Sur ce site (en anglais) dédié à la comptabilité, on trouve des informations intéressantes sur l’histoire et les pratiques de ce domaine, qui peuvent être utiles aux professeurs enseignant des mathématiques financières (et aussi aux autres...).

La CGE et la réforme des lycées

lundi 16 janvier 2012

La Conférence des Grandes Écoles publie 19 préconisations pour la réforme du lycée.

Sur le Web : Les 19 préconisations

Pratique des mathématiques en série STD2A

lundi 16 janvier 2012

Le site de l’IGEN offre des recommandations et des ressources pour enseigner les mathématiques en série STD2A. Les thèmes abordés (couleurs et nuances de gris, arcs et architecture, jeux vidéos, photo et tableur, perspectives parallèles...) sont de nature à donner aussi des idées d’activités aux enseignants des autres séries !

En cheminant avec Kakeya

lundi 16 janvier 2012

Un livre (à télécharger) de Vincent Borelli et Jean-Luc Rullière qui présente le calcul intégral et la dérivation en s’appuyant sur la question de Kakeya. Pour les lycéens, les étudiants et tous les esprits curieux qui souhaitent voir les mathématiques sous un jour différent.

Sur le Web : Livre à télécharger

Bicentenaire Galois

lundi 12 septembre 2011

À l’occasion du bicentenaire de la naissance d’Évariste Galois (1811-2011), l’Institut Henri Poincaré et la Société mathématique de France organisent un ensemble de manifestations et proposent un site contenant diverses ressources documentaires susceptibles d’intéresser les enseignants.

Statistiques

Dernière mise à jour

jeudi 23 février 2017

Publication

732 Articles
Aucun album photo
125 Brèves
11 Sites Web
126 Auteurs

Visites

41 aujourd'hui
1056 hier
1929202 depuis le début
6 visiteurs actuellement connectés