NOMBRES - Curiosités, théorie et usages

Accueil / Dictionnaire / Rubriques / Index / Références / Nouveautés

ORIENTATION GÉNÉRALE  - M'écrire - Édition du: 24/09/2005

 

 -Ý- RUBRIQUE: INTELLIGENCE ARTIFICIELLE

§         Introduction

§         Jeux

§         Théorie

§         Algorithmes

§         Systèmes experts

§         Réseaux neuronaux

§         Machine de Turing

§         Automate

§         Lambda-calcul

§         Programmation

§          

§          

Sommaire de cette page

>>> APPROCHE DU PEINTRE

>>> TOUR D'HORIZON

>>> RUDIMENTS DE LANGAGE

>>> CALCUL

>>> QUELQUES FORMULATIONS

>>> PROPRIÉTÉS

Pages sur sujets voisins

§         Dualité

§         Logique

§         Outils de la logique

§         Incomplétude

§         Raisonnement

§         Énigmes et paradoxes


  

LAMBDA - CALCUL

Base de tous les raisonnements:

§        Mathématiques

§        Informatiques

§         Linguistiques

 Anglais :  Lambda-calculus

Avertissement

N'étant pas un spécialiste de ce domaine,

ce qui suit permet de toucher du doigt ce sujet

Sans prétention !

 

-Ý- APPROCHE DU PEINTRE

§        Imaginons une méthode pour donner des consignes précises aux peintres

§        Un peu compliquée, mais efficace

Appliquer la consigne "PEINDRE EN COULEUR" en utilisant le ROUGE

Voici l'illustration

 

Traduction en lambda-langage

Écriture en lambda-calcul

(l x . peindre en x ) rouge

qui veut dire ®

peindre en rouge

 

Mise en cascade

Un seul niveau

 

 

(l couleur

 

peindre en couleur l'objet

 

) rouge

 

 

Application

 

 

(l couleur

 

peindre en couleur l'objet

 

) rouge

 

 

Réduction

 

 

 

 

peindre en rouge l'objet

 

 

 

 

Deux niveaux

((l objet .

 

l couleur

 

peindre en couleur l'objet

 

) rouge

 

) mur

Application 1

((l objet .

 

l couleur

 

peindre en couleur l'objet

 

) rouge

 

) mur

Réduction1

 

 

( l couleur

 

peindre en couleur le mur

 

) rouge

 

 

Application 2

 

 

( l couleur

 

peindre en couleur le mur

 

) rouge

 

 

Réduction 2

 

 

 

 

peindre en rouge le mur

 

 

 

 

 

§        Avec ces seules instructions:

o       applications et réductions

o       sur des variables

§        Il est possible de reformuler tous les fonctions mathématiques

§        et même, le raisonnement dans tous les domaines

o       linguistique

o       mathématique

o       informatique

 

§        De même qu'en informatique,

o       écrire des programmes en binaire est fastidieux

§        En lambda-calcul aussi, on a imaginé

o       des langages de plus haut niveau, plus faciles à manipuler

 

-Ý- TOUR D'HORIZON

§        Le lambda-calcul est une sorte de langage à syntaxe élémentaire qui permet d'exprimer toutes les fonctions calculables

§        Le lambda-calcul est considéré comme la base mathématique de tous les langages de programmation

§        Formalisation développée par Alonzo Church et Stephen Kleene en 1932

§        Étudié comme langage universel par Jean-Louis Krivine

§        Le langage correspond à l'application d'une fonction à ses arguments

§        Toute entité est formalisée par

o       soit une variable

o       soit l'application d'une fonction à une autre

o       soit comme l'abstraction  (réduction) d'une fonction

 

Principe du langage avec un exemple

§        Une variable x

égale à 7

§        Un fonction de x dite lx

égale à 3x + 5

§        Lambda expression

lx . 3x + 5

§        Une application (abstraction)

(lx . 3x + 5) 7

§        Sa réduction (calcul)

( 3x + 5) [7/x]

= 3 x 7 + 5

= 26

Note: on a utilisé 3x + 5 alors que

"addition et multiplication" ne sont pas encore définies;

C'est un exemple

 

§        Le lambda-calcul est la base, surtout, des langages fonctionnels comme

o       LISP

