La logique combinatoire selon Smullyan

jeudi 11 mai 2017
par  Alain BUSSER

En bas de cet article [1] était faite la recension d’un livre de Smullyan titré « to mock a mockingbird » et consacré à la logique combinatoire. Dans le présent article, on va montrer comment le λ-calculateur en ligne permet de vérifier les affirmations de Smullyan. Gare aux crocos !

Incroyables concaténations

C’est dans un autre de ses livres, « the lady or the tiger » [2], que Smullyan a introduit sa vision de la logique doxastique. Il évoquait une population dont les sains d’esprit ne croient qu’en des vérités, alors que les fous ne croient qu’en des choses fausses [3]. Dans cet univers, en notant f la proposition « je suis fou » et Bp la proposition « je crois que p », alors la proposition Bf est fausse quel que soit l’état de santé de l’interlocuteur :

  • soit il est sain d’esprit et dans ce cas f est fausse et il ne peut pas y croire ;
  • soit il est fou et dans ce cas f est vraie, et il ne peut pas y croire non plus (puisqu’il est fou et ne croit à rien de vrai).

Donc Bf est une antilogie. Mais BBf n’en est pas une : Puisque Bf est fausse, un fou y croira volontiers et même s’il ne croit pas être fou, il croit qu’il croit être fou ! C’est fou !

Voici une énigme proposée par Smullyan dans logical labyrinths (à propos d’un mari dont on aimerait savoir s’il est fou) :

My wife once said that I believe that she believes I am mad

On peut traduire la parole du mari en « Ma femme a dit un jour que je crois qu’elle me croit fou ». On demande l’état de santé mentale du mari. Si on note Bmp la proposition « le mari croit que p » et Bfp la proposition « la femme croit que p », alors l’énoncé de l’exercice s’écrit BmBfBmBff : Ce genre de proposition complètement folle est obtenue par concaténation à répétition des opérateurs modaux doxastiques : L’idée est que si p est une proposition, alors Bp en est aussi une, à laquelle on peut à son tour appliquer un opérateur modal pour avoir BBp etc : Les opérateurs modaux sont des cas particuliers de combinateurs.

Calculables concaténations

Toujours dans the lady or the tiger, il est question, dans toute la seconde moitié du livre, d’un certain McCulloch qui essaye de réaliser le rêve de Leibniz en construisant des machines effectuant de mystérieux calculs. Les opérations élémentaires de ces calculs sont les suivantes :

  • Le retourné d’un nombre est le même mais écrit à l’envers (inversion des chiffres). Par exemple le retourné de 6789 est 9876 ;
  • Le répété d’un nombre est son carré de concaténation ; par exemple le répété de 6789 est 67896789.
  • L’associé d’un nombre est presque pareil que son répété, sauf qu’on insère un « 2 » au milieu ; ainsi l’associé de 6789 est 678926789.

Pour simuler les machines de McCulloch, on peut utiliser sofus histoire de garder une sûre concision ! Dans une machine de McCulloch, les instructions sont des chiffres et on a donc besoin de lire et effacer le premier chiffre d’un nombre entier. Pour lire le dernier chiffre, on effectue une division euclidienne par 10 : Le reste est le dernier chiffre. Ensuite on utilise le fait que le premier chiffre d’un nombre est le dernier chiffre de son retourné :

La division euclidienne par 10 permet aussi de récupérer tous les chiffres sauf le premier :

L’associé se programme ainsi :

La deuxième machine de McCulloch est alors simulée par ce script :

Elle opère sur des nombres écrits sans le chiffre 0, et ne fonctionne pas sur les nombres d’un seul chiffre ou se terminant par un 2. Comme dans un système de tague, le premier chiffre joue le rôle de l’instruction en cours d’exécution, et est effacé après exécution (en fait, appel récursif), selon le code suivant :

  • 2 code un passage de paramètre (parenthèses dans le livre de Smullyan)
  • 3 code l’associé du nombre restant ;
  • 4 code le retourné des chiffres suivants ;
  • et 5 code le répété des chiffres suivants.

La machine de McCulloch est intéressante à explorer pour elle-même, par exemple il se pose des questions du genre « trouver x et y tels que chacun donne l’autre, après passage en machine ». Ou tout simplement « quels sont les nombres invariants après passage dans la machine ? » Voici un exemple de « point fixe » et de nombre qui donne son associé :

Voici les simulations des machines de McCulloch, au format Sofus :

machine 1 machine 2
Zip - 1.4 ko
Zip - 1.6 ko

