Le calcul, une notion difficile à attraper
On sait que le mot « calcul » vient du latin calculus, et rappelle l’utilisation de cailloux dans les procédures de comptage depuis au moins le IVe millénaire avant J.-C. Des cailloux jetés dans un bol à l’entrée de la bergerie pour vérifier qu’il y avait autant de moutons qui rentraient le soir que d’animaux qui en étaient sortis le matin, aux bits dans la mémoire d’un ordinateur qui comptabilisent notre compte en banque, le chemin est long et il peut faire oublier que le calcul ne se résume pas aux opérations arithmétiques.
Jusqu’au siècle dernier, les machines à calculer étaient principalement dédiées au calcul numérique : il s’agissait de simplifier le calcul de formules compliquées pour prévoir la position des étoiles ou de rendre routiniers les longs calculs nécessaires à la tenue des comptes. Cependant, l’homme a très tôt imaginé des machines dont le rôle est d’appliquer une procédure bien définie, on dit aujourd’hui un algorithme, à autre chose que des nombres, pour produire la réponse à un problème.
Un exemple ancien est donné par les roues pivotantes de Raymond Lulle, au treizième siècle. Précurseur de la logique combinatoire, il inventa sous le nom d’Ars universalis une espèce de machine dialectique où les idées de genre étaient classées et distribuées, ce qui permettait d’énumérer automatiquement toutes sortes de raisonnements par le jeu des combinaisons de toutes les propositions possibles.
Reproduction de l’une des machines de Lulle dans la traduction en français de Ars Brevis (1901, disponible sur Gallica). Le disque central et les deux anneaux sont mobiles.
Plus tard Leibniz, au dix-septième siècle, imaginait la construction d’une machine qui pouvait manipuler des symboles afin de déterminer les valeurs des énoncés mathématiques.
Faisons un saut temporel : en 1801, le lyonnais Joseph Marie Jacquard met au point un nouveau métier à tisser où le motif à réaliser est codé sur des cartes perforées qui commandent directement la mécanique servant à lever les trames. Suivant qu’une trame est levée ou non, le fil attaché à la navette passe au-dessus ou au-dessous du point correspondant qui devient visible ou non dans l’image tissée au final. L’image qui apparaît dans le tissage est donc codée dans les cartes perforées. Du codage au calcul, le pas est vite franchi.
Vingt ans plus tard, Charles Babbage présente une machine à différence à la Société Royale britannique. Il veut automatiser le calcul des tables de logarithmes et des autres fonctions qui, à l’époque, sont élaborées manuellement et entachées d’erreurs. Une brillante mathématicienne, Ada Lovelace, fille de Lord Byron, l’aide à concevoir les schémas de calcul pour faire fonctionner la machine. La machine est en constante évolution et entre 1834 et 1836, Babbage développe un nouveau modèle, la machine analytique, qui comporte un dispositif d’entrée et de sortie, une mémoire intermédiaire, un dispositif pour transférer des nombres entre les différentes unités de la machine, etc. Ada Lovelace comprend la puissance de cette machine.
« La caractéristique distinctive de la Machine Analytique, celle qui a permis de doter ce mécanisme de telles capacités qu’il est raisonnable de dire que cela en fait le premier assistant de l’algèbre abstraite, est l’utilisation du procédé que Jacquard conçut pour contrôler, au moyen de cartes perforées, les motifs les plus compliqués dans la fabrication des broderies. C’est en cela que réside la différence entre les deux machines. Rien de tel n’existe dans la Machine à Différence. Nous pouvons affirmer à juste raison que la Machine Analytique tisse des motifs algébriques tout comme le métier à tisser de Jacquard tisse des fleurs et des feuilles. », écrit-elle.
Et elle ajoute :
« De nombreuses personnes qui connaissent mal les études mathématiques pensent que parce que le travail de la machine est de donner des résultats en notation numérique, la nature du processus doit forcément être arithmétique et numérique, plutôt qu’algébrique et analytique. C’est une erreur… La machine peut produire trois types de résultats : (…) symboliques (…) ; numériques (…) ; et algébriques en notation littérale. »
Cette rapide évocation de quelques étapes historiques marquantes laisse cependant intacte notre question initiale : qu’est-ce qu’un calcul ?
C’est au début du vingtième siècle que la question devient urgente. Lors du deuxième congrès international de mathématiques tenu à Paris en 1900, David Hilbert présenta une liste de problèmes qui tenaient jusqu’alors les mathématiciens en échec. Deux d’entre eux ont un lien étroit avec notre question.
Le dixième problème consiste à trouver un procédé déterminant automatiquement si une équation diophantienne a des solutions. Il s’agit d’une équation dont les coefficients sont des nombres entiers et dont les solutions recherchées sont également entières. Résoudre ce problème implique tout d’abord de définir rigoureusement une notion acceptable de procédé automatique.
Le deuxième problème vise à démontrer la consistance des axiomes de l’arithmétique. Toute la question, qui n’est pas éludée par Hilbert, est là aussi de savoir ce qu’on accepte comme une démonstration d’un théorème de l’arithmétique et quels moyens on se donne pour une telle preuve. En 1928, David Hilbert et Wilhelm Ackermann formulent le problème de la décision (Entscheidungsproblem) : peut-on déterminer de façon mécanique, par un algorithme, si un énoncé est un théorème de la logique ? Cet énoncé semble n’intéresser que les logiciens. Or c’est en fait un résultat de portée très générale. Par exemple, savoir si, étant donné les distances entre les villes d’une carte et une distance d, il existe un chemin passant par toutes les villes et de longueur inférieure à d, peut se formuler comme un problème de décision.
Les quatre chasseurs
Chasse au sanglier de Calydon – Musée du Louvre. Photo Bibi Saint-Pol, Wikimedia Commons
Dans le Sophiste, Platon rapproche la recherche de la connaissance de la chasse. Suivons sa métaphore : dans les années 1930, pour répondre à la question qui nous préoccupe, quatre chasseurs au moins sont sur la piste. Ils se nomment Stephen Kleene, Alonzo Church, Alan Turing et Emil Post. Chacun veut définir une certaine notion de calcul. La chasse va se révéler plus longue que prévue, mais les questions posées commencent à recevoir une réponse et c’est la naissance de la théorie de la calculabilité. Cette théorie vise à définir précisément ce qui est effectivement calculable.
Stephen Kleene
Stephen Cole Kleene passe sa thèse en 1934. Il veut expliciter la notion de « définition récursive de fonctions sur les entiers par un processus mécanique ». Les fonctions récursives dites « primitives » ont été utilisées par Kurt Gödel dans sa réponse au deuxième problème de Hilbert. Mais on sait, par un exemple d’Ackerman, qu’il y en a d’autres. Comment les définir ?
Le mot « mécanique » est ici important : le calcul de la valeur d’une telle fonction appliquée à un entier donné doit pouvoir se faire automatiquement, « sans réfléchir », en suivant une recette prédéterminée. Il est par exemple possible de décrire l’opération d’addition de deux entiers par une telle recette. Il en existe même plusieurs, et elles se sont matérialisées dans des machines à calculer comme la Pascaline développée par Blaise Pascal au début des années 1640. Les quatre opérations arithmétiques usuelles sont des fonctions récursives, c’est-à-dire qu’elles font appel à elles-mêmes. Pour aider à comprendre la notion de fonction récursive, il est plus simple d’illustrer le concept de récursion à partir de l’exemple classique de la fonction factoriel sur les entiers positifs.
Étant donné un entier naturel n, factoriel(n) calcule le produit de tous les entiers de 1 à n. On peut donc définir factoriel de la manière suivante :
factoriel(0) = 1 factoriel(n) = n × factoriel(n - 1) pour n > 0
La définition de factoriel est une recette : elle dit que pour calculer la valeur de factoriel sur un entier n différent de 0, il suffit de multiplier la valeur de n par la valeur que prend factoriel sur l’entier n – 1. Cette recette, on dira dorénavant un algorithme, utilise donc un autre algorithme, celui de la multiplication. Et il fait aussi appel à lui-même (c’est ce qu’indique le qualificatif de « récursif »).
Notons que les définitions récursives ne sont pas restreintes aux fonctions sur les entiers. Par exemple, on peut définir un oignon soit comme un trognon soit comme une pelure qui entoure un oignon. Derrière cet exemple amusant, on voit que la récursion est outil très puissant et général.
Mais définir un objet en faisant appel à l’objet qu’on est en train de définir est un procédé dangereux : est-on sûr que la définition produite est cohérente ? On connaît par exemple les problèmes posés par les menteurs qui parlent d’eux-mêmes, ou par les barbiers qui rasent uniquement tous les hommes qui ne se rasent pas, et dont on on a du mal à savoir finalement s’ils existent ou pas.
Épiménide le Crétois a dit : « Les Crétois mentent toujours ». Épiménide est crétois, donc il ment, mais dans le même temps, il vient de dire la vérité. D’un autre côté, si Épiménide affirme une vérité (à savoir que les Crétois mentent toujours), dans le même temps, il vient de la contredire. L’énoncé est contradictoire : c’est l’antinomie du menteur.
Un barbier décide de raser tous les habitants masculins du village qui ne se rasent pas eux-mêmes, et seulement ceux-ci. S’il se rase, il enfreint sa propre règle de ne raser que ceux qui ne se rasent pas. S’il ne se rase pas, il enfreint sa règle de raser tous les hommes qui ne se rasent pas. Aboutissant à une contradiction, il faut déduire qu’il ne peut exister de barbier qui décide de raser tous les habitants masculins du village qui ne se rasent pas eux-mêmes et seulement ceux-ci.
Pourtant, il existe aussi des cas où les définitions récursives sont utiles et ne posent pas de problème, comme celle de factoriel, où la définition de factoriel(n) ne fait intervenir la valeur de factoriel que sur des entiers strictement inférieurs à n. Kleene montre comment définir toutes les fonctions récursives sur les entiers qui étaient utilisées à l’époque, et bien d’autres, uniquement à partir de 6 schémas de base. Et il étudie les cas où ces définitions « ne définissent rien ». Grâce à Kleene, on sait précisément ce que cela veut dire « une fonction arithmétique calculable » : ce sont toutes les fonctions récursives que l’on peut définir à partir de ces 6 schémas.
Alonzo Church
Alonzo Church est le directeur de thèse de Stephen Kleene. Il a un projet a priori un peu plus général. Il veut capturer avec un nouveau formalisme, le lambda-calcul, la notion de « fonction définie intensionnellement par des règles de calcul ». Cette notion de fonction était celle qui prévalait jusqu’au XIXe siècle : une fonction était une procédure permettant de produire un résultat à partir d’un argument. Ce point de vue cède le pas à une nouvelle conception dans la première moitié du XIXe siècle : on attribue à Dirichlet la définition d’une fonction comme une application. Selon ce point de vue, que l’on qualifie d’« extensionnel », une fonction est identifiée avec son graphe : l’ensemble des paires argument-résultat. Cette nouvelle vision repose sur la théorie des ensembles. Elle n’est pas très utile pour réaliser un calcul, dans le sens où il faut une quantité d’information infinie pour définir par exemple une fonction f sur les entiers. Il faut en effet donner explicitement l’image f(n) de chaque entier n. Mais cette approche permet au mathématicien de répondre à des questions auxquelles il est difficile de répondre lorsqu’on conçoit une fonction comme une règle de calcul. Par exemple, « Existe-t-il des fonctions f continues sur R qui vérifient l’équation suivante (où f -1 dénote l’inverse de la fonction f) : f -1(x.y) = f -1(x) + f -1(y) ? » (La réponse est : oui, ce sont les fonctions exponentielles.)
 |
