En toute logique : une origine de l’ordinateur
Charles Babbage.
La naissance de l’ordinateur est attribuée à Charles Babbage. Dès 1834, afin de construire des tables mathématiques pour différentes fonctions, Babbage conçut une machine de calcul générique, dont quelques exemplaires furent fabriqués. Il proposa également une machine bien plus ambitieuse, la machine analytique, qu’il ne put construire pour des raisons économiques et technologiques. C’est cette machine en projet dont on a pu montrer a posteriori qu’elle aurait les caractéristiques fondamentales d’un ordinateur. Cependant Babbage disait de sa machine analytique qu’elle « pourrait tout faire mis à part composer des chansons populaires ». Cette citation peut laisser à penser qu’il n’avait pas perçu la portée véritablement universelle de son invention, mais reste d’actualité : il n’est toujours pas vraiment possible de faire composer automatiquement des chansons populaires à un ordinateur ! Cette limite, la logique nous permet de l’appréhender, comme nous allons le voir ici.
Voilà donc un objet qui d’un côté est hautement perfectionné, mais dont d’un autre côté on ne saisit bien ni la logique du fonctionnement, ni ses utilisations, de nature a priori totalement étrangères les unes aux autres. C’est pourquoi l’invention de l’ordinateur n’a pas été de même nature que celle d’une découverte issue d’un « heureux hasard » (comme ce fut le cas pour la pénicilline par exemple).
Les aspects technologiques, tels que l’amélioration des performances de stockage et de calcul, la démocratisation massive et rapide des technologies de l’information, etc., sont souvent mis en avant dans les discours sur l’histoire de l’informatique. Ces éléments sont importants pour la réalisation effective des machines, mais n’expliquent pas les caractéristiques fondamentales qui en font une machine universelle. Nous les passerons donc volontairement sous silence, pour nous concentrer uniquement sur l’histoire des idées qui constituent le socle théorique à partir duquel l’ordinateur a pu être imaginé. Nous nous proposons de montrer comment des réflexions de type philosophique sur la vérité ont conduit à formaliser la définition de l’ordinateur.
Les Grecs : logique, raisonnement et réflexivité
C’est dans la pensée grecque qu’on trouve les prémisses de ces réflexions. Aristote est reconnu comme étant le père de la logique. Il fut le premier à s’interroger sur le raisonnement en tant que tel, sans s’intéresser au contenu du raisonnement. Son objectif était d’éviter les erreurs : son maître, Platon, enseignait en effet que les « lois de la pensée » devraient imiter les lois qui règlent le mouvement des astres (qui eux n’errent jamais sur leurs orbites).
Gravure représentant Épiménide.
Pourtant, d’autres philosophes soulevèrent des objections, qui montraient que si on pouvait formaliser le raisonnement, les choses n’étaient pas aussi simples qu’il le semblait. Les paradoxes de Zénon d’Élée sur le mouvement montrent notamment que penser la réalité n’est pas aussi immédiat qu’on pourrait le croire. Dans un autre domaine, celui-là purement intellectuel, Épiménide montra un problème du même ordre. On peut résumer son paradoxe par l’énoncé suivant : « je mens ». Si l’on considère cette affirmation du point de vue de sa vérité, alors de deux choses l’une : soit en disant « je mens », je dis la vérité, alors cela signifie que je mens, donc que je ne dis pas la vérité ; soit je ne dis pas la vérité, mais alors en disant précisément « je mens », je dis la vérité. Dans les deux cas, on se retrouve face à des contradictions qui se renvoient l’une l’autre comme les images de deux miroirs face à face.
Le problème soulevé est en fait celui de l’autoréférence : la phrase « je mens » fait référence à sa propre vérité. C’est en étudiant précisément ce problème que l’on a débouché sur la définition de l’ordinateur, qui n’est rien d’autre qu’une machine capable de se simuler elle-même, c’est-à-dire une réalisation matérielle de cette idée d’autoréférence.
Leibniz : la réflexion est un calcul
Portrait de Gottfried Wilhelm Leibniz.
Au XVIIe siècle, Leibniz, un génie universel (philosophe, théologien, mathématicien, logicien : aucun domaine du savoir ne lui échappait), et européen avant l’heure, s’est interrogé sur la mécanique des mathématiques. Il était fasciné par cet « art d’infaillibilité » qu’Aristote avait commencé à développer. Il avait notamment retenu cette idée que la forme du raisonnement pouvait suffire à en assurer la validité.
En logique, il fut un visionnaire, et il laissa de plus nombreux travaux inachevés que de réalisations effectives. Cependant, ses « rêves » marquèrent un tournant conceptuel majeur. Il eut notamment deux idées formidables : la première est celle d’une langue universelle ayant la rigueur des mathématiques, où l’on pourrait s’exprimer sans ambiguïtés (lingua caracteristica universalis). La seconde est celle d’un calcul logique (calculus ratiocinator) : il imaginait que nos pensées pouvaient se décrire au moyen d’un alphabet des pensées humaines, qu’on pourrait combiner entre elles par des combinaisons semblables aux opérations de l’algèbre usuelle. C’est en particulier par cette notion de calculus ratiocinator que Leibniz s’inscrit dans la lignée des précurseurs de l’informatique.
Fondement des mathématiques
Georg Cantor.
Vers la fin du XIXe siècle, l’introduction de la théorie des ensembles par Cantor a pour projet d’unifier les mathématiques : algèbre, analyse, géométrie, etc., ne sont dans ce formalisme que des aspects différents du raisonnement mathématique. Un problème est soulevé par Burali-Forti, puis Russell, par l’apparition d’un paradoxe.
Ce formalisme permet en effet de définir des objets qui conduisent à une contradiction : on peut y décrire l’ensemble des ensembles qui ne s’appartiennent pas à eux-mêmes. Il ne s’agit ni plus ni moins que du paradoxe d’Épiménide mathématisé !
Divers formalismes furent proposés pour résoudre ce problème (dont celui de Zermelo qui est celui utilisé aujourd’hui).
Le principe fondamental de la théorie des ensembles de Cantor est le schéma de compréhension. L’idée est de dire qu’une propriété caractérise un ensemble : l’ensemble défini par la propriété P est la collection des éléments e vérifiant P. Par exemple, l’ensemble des entiers pairs peut se voir comme l’ensemble des entiers e tels qu’il existe un entier d et e = 2 d.
Le problème est que dans la théorie de Cantor, les propriétés sur lesquelles portent les définitions d’un ensemble ne sont pas limitées. On peut donc définir un ensemble qui correspond à la propriété « ne pas s’appartenir à soi-même » qui porte sur les ensembles d’ensembles. On a R={a | a ∉ a}. On peut en dériver que X est élément de X implique que X n’est pas élément de X et vice versa. Autrement dit une contradiction.
La solution proposée par Zermelo consiste à restreindre le schéma de compréhension. En gros, l’idée est qu’on peut définir, au moyen d’une proposition, que ces propriétés ne s’appliquent que sur des objets déjà existants. Ainsi, un ensemble est la collection des éléments a vérifiant la propriété P et appartenant à un certain ensemble donné E. On ne peut donc construire que des ensembles plus petits que ceux déjà existants. Si on veut construire un ensemble plus grand, il faut l’ajouter comme un axiome. Cela implique une hiérarchisation des ensembles définissables et brise ainsi les possibilités d’autoréférence (un terme ne peut pas baser sa propre définition sur lui-même).
Pour clore une fois pour toutes cette « crise des fondements », David Hilbert proposa au congrès de mathématiques de Paris en 1900, une série de questions sur les fondements des mathématiques. On peut regrouper ces questions de la façon suivante :
- Cohérence : est-ce que tout ce que l’on peut prouver en mathématique est forcément vrai ? Autrement dit, aucune démonstration correcte ne doit aboutir à une absurdité.
- Complétude : est-ce que tout ce qui est vrai est forcément prouvable ?
- Décidabilité : est-ce qu’il existe une méthode infaillible pour décider si un énoncé mathématique est vrai ou faux ?
Gödel et la machine de Turing universelle
À cette époque, la majorité des mathématiciens pensaient que la réponse à ces trois questions était oui. À tort, comme le montra dans les années trente un logicien autrichien, Kurt Gödel.
Kurt Gödel.
La première étape de Gödel fut de plonger les mathématiques à l’intérieur d’elles-mêmes (autoréférence) en réalisant en cela plus ou moins le programme de Leibniz : tout énoncé mathématique devient un objet mathématique (il code les théorèmes comme des chiffres et les raisonnements comme des opérations), plus précisément un système formel. La cohérence d’un tel système formel devient dès lors un théorème qu’on peut prouver ou non. Or Gödel a montré que de deux choses l’une, pour un système formel particulier : soit ses formules sont cohérentes, mais à ce moment-là, elles sont incomplètes, soit elles sont incohérentes. En particulier, il a montré que pour tout système formel assez puissant (il suffit qu’il contienne les postulats de l’arithmétique), si ces formules sont cohérentes, alors on ne peut donner une démonstration de cette cohérence ! Il ne s’agit ni plus ni moins que d’une version sophistiquée du paradoxe du menteur d’Épiménide.
Ce résultat frappa fortement les esprits. En travaillant sur le sujet plus précis de la décidabilité, un jeune mathématicien anglais du nom d’Alan Turing invente une classe de machines idéales permettant de faire des calculs élémentaires. Il formalise ainsi la notion de « méthode » énoncée dans le problème d’Hilbert. C’est en étudiant de près cette classe de machines que Turing se rend compte qu’elle présente une particularité remarquable : certaines machines de Turing sont capables de simuler toutes les machines imaginables, moyennant un certain codage : il s’agit de l’ordinateur et de la programmation. Nos ordinateurs ne sont que la réalisation technologique de cette machine de Turing intellectuelle.
Alan Turing.
On s’aperçoit encore une fois que l’autoréférence est au centre de la réflexion qu’a menée Turing. Si avant lui existaient différents types de calculateurs plus ou moins perfectionnés, c’est l’idée d’une machine universelle (c’est-à-dire capable de simuler n’importe quelle autre machine de la même classe : y compris elle-même donc) qui est fondamentale. En effet, puisque le processus du calcul est un calcul en tant que tel, une machine ne pouvant simuler son fonctionnement ne peut représenter tous les calculs (son fonctionnement en étant un particulier).
Avant Turing, une machine telle que celle de Babbage était déjà une machine universelle, même s’il n’avait pas réussi à la construire, et que contrairement à Turing, il n’avait pas compris qu’elle était universelle. Elle donnait la possibilité de faire des branchements conditionnés au résultat d’un calcul précédent, des boucles et des opérations arithmétiques, elle pouvait donc (en théorie) calculer toutes les fonctions récursives, et de ce fait elle était universelle.
Mais en pratique, l’utilisation de machines à calculer comprenait trois parties distinctes : la machine elle-même (un assemblage d’engrenages), le programme (une suite de manipulations par exemple pour calculer une multiplication avec un additionneur), et les données (les valeurs sur lesquelles le calcul porte). Ce qu’a montré Turing avec sa machine universelle était que cette distinction n’était qu’une illusion. Plus précisément, la machine universelle permet sans modifications physiques de simuler le comportement de n’importe quelle autre machine. Le tour de force est que les données et les instructions sont vues de façon uniforme et peuvent même changer de statut au cours de l’exécution d’un programme. La machine universelle représente donc les mécanismes fondamentaux de toute machine effectuant un calcul, aussi compliqué soit-il.
En grossissant le trait, on peut donc soutenir que c’est par une réponse négative à un problème sur le fondement des mathématiques que l’ordinateur a été défini – ce problème des fondements provenant lui-même de toute une réflexion sur les statuts relatifs de la vérité et de la démonstration (pendant longtemps les deux notions ont été considérées comme équivalentes).
Qui sait, sans doute que même sans Turing, des ordinateurs électroniques auraient pu être des machines universelles. Babbage, le savant du XIXe siècle, est peut-être bien l’inventeur de l’ordinateur, mais une chose est probable : sans les logiciens, les tâtonnements pour en comprendre les possibilités et surtout les limites auraient été bien plus importants et… on essaierait peut-être encore vainement de leur faire composer des chansons populaires.
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 !
Frédéric Prost