HISTOIRES
Alonzo Church, Alan Turing ...
Alan Turing.
consiste à définir, en fon ction de l'état
du processeur et de la va leur lue sur le
ruban, des actions d 'écriture sur le ruban,
de dé place ment de la tête de lecture, de
changement d 'état du processeur.
À pai1ir d ' une information initi ale ment
écrite sur un nombre fini de cases du
ruban, la machine de Turing opère selon
le programme prédéterminé et, si celui -
ci conduit le processeur à un état qualifié de final , on dit que la machine de
Turing s'est arrêtée. L' utili sate ur I it
alors le contenu du ruban, qui se comprend comme étant la ré pon se calcu lée
par la mac hin e de Turing à partir du
ruban d 'entrée. Au fin al, une machine de
Turing se comprend comme une fo nction mécanique tra nsform ant l'état du
ruban en un autre . Al an Turing a ain si
défini ce que pou vait être un ordinateur
aya nt é té prog ramm é. Il parti c ipe ra
d 'a ille urs acti vement à la créati on d ' un
des premiers ordinate urs en 1949.
Bie n que ce modè le parai sse é lé me ntaire (et c'est ce qui en fa c ilite l'étude),
il suffit pour mettre en place des démarches
algorithmiques complexes. Alan Turing
pe ut ainsi étudier ce que sont les fo nctions T-calcu lables, c'est-à-dire les fo nctio ns dont les va le urs sont fourni es par
l'exécution d ' une mac hine de Turing.
La« À.-ca lcul alibilité » et la« T-ca lculalibilité » sont de ux approches a priori
di fférentes, car! ' une est plutôt log icielle
alors que ! 'autre est plus matérielle. Elles
visent cependant toutes deux à défi nir le
plus généra lement poss ible ce que pouvait être une fo nction ca lculable. En
1936, Al onzo C hurch démontre que ces
de ux notion s déterminent exacte ment
les mê mes fo ncti o ns ca lc ul abl es ' li
affirme même qu ' il n 'est sans doute pas
poss ible de proposer un ensemble plus
large de fo ncti ons ca lc ul a bl es. Cette
affirmati on (un peu vague) est appe lée
la thèse de Church . Ce n'est pas un théorème, car la notion de fo nction calculable
n'est qu ' intuitive. C'est plutôt un constat :
o n ne parvient pas à dé finir une cl asse
plus large de fo nctions dont les va le urs
pourraient être ca lcul ées par un procédé
de nature algorithmique.
Après ses théo rè mes de co mpl étu de,
Kurt Gode! a énoncé des théorèmes d ' incompl études. Sché matiqu eme nt , l' un
d 'eux a ffirm e que, dans toute théori e
capable de définir l'arithm étique des
entiers, il ex iste un énoncé qui ne pe ut
(ni lui , ni sa négati on) être dé montré .
Cela entraîne qu 'on ne pe ut définir d 'algorithme prenant la déc ision de savo ir
si un énoncé arithmétique est, ou non ,
vérifié: on dit qu ' il s'ag it d ' un problème indécidable. Parai lèlement, Alonzo
C hurch dé montre qu ' il est indéc idable
de savoir si de ux phrases du À-ca lcul
sont équiva lentes. Al an Turing établit
quant à lui qu ' il n 'est pas non plu s déc id able de savo ir si le fo ncti onn ement
d ' une machine de Turing donnée va ou
no n s'arrêter.
Ces études ont fo rte ment partic ipé aux
pro g rès des ma th é matiqu es d a ns le
do ma ine de la log ique et ont développé
les outil s contribuant à la fo rmali sation
de l' info rmatique modern e .
D. D.
42 Tangente Hors-série n°52. Mathématiques & informatique
Alonzo Church, Alan Turing ...
Alan Turing.
consiste à définir, en fon ction de l'état
du processeur et de la va leur lue sur le
ruban, des actions d 'écriture sur le ruban,
de dé place ment de la tête de lecture, de
changement d 'état du processeur.
À pai1ir d ' une information initi ale ment
écrite sur un nombre fini de cases du
ruban, la machine de Turing opère selon
le programme prédéterminé et, si celui -
ci conduit le processeur à un état qualifié de final , on dit que la machine de
Turing s'est arrêtée. L' utili sate ur I it
alors le contenu du ruban, qui se comprend comme étant la ré pon se calcu lée
par la mac hin e de Turing à partir du
ruban d 'entrée. Au fin al, une machine de
Turing se comprend comme une fo nction mécanique tra nsform ant l'état du
ruban en un autre . Al an Turing a ain si
défini ce que pou vait être un ordinateur
aya nt é té prog ramm é. Il parti c ipe ra
d 'a ille urs acti vement à la créati on d ' un
des premiers ordinate urs en 1949.
Bie n que ce modè le parai sse é lé me ntaire (et c'est ce qui en fa c ilite l'étude),
il suffit pour mettre en place des démarches
algorithmiques complexes. Alan Turing
pe ut ainsi étudier ce que sont les fo nctions T-calcu lables, c'est-à-dire les fo nctio ns dont les va le urs sont fourni es par
l'exécution d ' une mac hine de Turing.
La« À.-ca lcul alibilité » et la« T-ca lculalibilité » sont de ux approches a priori
di fférentes, car! ' une est plutôt log icielle
alors que ! 'autre est plus matérielle. Elles
visent cependant toutes deux à défi nir le
plus généra lement poss ible ce que pouvait être une fo nction ca lculable. En
1936, Al onzo C hurch démontre que ces
de ux notion s déterminent exacte ment
les mê mes fo ncti o ns ca lc ul abl es ' li
affirme même qu ' il n 'est sans doute pas
poss ible de proposer un ensemble plus
large de fo ncti ons ca lc ul a bl es. Cette
affirmati on (un peu vague) est appe lée
la thèse de Church . Ce n'est pas un théorème, car la notion de fo nction calculable
n'est qu ' intuitive. C'est plutôt un constat :
o n ne parvient pas à dé finir une cl asse
plus large de fo nctions dont les va le urs
pourraient être ca lcul ées par un procédé
de nature algorithmique.
Après ses théo rè mes de co mpl étu de,
Kurt Gode! a énoncé des théorèmes d ' incompl études. Sché matiqu eme nt , l' un
d 'eux a ffirm e que, dans toute théori e
capable de définir l'arithm étique des
entiers, il ex iste un énoncé qui ne pe ut
(ni lui , ni sa négati on) être dé montré .
Cela entraîne qu 'on ne pe ut définir d 'algorithme prenant la déc ision de savo ir
si un énoncé arithmétique est, ou non ,
vérifié: on dit qu ' il s'ag it d ' un problème indécidable. Parai lèlement, Alonzo
C hurch dé montre qu ' il est indéc idable
de savoir si de ux phrases du À-ca lcul
sont équiva lentes. Al an Turing établit
quant à lui qu ' il n 'est pas non plu s déc id able de savo ir si le fo ncti onn ement
d ' une machine de Turing donnée va ou
no n s'arrêter.
Ces études ont fo rte ment partic ipé aux
pro g rès des ma th é matiqu es d a ns le
do ma ine de la log ique et ont développé
les outil s contribuant à la fo rmali sation
de l' info rmatique modern e .
D. D.
42 Tangente Hors-série n°52. Mathématiques & informatique