argument | résultat | |
|
|
|
||
| 0 | 1 | ||
| 1 | 2 | ||
| 2 | 3 | ||
| 3 | 4 | ||
| 4 | 5 | ||
| … | … | ||
|
La fonction succ (successeur d’un entier) comme règle de calcul (à gauche) ou bien comme graphe (à droite). |
|||
Si Alonzo Church revient à l’ancienne conception des fonctions, c’est qu’il veut définir précisément les fonctions effectivement calculables. Et pour lui, les fonctions calculables sont celles qui sont « lambda-définissables », c’est-à-dire celles qui peuvent se définir dans son formalisme.
Alan Turing
Le lambda-calcul est un formalisme très abstrait dans le sens où il ne fait référence à aucun processus physique existant. Dans les années trente, c’est un jeu d’écriture effectué à la main par un mathématicien sur une feuille de papier. Alan Turing insiste lui sur la plausibilité physique du calcul : une fonction est effectivement calculable si ses valeurs peuvent être trouvées par un moyen purement mécanique. Et il ajoute qu’il faut comprendre cette affirmation au sens littéral : un moyen purement mécanique est un processus réalisé par une machine physique sans intervention humaine. Turing propose donc en 1936 une machine idéalisée qui travaille sur un ruban divisé en cases. Chaque case contient un symbole que la machine va lire. Suivant le symbole lu et son état propre, la machine peut remplacer ce symbole par un autre, se déplacer vers la case à droite ou bien à gauche, et changer d’état. Les symboles peuvent représenter des nombres, mais pas seulement (mais il faut qu’ils soient en nombre fini, tout comme les états de la machine). La machine de Turing est idéalisée car on a abstrait son fonctionnement réel. On suppose par exemple que le ruban est toujours suffisamment long (donc potentiellement infini), et Turing ne décrit pas une réalisation concrète de sa machine : un dispositif mécanique, pneumatique ou électrique pourrait la concrétiser. Il n’empêche que la machine de Turing idéalise les ordinateurs d’aujourd’hui et, inversement, on peut voir dans les ordinateurs d’aujourd’hui une réalisation physique et électrique de la vision de Turing. Church est sans nul doute le premier, au début des années 1930, à avoir pensé pouvoir définir formellement la calculabilité intuitive (par la lambda-définissabilité). Cependant, c’est l’article de Turing de 1936 et son modèle mécanique de calculabilité qui ont définitivement emporté l’adhésion, selon Gödel, Kleene et Church lui-même.
Emil Post
C’est en 1936 qu’Alan Turing publie sa définition de la calculabilité. Indépendamment, Emil Post propose une machine très similaire à celle de Turing. La motivation de Post est d’établir les limites fondamentales de la pensée humaine. Il suppose que les processus de pensée dont l’esprit humain est capable ne sont pas quelconques : ils sont finis et déterminés par des règles. Enfermés dans des règles (de calcul), il y a des problèmes que l’esprit ne peut résoudre (calculer). Ce rapprochement entre la pensée et le calculable n’est pas une préoccupation unique à Post. Ainsi, dans les années 1950, Turing proposera une procédure, le test de Turing, pour déterminer si une machine fait preuve d’intelligence. Le travail de Post est cependant beaucoup moins avancé que celui de Turing. En effet, en 1936, Turing ne se contente pas de décrire sa machine. Il montre qu’il existe une machine particulière, la machine universelle, qui est capable de simuler toutes les autres machines. Nous y reviendrons par la suite. Turing indique l’équivalence entre la lambda-définissabilité de Church et les fonctions qui sont calculables par sa machine. Par ailleurs, il donne aussi des exemples de fonctions qui ne sont pas calculables par sa machine.
Flèche et harpon contre nasse et filet
À la fin des années 30, on a donc plusieurs définitions mathématiques de la notion de calcul : les fonctions arithmétiques récursives de Kleene, les fonctions lambda-définissables de Church, les fonctions Turing-calculables. Bien que partis avec des motivations différentes, nos quatre chasseurs ont voulu répondre à la même question : qu’est-ce que suivre des règles qui prescrivent des actions sans ambiguïté, en un nombre fini d’étapes, pour aboutir effectivement à un résultat bien défini ? Et chacun est revenu avec un gibier différent dans sa gibecière. Différent, pas si sûr. Car si les réponses apportées par nos chasseurs sont différentes, il s’avère qu’elles sont équivalentes. Autrement dit, ce qui peut être calculé par un moyen peut l’être par un autre. Dans le Sophiste, Platon fait définir à Théétète deux sortes de chasse : la chasse frappeuse qui se pratique à l’aide de flèches, de hameçons ou de harpons, et la chasse qui se fait au moyen de clôtures, qui utilise des filets, des lacets et des paniers pour empêcher la proie de fuir et la cerner. Ainsi, si chaque chasseur a épinglé sa propre définition du calculable, grâce à l’équivalence de leurs différentes approches, on peut affirmer que c’est bien la même notion qui a été capturée dans leur filet. Par exemple, on peut représenter le contenu initial du ruban d’une machine de Turing par un entier m et coder son fonctionnement par le calcul d’une fonction arithmétique : l’application de cette fonction à l’entier m produit un entier qui représente le contenu du ruban de la machine quand elle a cessé de fonctionner. Inversement, un entier m peut se représenter (par exemple en binaire) sur le ruban d’une machine de Turing et il est possible pour chaque fonction récursive f d’exhiber une machine de Turing qui s’arrête en laissant sur son ruban la représentation de f(m). La situation est donc la suivante : nous n’avons pas réussi à définir une notion de calcul suffisamment générale pour que le calcul arithmétique ou le lambda-calcul ou le calcul par une machine de Turing soient des cas particuliers de cette notion la plus générale possible de calcul. Mais on peut montrer que, grâce à des codages, tout ce qu’on peut calculer d’une manière, on peut le calculer d’une autre manière.
Tout n’est pas calculable
Définir ce qui est calculable n’est pas une notion vide, dans le sens où l’on peut montrer qu’il existe des fonctions qui ne sont pas calculables. Tout n’est pas calculable. Être calculable est donc une propriété forte. S’il n’existe pas de machine de Turing permettant de calculer une fonction f, on dit qu’elle n’est pas Turing-calculable. Plus généralement, un problème de décision est dit indécidable s’il n’existe aucun algorithme (aucun programme informatique) qui permette de le résoudre (sans restriction de mémoire ni de temps) à l’aide d’une machine de Turing. On peut définir très formellement des fonctions (par exemple sur les entiers naturels) qui ne sont pas calculables. Par exemple, il n’existe pas de machine de Turing qui permette de répondre à la question de savoir si une machine de Turing quelconque va s’arrêter ou pas. Un autre exemple est celui de la fonction f qui donne le nombre maximum f(n) de 1 que peut inscrire sur son ruban une machine de Turing à n états (et deux symboles 0 et 1). Cette fonction, dite du castor affairé, n’est pas une fonction récursive (et elle ne peut donc pas se calculer par une machine de Turing). Cela ne veut pas dire que pour certaines valeurs de n on ne puisse pas calculer f(n). Par exemple, pour n = 2, f(2) = 4 et pour n = 4, f(4) = 13. Mais il n’existe pas un algorithme unique permettant de calculer f(n). Les exemples précédents (le problème de l’arrêt de la machine de Turing et le calcul de la fonction du castor affairé) sont directement liés au fonctionnement d’une machine de Turing et sembleront peut-être un peu artificiels. Mais il existe des problèmes de mathématiques qui se sont posés bien avant l’invention de la machine de Turing et dont on peut montrer qu’ils n’acceptent pas de solution algorithmique. Nous avons évoqué plus haut le dixième problème de Hilbert qui vise à trouver un algorithme déterminant si une équation diophantienne quelconque admet des solutions entières. Un cas particulier célèbre est la conjecture de Fermat, qui a été résolu dans les années 90 par Andrew Wiles. Wiles a montré que les équations diophantiennes de la forme xn + yn = zn où n est un entier plus grand que 2, n’ont pas de solution, apportant ainsi une preuve à une proposition formulée par Pierre de Fermat en 1637. Le résultat de Wiles montre qu’on peut répondre à la question de Hilbert pour certaines classes d’équations diophantiennes. Par contre, dans les années 1970, Yuri Matiyasevich a montré qu’un algorithme général (c’est-à-dire qui s’applique à n’importe quel système d’équation diophantienne) n’existe pas. Détaillons un peu ce résultat. On peut définir une fonction d qui prend en argument un système d’équation diophantienne s et qui retourne la valeur d(s) = 0 si s n’admet pas de solution et qui retourne la valeur 1 si s admet au moins une solution. Par exemple, si s représente l’équation x4 + y4 = z4, on a d(s) = 0 d’après le théorème de Wiles. La fonction d est parfaitement bien définie (en extension) car un système d’équations soit admet une solution, soit n’en admet pas. Cependant, comment calculer la valeur d(s) pour un s donné ? Le résultat de Matiyasevich indique que la fonction d n’est pas calculable (on ne peut la définir en intension). Autrement dit, il n’existe pas d’algorithme s’exécutant sur une machine de Turing qui calcule pour tout système s le résultat d(s).
La notion intuitive de calculabilité
Il reste cependant un doute : est-ce bien la notion intuitive de calculabilité qui a été capturée ? Ou bien quelque chose de moins expressif ? En effet, les fonctions récursives, ou les fonctions lambda-définissables, ou les fonctions Turing-calculables sont des fonctions que l’on veut déclarer calculables. Mais y en a-t-il d’autres ? Est-il possible qu’un jour quelqu’un arrive et propose un ensemble de règles, que tout le monde s’accorde comme bien déterminées et sans ambiguïté, et qui permette de décrire un algorithme résolvant un problème indécidable (par une machine de Turing) ? La thèse de Church affirme que cela ne sera pas le cas. Mais il ne s’agit pas là d’un théorème. C’est un acte de foi qui affirme que la notion intuitive de calculabilité coïncide avec la notion formelle de calculabilité définie par la machine de Turing. Depuis les années 30, de nombreux systèmes ont été proposés comme définition alternative de la notion de calcul. À chaque fois, on a pu montrer qu’ils étaient équivalents à une machine de Turing, en produisant une traduction appropriée. Ces systèmes, qui ont le même pouvoir d’expression que l’une quelconque de nos trois définitions équivalentes, sont dits Turing-équivalents ou Turing-complets. Le fait que toutes ces tentatives pour formaliser le concept d’algorithme aient conduit à des résultats équivalents est l’argument qui rend la thèse de Church incontournable. Cela doit-il pour autant nous décourager de chercher d’autres manières de calculer ? Nous reviendrons sur cette question dans un autre document.
Newsletter
Le responsable de ce traitement est Inria. En saisissant votre adresse mail, vous consentez à recevoir chaque mois une sélection d'articles et à ce que vos données soient collectées et stockées comme décrit dans notre politique de confidentialité
Niveau de lecture
Aidez-nous à évaluer le niveau de lecture de ce document.
Votre choix a été pris en compte. Merci d'avoir estimé le niveau de ce document !
Jean-Louis Giavitto