Le fait que le chiffre 2 modélise l’application de la fonction codée avant lui, permet de faire de l’autoréférence : L’associé d’un nombre permet d’utiliser une telle autoréférence comme par le codage de Gödel, sans utiliser tout l’arsenal de la décomposition en facteurs premiers.

Et là encore, c’est la concaténation qui joue le rôle d’opération fondamentale, avec des chiffres qui codent des opérations sur des nombres : Les chiffres de McCulloch sont des cas particuliers de combinateurs.

Un combinateur est une λ-expression dont toutes les variables sont liées. Par exemple λx.x+y (fonction qui, à x, associe x+y) n’est pas un combinateur alors que λx.λy.x+y (fonction des deux variables x et y) en est un. Ce qui est impressionnant avec les combinateurs, c’est qu’on peut les combiner entre eux !

Voici la présentation de certains oiseaux combinateurs par Smullyan :

PDF -
description des principaux combinateurs par Smullyan

M

Le titre du livre est « to mock a mockingbird ». Le premier combinateur présenté est donc M, le « mockingbird ». Il a pour particularité que, quel que soit l’oiseau qu’on lui nomme, sa réponse est la même que celle de l’oiseau en question, en entendant son propre nom. Si l’oiseau nommé est noté x, on a Mx=x(x) noté x x, et donc, dans la notation du λ-calcul on a M=λx. x x :

Le titre du livre suggère d’appliquer M à M. Si on essaye de réduire la λ-expression (λx. x x) (λx. x x) obtenue, on a d’abord un renommage en λa.( a a ) λa.( a a ) puis en λa.( a a ) λb.( b b ) et finalement on applique M à λb.( b b ) ce qui donne λb.( b b ) λb.( b b ) : On voit une alternance entre

  • λa.( a a ) λa.( a a )
  • λb.( b b ) λb.( b b )

Soit M lui-même, sous deux formes différentes !

K

Un combinateur omniprésent dans le livre, et déjà présent dans le calculateur en ligne, sous le nom TRUE (clavier du calculateur) :

I

Le plus simple des combinateurs :

Sa recette est λa. a

Il vérifie IK=K, IM=M, II=I, etc. Il deviendra intéressant non pas lorsqu’on l’applique à un autre combinateur, mais lorsqu’on applique un autre combinateur à I.

L

La définition de L est λa.λb. a ( b b ) :

On a déjà une première recette pour fabriquer M :

En effet en réduisant (λa.λb. a ( b b )) (λa. a ) on a successivement :

Outre les parenthèses inutiles (le croco blanc), on reconnaît M ; donc LI=M.

W

Son expression est λx.λy.(x y y ) :

Pour calculer WI, on entre λx.(λy.(x y y ) ) (λa. a ) ; voici les étapes du calcul, montrant que WI=M :

On peut aussi vérifier que WK=I, en réduisant l’expression λx.(λy.(x y y ) )  (λa.λb.a) :

B

Le combinateur B sert à introduire des parenthèses :

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

Il a été présenté par Alonzo Church en 1941. Il est important parce qu’il permet de combiner des combinateurs.

D

On peut définir D=BB, ou par l’expression λb.λc.λe.λf.( ( b c ) ( e f ) ) ) :

E

Pour la suite, on regarde le combinateur DB=λc.λe.λf.λg.c ( ( e f ) g ) ) ) :

Le combinateur E peut s’obtenir en applicant B à ce dernier (DB), soit en réduisant l’expression (λa.λb.λc. a ( b c ) ) (λc.λe.λf.λg.c ( ( e f ) g ) ) ) ) :

On a finalement E = λb.λc.λe.λf.λg. ( b c ) ( (e f)  g )

C

Le combinateur C est un permutateur ; on l’obtient en cliquant sur le bouton NOT du calculateur en ligne ; l’expression obtenue ainsi est (λp.λa.λb.p b a).

Et comme K peut s’obtenir par un clic sur le bouton TRUE, Il suffit pour obtenir CKK, de cliquer successivement sur les boutons Not, True et True ; voici les étapes successives de la réduction de ce « nouveau » combinateur :

On a donc CKK=I : En combinant les combinateurs, on n’a pas nécessairement de nouveaux combinateurs.

T

Intéressons-nous maintenant au combinateur CI :

Le résultat, d’expression λa.λb.(b a), est noté T (comme « transposition ») ; c’est bien entendu lui aussi un combinateur de permutation.

