Livre_silo 30 août 2013 16:32 Page 6
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
6
Informatique pour tous
Les mathématiciens ont également réalisé que de nombreux calculs pourraient être automatisés. Dès 1642, Blaise Pascal avait ainsi conçu et réalisé une machine (la Pascaline) qui
effectuait les quatre opérations usuelles sur les entiers : addition, soustraction, multiplication et division. Plus tard, vers le milieu du siècle, suite aux travaux de Babbage,
plusieurs machines à différences, des machines mécaniques, ont été produites pour calculer
et imprimer des tables de logarithmes.
Finalement, au siècle, on s’est demandé si l’on pouvait tout calculer. Peut-on calculer
toutes les fonctions des entiers dans les entiers ? Peut-on trouver une machine qui imprime
sur un ruban les chiffres successifs de n’importe quel réel ?
David Hilbert demande même en 1928 s’il existe une machine capable de décider si une
proposition mathématique est vraie ou fausse. Alonzo Church et Alan Turing répondent
indépendamment non à cette question, en 1936 et 1937 respectivement.
L’article de Turing propose un modèle de machine (appelée aujourd’hui machine de Turing)
qui possède les caractéristiques suivantes :
1 Une machine de Turing possède un ruban infini sur lequel on a disposé des données.
Elle peut lire des données sur ce ruban, les traiter et en écrire d’autres. Au bout d’un
certain temps, il se peut qu’ elle s’arrête, on peut alors lire le résultat du calcul sur le ruban
(mais il se peut aussi que la machine continue à travailler indéfiniment).
2 Pour tout procédé qui peut être calculé par un algorithme, il semble qu’il y ait une machine de Turing capable de le calculer (il est difficile de montrer que c’est effectivement le
cas si on ne sait pas définir précisément ce qu’est un algorithme ; cette dernière question
est justement une de celles auxquelles Turing tente de répondre).
3 Turing démontre qu’ on peut construire une machine universelle, c’est-à-dire une machine capable de simuler toutes les autres. Pour l’utiliser, on dispose simplement sur son
ruban une description de la machine qu’on veut simuler ainsi que les données d’entrée
de la machine à simuler.
4 Il démontre également qu’il existe cependant des problèmes que cette machine n’est pas
capable de résoudre : par exemple, décider si une proposition mathématique est vraie
ou même, beaucoup plus simplement, à partir de la description d’une machine et de ses
données d’entrée, décider à coup sûr si cette machine va s’arrêter ou non.
Cet article est extrêmement novateur car il considère que la description d’une machine
(ou d’un algorithme) peut en fait être considérée comme une donnée : la donnée d’entrée
d’une machine de Turing universelle.
Aujourd’hui, on considère ce point comme une caractérisation essentielle de ce qu’est un
ordinateur : un ordinateur est la réalisation concrète d’une machine de Turing universelle, c’està-dire une machine traitant des informations et capable en principe de prendre comme donnée
d’entrée n’importe quel algorithme et de l’exécuter.
¨
©
¨
©
¨
©
¨
©
C o p y r i g h t E y r o l l e s
6
Informatique pour tous
Les mathématiciens ont également réalisé que de nombreux calculs pourraient être automatisés. Dès 1642, Blaise Pascal avait ainsi conçu et réalisé une machine (la Pascaline) qui
effectuait les quatre opérations usuelles sur les entiers : addition, soustraction, multiplication et division. Plus tard, vers le milieu du siècle, suite aux travaux de Babbage,
plusieurs machines à différences, des machines mécaniques, ont été produites pour calculer
et imprimer des tables de logarithmes.
Finalement, au siècle, on s’est demandé si l’on pouvait tout calculer. Peut-on calculer
toutes les fonctions des entiers dans les entiers ? Peut-on trouver une machine qui imprime
sur un ruban les chiffres successifs de n’importe quel réel ?
David Hilbert demande même en 1928 s’il existe une machine capable de décider si une
proposition mathématique est vraie ou fausse. Alonzo Church et Alan Turing répondent
indépendamment non à cette question, en 1936 et 1937 respectivement.
L’article de Turing propose un modèle de machine (appelée aujourd’hui machine de Turing)
qui possède les caractéristiques suivantes :
1 Une machine de Turing possède un ruban infini sur lequel on a disposé des données.
Elle peut lire des données sur ce ruban, les traiter et en écrire d’autres. Au bout d’un
certain temps, il se peut qu’ elle s’arrête, on peut alors lire le résultat du calcul sur le ruban
(mais il se peut aussi que la machine continue à travailler indéfiniment).
2 Pour tout procédé qui peut être calculé par un algorithme, il semble qu’il y ait une machine de Turing capable de le calculer (il est difficile de montrer que c’est effectivement le
cas si on ne sait pas définir précisément ce qu’est un algorithme ; cette dernière question
est justement une de celles auxquelles Turing tente de répondre).
3 Turing démontre qu’ on peut construire une machine universelle, c’est-à-dire une machine capable de simuler toutes les autres. Pour l’utiliser, on dispose simplement sur son
ruban une description de la machine qu’on veut simuler ainsi que les données d’entrée
de la machine à simuler.
4 Il démontre également qu’il existe cependant des problèmes que cette machine n’est pas
capable de résoudre : par exemple, décider si une proposition mathématique est vraie
ou même, beaucoup plus simplement, à partir de la description d’une machine et de ses
données d’entrée, décider à coup sûr si cette machine va s’arrêter ou non.
Cet article est extrêmement novateur car il considère que la description d’une machine
(ou d’un algorithme) peut en fait être considérée comme une donnée : la donnée d’entrée
d’une machine de Turing universelle.
Aujourd’hui, on considère ce point comme une caractérisation essentielle de ce qu’est un
ordinateur : un ordinateur est la réalisation concrète d’une machine de Turing universelle, c’està-dire une machine traitant des informations et capable en principe de prendre comme donnée
d’entrée n’importe quel algorithme et de l’exécuter.