o       Haskell (logo d' -)

o       Miranda

o       ML , OCaml

§        Il est aussi utilisé comme métalangage

o       pour obtenir des définitions formelles

§        Langage fonctionnel: programmation en écrivant des fonctions qui appellent d'autres fonctions, qui appellent des fonctions... (Lisp pur, Miranda,  Haskell …)

§         Langage impératif : langage de programmation décrivant le parcours d'un algorithme précis (Pascal, C++ …)

§         Langage impératif fonctionnel: Lisp, ML

Voir exemples en Programmation

 

-Ý- RUDIMENTS DE LANGAGE

Un niveau

§         Variable objet

mur

x = a

§         Fonction

peindre en bleu

f

§         Lambda-fonction

l objet . peindre en bleu l'objet

lx . f

§         Lambda-abstraction

(l objet . peindre en bleu l'objet) mur

(lx . f) a

§         Réduction

peindre en bleu le mur

f [a/objet]

 

Deux niveaux en cascade

Données

 

 

§         Variable objet

§         Variable couleur

mur

rouge

x = a

y = b

§         Fonction

peindre en couleur l'objet

f

Lambda de premier niveau

§         Lambda-fonction

l couleur . l objet . peindre en couleur l'objet

ly . lx . f

§         Lambda-abstraction

(l couleur . l objet . peindre en couleur l'objet) rouge

(ly . lx . f) b

§         Réduction

peindre en rouge l'objet

lx . f [b/couleur]

Lambda avec les deux niveaux

§         Application complète

((l couleur . l objet . peindre en couleur l'objet) rouge) mur

((ly . lx . f) b) a

§         Réduction d'un niveau

(l objet . peindre en rouge l'objet) mur

(lx . f [b/couleur])  a

§         Nouvelle application

peindre en rouge le mur

f [b/couleur, a/objet]

 

-Ý- CALCUL

Alpha réduction

lx. E ® lz {z/x} E

P = …x … x …

P = …z … z …

§        Dans la fonction E, tous les x peuvent être remplacé par z

lx . peindre objet ® peindre le mur

 

Bêta réduction

(lx. P) Q ® [Q/x] P

P = …x … x …

P = …Q … Q …

§        Dans la fonction P, tous les x peuvent être remplacé par Q

 

(lx . x) toto ® toto

Exemple en cascade

 

( (lx . ly . x) singe ) cacahuète ® ?

 

§         Expression entre parenthèses rouges:

( (lx . ly . x) singe ) cacahuète ® (ly . cacahuète) singe

§        En effet, il faut remplacer dans la fonction x tout ce qui est x par cacahuète

§        Nous avons obtenu:

(ly . cacahuète) singe

§         Dans la fonction cacahuète nous devons remplacer tout y par singe

§        Or, il n'y a pas singe dans cacahuète

§        La fonction ne peut pas de réduire en une expression en "singe"

§        Elle reste dans son état général de cacahuète

(ly . cacahuète) singe ® cacahuète

 

 

-Ý- QUELQUES FORMULATIONS

Fonctions duales

VRAI

FAUX

§         Reprenons l'exemple précédent

( (lx . ly . x) b ) a

® (ly . a) b

®  a

§         Idem avec une nuance

( (lx . ly . y) b ) a

® (ly . y) b

®  b

§         Cette application sur a donne toujours a

§         C'est la fonction "vrai"

§         Cette application sur a donne toujours b

§         C'est la fonction "faux"

 

Vrai = (lx . ly . x)

Faux = (lx . ly . y)

 

Définition des nombres

0, 1, 2, …

§         La formulation fait allusion à la répétition de l'application

0 = lf . lx . x

1 = lf . lx . (f) x

2 = lf . lx . (f) (f) x

3 = lf . lx . (f) (f) (f) x

 

 

 

-Ý- PROPRIÉTÉS

Thèse de Church

§        Toute fonction calculable peut l'être avec un ensemble réduit d'instructions

§        Affirmation philosophique indémontrable, base de toute l'algorithmique

 

Théorème de Church-Rosser

§        Le résultat final de substitutions lors des réductions ne dépend pas de l'ordre dans lequel ces substitutions sont effectuées

 

Modèle de calcul universel

§        Tout calcul exprimable en machine de Turing est aussi exprimable en lambda-calcul

 

 

 


-Ý-

Voir

§         Systèmes experts

§         Réseaux neuronaux

§         Multimédia

§         Événements chronologiques

 

Sites

§         Lambda calcul par Bruno Courcelle

§         Lambda-calcul et langages fonctionnels par Jean Goubault-Larrecq

§         An Introduction to Lambda Calculus and Scheme

 

Livre

§         Science & Vie de février 2002:

"L'intelligence dévoile enfin sa vraie nature -

Toute pensée est un calcul"