Un exemple d’utilisation : BT se simplifie en λb.λc.λe.e ( b c). En appliquant ce combinateur à M, on a (λb.λc.λe.e ( b c)) (λx. x x) qui se simplifie en λc.λe.e ( c c ) = L ; et ML = (λx. x x) (λc.λe.e ( c c ) ) est un combinateur qui ne se réduit pas, mais qui a la propriété de commuter avec tout (autre) combinateur.

R

Essayons avec DT (expression (λb.λc.λe.λf.( ( b c ) ( e f ) ) ))  ( λa.λb.(b a))). Il paraît impressionnant comme ça :

Mais il se réduit :

Son expression dans le λ-calcul est λc.λe.λf.((e f) c )=λc.λe.λf.e f c ) : Il s’agit encore d’un combinateur de permutation, en l’occurence une rotation sur c,e et f, d’où son nom : R.

On le retrouve en réduisant BBT, mais aussi avec CC :

F

On va calculer BCR, soit (λa.λb.λc. a ( b c ))  (λp.λa.λb.p b a) (λc.λe.λf.e f c) à réduire :

L’expression finale est λc.λd.λe. e d c qui est aussi un combinateur de permutation : Il échange la première et la dernière variable sans bouger la seconde :

V

Maintenant on va calculer CF (expression (λp.λa.λb.p b a) (λc.λd.λe. e d c)) :

L’expression obtenue est λa.λb.λe. e a b = V : C’est un peu R à l’envers, puisqu’il fait une rotation sur trois variables, mais dans le sens inverse de ce que fait R. Bien entendu il s’agit là encore d’un combinateur de permutation.

À l’inverse, CV=F, en 4 étapes de réduction à partir de l’expression (λp.λa.λb.p b a) ( λa.λb.λe. e a b). Et RFR=V comme on le voit en réduisant (en 5 étapes) l’expression (λc.λe.λf.e f c) (λc.λd.λe. e d c) (λc.λe.λf.e f c )

G

Calculons ensuite BBC :

L’expression obtenue est G = λc.λe.λf.λg.c g ( e f ) :

S

S (comme « substitution ») est défini par S = λa.λb.λc. a c (b c) :

Il permet, en combinaison avec K et I, de fabriquer tous les combinateurs.

Si on calcule ST, on trouve, en trois étapes, λb.λc. (b c ) c = W.

Voici la description, par Smullyan, de ces combinateurs :

PDF -

Combinateurs de point fixe

Un combinateur de point fixe noté Θ par Smullyan (et appelé Tetras ou « sage bird », il faut les chercher longtemps !), a pour effet, quand on l’applique à une λ-expression x, de fournir un point fixe de x, ce qui signifie que x(Θx)=Θx. Il y a moyen d’en construire quelques-uns à l’aide des combinateurs précédents.

Q

En appliquant C à B, on construit le combinateur CB = λa.λb.λc. b ( a c ) :

Ce combinateur est noté Q. Eh oui, on en revient toujours aux histoires de Q...

Mais il sera utile pour le combinateur suivant.

O

En guise d’échauffement, on peut calculer BW ; après quelques réductions, on trouve λb.λc.λy.(( b c ) y y). En appliquant ce combinateur à Q on obtient, après réduction, O = λx.λy. y (x y ) :

On peut aussi construire O comme SI.

On peut vérifier aussi que OI=M :

L’intérêt essentiel de O est que si Θ est un combinateur de point fixe alors ΘO et OΘ en sont aussi.

Smullyan

En calculant BM(RMB), on trouve après de multiples réductions, λm.( ( m m ) ( λk.( k k ) m ) )  :

C’est un combinateur de point fixe.

On peut aussi en construire un en passant par QL = λb.λc. b λe. c ( e e ) :

Alors W(QL(QL)) = λy. y λe.( y ( e e ) λb.λc. y λe.( y ( e e ) ) ) est aussi un combinateur de point fixe :

Curry

Première étape

En simplifiant le combinateur BW, on obtient le combinateur que Smullyan note W* = λb.λc.λy.(( b c ) y y) :

Ensuite on réduit BWB comme W*B soit (λb.λc.λy.(( b c ) y y)) (λa.λb.λc. a ( b c )), qui, après 6 réductions, donne λc.λy.( c ( y y ) ) :

Seconde étape

En simplifiant WS = ( λx.λy.(x y y)) (λa.λb.λc. a c (b c)) on obtient, au bout de 6 réductions, λy.λc.( y c (y c ) ) :

Troisième étape

En combinant les combinateurs des deux étapes précédentes, on obtient WS(BWB) =  (λy.λc.( y c (y c ) ) ) (λc.λy.( c ( y y ) )) :

