tion qui à x et y assoc ie e. Par exe mpl e,
Àxv_.ryx se compre nd co mme une fonction qui envoie x et y sur le résultat de
la compos ition x o yox. La fo ncti on K =
Àxy_r se comprend comme ce ll e associant à un couple (x, y) son premier é léme nt (projec ti o n s ur la pre mi è re
com posante).
En À-calcul , un e fo ncti o n défi ni e par
Àx.e es t com posée par y e n éc ri va nt
(Àx.e)y. Cette fo nction est a lors« équi -
va lente » à la fo ncti on obtenue e n rempl aça nt chaque occ urre nce libre de x
da nse par y. On dé finit a in si une règle
de tra nsform ation des ex press ions du Àca lcul do nnant par exe mpl e
(Àx.xx)y -+ yy, (Àxy_r) z --+ Ày.z,
(Àxy.yx)ab --+ ba
ou encore la success ion
(Àx .xx)(Ày.y) --+ (Ày.y)(Ày.y) --+ Ày.y.
Ces ca lcul s, a priori s impl ifi cate urs,
pe uvent néa nm o in s bo uc le r à l' infini
da ns certa ines situations. C'est le cas si
l'on considère fl = M avec
ô = Àx.xx, où l'on obtient :
fl = (Àx.xx)ô -+ M = fl -+ fl-+ ...
Parfo is mê me, il n 'y a simplifi cati on
qu'en fo nction de l'organisation du calcul:
Klfl = (Àx ~r) lfl --+ 1 alors que
Klfl= Kl (Àx.xx)ô -+ Klfl-+ KJfl-+ ...
En À-ca lcul , les lettres ne désignent que
des fo ncti o ns et null eme nt des o bjets
mathé matiques: les ex press ions écrites
en À-calcul ne compo11ent que les lettres
du vocabul a ire servant à no mme r les
fo ncti ons, le sy mbo le À et les sy mbo les
utiles au parenthèsage . Alonzo Church
parvient cependant à reconstruire dans
ce langage les objets du mo nde mathématique , à co mmencer par les e nti ers
nat ure ls ou les va le urs boo léennes. Il
parvient aussi à défi ni r les constructeurs
de la programmati on in fo rmatique que
sont les in structio ns conditi onnées, les
itérateurs et les appe ls réc ursifs. À ce
POUR L'INFORMATIQUE
Alonzo Church.
titre, le À-ca lcul pe ut être co ns id é ré
comme l' un des pre miers langages permettant de coder les algorithmes . Ain si,
Alonzo C hurch accède aux fo ncti ons Àca lcul ables, c'est-à-dire à celles pouva nt être obtenues par À-calcul.
Une machine à calculer uniuerselle
Parallè lement , le mathématic ien et logic ien britannique Al an Turing compl ète
lui auss i les tra vaux de Gi:ide l afin de
déterminer ce qui est « mécaniquement
ca lcul a bl e». Il définit po ur ce la un e
« machine à calculer uni verselle». Cellec i es t parti c uli è re me nt rudime nta ire,
mais ses capac ités théoriques éga le nt ,
et même surpassent , ce lles de n' importe
que l superca lcul ate ur moderne !
Une machine de Turing est constituée d'un
ruban de lo ngueur infini e (équi valent
d ' une mémo ire) sur leque l évo lue une
tête de lecture et d 'écriture . Une machine
de Turing est auss i constituée d ' un processeur pouvant prendre un nombre fini
d 'états et commandant le comportement
de la tête de lecture. La programmation
d ' une mac hine de Turing se fa it préa labl e me nt à so n fo nc ti o nn e me nt. Ell e
Hors-série n• 52. Mathématiques & informatique Tangente
Àxv_.ryx se compre nd co mme une fonction qui envoie x et y sur le résultat de
la compos ition x o yox. La fo ncti on K =
Àxy_r se comprend comme ce ll e associant à un couple (x, y) son premier é léme nt (projec ti o n s ur la pre mi è re
com posante).
En À-calcul , un e fo ncti o n défi ni e par
Àx.e es t com posée par y e n éc ri va nt
(Àx.e)y. Cette fo nction est a lors« équi -
va lente » à la fo ncti on obtenue e n rempl aça nt chaque occ urre nce libre de x
da nse par y. On dé finit a in si une règle
de tra nsform ation des ex press ions du Àca lcul do nnant par exe mpl e
(Àx.xx)y -+ yy, (Àxy_r) z --+ Ày.z,
(Àxy.yx)ab --+ ba
ou encore la success ion
(Àx .xx)(Ày.y) --+ (Ày.y)(Ày.y) --+ Ày.y.
Ces ca lcul s, a priori s impl ifi cate urs,
pe uvent néa nm o in s bo uc le r à l' infini
da ns certa ines situations. C'est le cas si
l'on considère fl = M avec
ô = Àx.xx, où l'on obtient :
fl = (Àx.xx)ô -+ M = fl -+ fl-+ ...
Parfo is mê me, il n 'y a simplifi cati on
qu'en fo nction de l'organisation du calcul:
Klfl = (Àx ~r) lfl --+ 1 alors que
Klfl= Kl (Àx.xx)ô -+ Klfl-+ KJfl-+ ...
En À-ca lcul , les lettres ne désignent que
des fo ncti o ns et null eme nt des o bjets
mathé matiques: les ex press ions écrites
en À-calcul ne compo11ent que les lettres
du vocabul a ire servant à no mme r les
fo ncti ons, le sy mbo le À et les sy mbo les
utiles au parenthèsage . Alonzo Church
parvient cependant à reconstruire dans
ce langage les objets du mo nde mathématique , à co mmencer par les e nti ers
nat ure ls ou les va le urs boo léennes. Il
parvient aussi à défi ni r les constructeurs
de la programmati on in fo rmatique que
sont les in structio ns conditi onnées, les
itérateurs et les appe ls réc ursifs. À ce
POUR L'INFORMATIQUE
Alonzo Church.
titre, le À-ca lcul pe ut être co ns id é ré
comme l' un des pre miers langages permettant de coder les algorithmes . Ain si,
Alonzo C hurch accède aux fo ncti ons Àca lcul ables, c'est-à-dire à celles pouva nt être obtenues par À-calcul.
Une machine à calculer uniuerselle
Parallè lement , le mathématic ien et logic ien britannique Al an Turing compl ète
lui auss i les tra vaux de Gi:ide l afin de
déterminer ce qui est « mécaniquement
ca lcul a bl e». Il définit po ur ce la un e
« machine à calculer uni verselle». Cellec i es t parti c uli è re me nt rudime nta ire,
mais ses capac ités théoriques éga le nt ,
et même surpassent , ce lles de n' importe
que l superca lcul ate ur moderne !
Une machine de Turing est constituée d'un
ruban de lo ngueur infini e (équi valent
d ' une mémo ire) sur leque l évo lue une
tête de lecture et d 'écriture . Une machine
de Turing est auss i constituée d ' un processeur pouvant prendre un nombre fini
d 'états et commandant le comportement
de la tête de lecture. La programmation
d ' une mac hine de Turing se fa it préa labl e me nt à so n fo nc ti o nn e me nt. Ell e
Hors-série n• 52. Mathématiques & informatique Tangente