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 notre ère. 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.
Compter, calculer, une histoire ancienne
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 serait 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 XIIIe 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. Le jeu des combinaisons de toutes les propositions possibles permettait d’énumérer automatiquement toutes sortes de raisonnements (cf. ci-dessous).
© A. Couty, CRDP de l’Académie de Versailles.
Ce dessin représente une « machine à penser », une roue, imaginée au XIIIe siècle, dont le but était, grâce à ses deux anneaux mobiles, de mécaniser des raisonnements logiques. Par ce processus, on peut voir dans cet objet les prémices de l’informatique !
Plus tard, Leibniz, au XVIIe siècle, imaginait la construction d’une machine qui pouvait manipuler des symboles afin de déterminer les valeurs des énoncés mathématiques. En 1821, Charles Babbage présente à la Société royale britannique une « machine à différence ». 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. 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.
Qu’est-ce qu’un calcul ?
Cette rapide évocation de quelques étapes historiques marquantes laisse cependant intacte la question : qu’est-ce qu’un calcul ? Une question qui attend une réponse urgente au début du XXesiècle, en même temps que d’autres questions sur les fondements mêmes des mathématiques.
Dans les années trente, quatre mathématiciens au moins sont en lice pour répondre à cette question : Stephen Kleene, Alonzo Church, Alan Turing et Emil Post. Chacun veut définir une certaine notion du calcul. La quête 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é, qui vise à définir précisément ce qui est effectivement calculable. Alonzo Church est sans nul doute le premier à avoir pensé pouvoir définir formellement ce que l’on s’accorde à reconnaître intuitivement comme un calcul. En 1935, Stephen Kleene, son étudiant en thèse, formalise ce qu’est une « fonction arithmétique calculable » à travers la notion de « fonction récursive ». Alonzo Church essaie de capturer plus généralement l’idée de fonctions définies par des règles de calcul en développant un nouveau formalisme, le « lambda-calcul ».
Une machine sans conducteur
Alan Turing explore une autre approche, qui va lier la notion de « calcul » à la notion de « machine » : une machine qui peut fonctionner sans intervention humaine, une machine idéale qui n’a pas (encore) de réalisation physique, mais qui semble plausible. Cette machine possède un ruban, aussi long que nécessaire, sur lequel une tête de lecture/ écriture peut lire, écrire, effacer et réécrire des symboles pris dans un alphabet fini. La machine possède aussi un état interne et l’ensemble des états internes possibles est fini. Quand la tête lit un symbole, elle réagit en fonction de l’état interne en le modifiant, en réécrivant un symbole et en déplaçant éventuellement la tête vers la droite ou la gauche du symbole courant sur le ruban. Alan Turing justifie l’organisation et le fonctionnement de cette machine par analogie avec le travail d’un opérateur humain qui disposerait d’une mémoire propre très limitée, mais qui pourrait écrire des symboles sur une feuille de papier pour l’aider à dérouler un calcul. Au lieu d’écrire sur une surface, la machine écrit sur un ruban aussi long que nécessaire. Il apparaît clairement que cette machine abstraite peut réellement être construite.
Cette construction est le résultat d’un défi relevé par huit étudiants : ils ont concrétisé une représentation de la machine qu’avait imaginée le mathématicien Alan Turing en 1936.
