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 |
|
|
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 :
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 :
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 :
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 :
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 :
- En réduisant
JT = (λa.λb.λc.λd.a b (a d c)) (λa.λb.(b a))on trouve R. - En réduisant
JI = (λa.λb.λc.λd.a b (a d c)) (λa. a )on trouveQ1 = λb.λc.λd. b ( d c ). - Comme RRR=C, on peut réduire Q1CQ1 ; on trouve B.
- étape 3 : M
- On réduit BJT pour trouver
J1 = λc.λf.λg.λd. f c ( d c g ). - 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 :
∞
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 :
Dessin de combinateurs
Le flow programming permet de dessiner des combinateurs :
| les dessins en pdf | le source en LaTeX |
|
|
|
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.
Commentaires