C’est le combinateur de point fixe de Curry ; il ne se réduit pas.

Turing

Première étape :

On réduit LQ = (λa.λb. a ( b b )) (λa.λb.λc. b ( a c )) :

On obtient λb.λe.λc. e ( ( b b ) c )

Deuxième étape

On combine W* de l’onglet précédent avec ce dernier combinateur, pour avoir (λb.λc.λy.(( b c ) y y)) (λb.λe.λc. e (  b b c ) ) à réduire :

Le combinateur obtenu est U = λx.λy. y (x x y) que Smullyan appelle combinateur de Turing. Et il se trouve que UU est un combinateur de point fixe...

Le voici dans toute sa splendeur :

U

En réduisant LO = (λa.λb. a ( b b )) (λx.λy. y (x y)), on trouve successivement :

LOL [4], on retrouve le combinateur U vu à l’onglet précédent !

Du coup LO(LO) est un combinateur de point fixe. Après les histoires de Q, on se retrouve avec des LO(LO)s !

Y

Le combinateur de Curry est une vieille vedette. En notant t=K (true) et f=KI (false) on a :

  • Yxt=t pour toute valeur de x (t ou f) ;
  • Yfy=t pour toute valeur de y (t ou f) ;
  • t AND Yty se simplifie en t ;

Ce qui amène à considérer que Y, si on l’interprète comme une proposition, représente l’implication ; mais cela mène alors au paradoxe de Curry : Yxy « implique » alors tout. Curry estime alors que Y ne doit pas être considéré comme une proposition,et donc certains combinateurs (Y par exemple) ne sont pas des propositions.

Pour faire de la logique propositionnelle avec t et f, on remarque que

  • Si on réduit Vft on a λe.e λd.d

Or si on applique ce combinateur à t on a f, mais si on applique le combinateur à f on a I (on espérait t).

  • Si on réduit Rf on a λe.λf.(e f λa.λb.b ) . Là encore, en appliquant ce combinateur à t et t, on n’a pas t mais λe.(e λa.(λb.b) ) ...
  • Idem pout Tt (disjonction) et Rt (implication).

Moralité : Il faut parfois éviter de réduire un combinateur seul (sans les propositions).

La fonction successeur est, chez Smullyan, représentée par le combinateur Vf = λa.λb.λe. e a b. Alors

  • le nombre 0 est représenté par I = λd.d
  • le nombre 1 est représenté par λe.e λd.d
  • le nombre 2 est représenté par λb.λe.e b λd.d
  • le nombre 3 est représenté par λb.λe.e λf.(f b λd.d)

Voici la partie du livre traitant des applications de la logique combinatoire à la logique propositionnelle et à l’arithmétique :

PDF -

Combiner les combinateurs

BTMI

K a la propriété de réduire le nombre de variables ; du coup on ne peut pas le construire avec des combinateurs non réducteurs, et chacun des systèmes suivants engendre un λ-calcul restreint noté λI-calcul :

  • B, T, M et I (Alonzo Church) ;
  • B, C, W et I (Haskell Curry) ;
  • B, C, S et I (Smullyan) ;

S,K

Par contre tous les combinateurs, sans exception, peuvent s’obtenir en combinant S et K ; déjà, en simplifiant SKK=(λa.λb.λc. a c (b c))  (λa.λb.a) (λa.λb.a) [5], on obtient λc. c soit I : SKK=I, donc les combinateurs constructibles à partir de S, K et I, le sont à partir de S et K seuls. Par exemple, SII = (λa.λb.λc. a c (b c)) (λa. a) (λa. a ) se réduit, en 5 étapes, à λc. c c = M. Puis S(KS)K se réduit en B, etc.

Ceci est décrit dans cette partie du livre :

PDF -

J

Le combinateur J de Rosser est défini par J = λa.λb.λc.λd.a b (a d c) :

avec I, il permet de construire tout le λI-calcul ; pour le montrer, on va prouver que B, T et M sont constructibles avec I et J (comme B, T, M et I engendrent tout le λI-calcul cela suffit) :

  • étape 1 : On simplifie l’expression JII=(λa.λb.λc.λd.a b (a d c)) (λa. a ) (λa. a ) :

Cela prouve que JII=T ; reste alors à montrer comment construire B et M à partir de J, I et T.

  • étape 2 : B

Plus long :

  1. En réduisant JT = (λa.λb.λc.λd.a b (a d c)) (λa.λb.(b a)) on trouve R.
  2. En réduisant JI = (λa.λb.λc.λd.a b (a d c)) (λa. a ) on trouve Q1 = λb.λc.λd. b ( d c ).
  3. Comme RRR=C, on peut réduire Q1CQ1 ; on trouve B.
  • étape 3 : M
  1. On réduit BJT pour trouver J1 = λc.λf.λg.λd. f c ( d c g ).
  2. Le combinateur C(C(CJ1T)T)T se réduit alors en M.

B,T,I

Le système engendré par B, T et I a été étudié par Rosser ; il ne contient ni M, ni W, ni L, ni S et bien entendu pas J non plus. Il est également engendré par B, C et I. Ce sous-ensemble du λI-calcul peut lui aussi être engendré par seulement deux combinateurs : I et G. Pour le montrer, il suffit de construire B et T à partir de J et G.

  • 1re étape : Joe

En réduisant GI, on trouve Q3 = λe.λf.λg. g ( e f ) :

  • 2e étape : T

Ensuite en réduisant Q3I, on trouve T :

Il ne reste maintenant plus qu’à construire B à partir de G, I, T.

  • 3e étape : R et C

En réduisant GGII, on trouve C. Et comme on a vu que CC=R, on considère R comme construit aussi.

  • 4e étape : Encore une histoire de Q

En réduisant GRQ3, on trouve Q.

  • 5e étape : CQ

En réduisant CQ on trouve B :

Pour en savoir plus, voici la suite du livre de Smullyan :

PDF -

On a vu plusieurs fois ci-dessus un phénomène cyclique : CC=R :

Mais RRR=C :

Étonnant non ? Du coup on peut écrire R sous la forme RRR(RRR) et C sous la forme CC(CC(CC)) voire CC(CC(CC))CC(CC(CC))(CC(CC(CC))CC(CC(CC))(CC(CC(CC))CC(CC(CC)))) etc.

De même, alors que KK n’est pas égal à K mais à λb.λc.λd.c, on trouve, après réduction, que KKK=K, mais aussi KKKK=KK, KKKKK=K, etc.

Par contre les combinateurs suivants sont tous différents, et cela prouve qu’il y a une infinité de combinateurs :

  • K
  • KK =  λb.λc.λd.c
  • K(KK) =  λb.λe.λc.λd.c
  • K(K(KK)) = λb.λf.λe.λc.λd.c
  • etc (la fonction qui, à n variables, associe l’avant-dernière de ces variables).

Voici le portrait de cette famille infinie :

La conclusion du livre est ce qui a été cité au début de cet article : La concaténation peut se réaliser par des opératons arithmétiques, et le codage de Gödel peut s’appliquer aux expressions parenthésées qui représentent les combinateurs avec les lettres S, K et I. Smullyan redémontre, avec ces outils, le théorème d’incomplétude de Gödel.


[1le thème de la semaine des maths 2017 était « mathématiques et langages » ; la logique combinatoire peut être considérée comme l’étude de langages où les mots ont une structure arborescente de par l’usage des parenthèses...

[2en français « le livre qui rend fou », paru chez Dunod

[3Smullyan considérait qu’un vrai mensonge est intentionnel : Si on prétend que \sqrt{2}^{\sqrt{2}} est une fraction alors que ce n’en est pas une, on mérite plus d’être traité d’ignare que d’être traité de menteur. Pour Smullyan, le vrai menteur est celui qui dit une chose en en croyant une autre. En défendant un tel point de vue, il était inévitable qu’il s’intéresse à la logique doxastique, puisqu’on peut très bien croire en quelque chose de faux.

[4Euh non c’est pas LOL c’est seulement LO ; je sais c’est bas (low) ce genre de jeux de mots...

[5obtenu en copiant-collant S depuis cet article puis en cliquant deux fois de suite sur TRUE puisque c’est par K que Church représente le vrai


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 14 juin 2017, 14h-18h, PTU, Saint-Denis, salle S23.6
- Mercredi 21 juin 2017, 14h-18h, 146 route de Grand-Coude, Saint-Joseph


Brèves

Décès de Raymond Smullyan

mercredi 15 mars

Le logicien Raymon Smullyan est décédé en février 2017, à l’âge respectable de 97 ans : Il avait eu Alonzo Church comme professeur ! Pour en savoir plus, voir cet article

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

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

mardi 18 juillet 2017

Publication

759 Articles
Aucun album photo
133 Brèves
11 Sites Web
132 Auteurs

Visites

212 aujourd'hui
342 hier
2062272 depuis le début
10 visiteurs actuellement connectés