Théorie de la calculabilité

Le fragment principal de la machine d'Anticythère.

Bien avant de théoriser ce qu’est la calculabilité, les scientifiques ont commencé à développer des machines à calculer. Ainsi, dans l'Antiquité, la machine d'Anticythère date du I^er siècle av. J.-C.[5] - [6] - [7].

Dans une période plus récente, Wilhelm Schickard a imaginé, au XVII^e siècle, une « machine » à calculer mécanique avec une horloge à calculer qui utiliserait un système de rouages. Cependant, ce projet dépassait les capacités techniques des artisans de l’époque et n’a jamais pu voir le jour[8].

La première machine à calculer opérationnelle du XVII^e siècle est donc la pascaline de Blaise Pascal. Elle utilise un système de pignons lanternes et permet de réaliser des calculs simples (addition, soustraction, multiplication et division)[9].

Au XIX^e siècle, Joseph Marie Jacquard met au point le métier à tisser Jacquard. Premier système mécanique programmable avec cartes perforées, il est à l’origine des premiers programmes de calculs.

Charles Babbage développe en 1821 une machine à calculer destinée au calcul de polynômes appelée la machine à différences. En 1834, à partir de cette première machine, il développe la machine analytique en y incorporant les cartes du métier Jacquard. Cette machine analytique contient une unité de contrôle, une unité de calcul, une mémoire et une entrée-sortie et préfigure les ordinateurs d’aujourd’hui (voir XIX^e siècle- Le début de la production industrielle (dans l'article Calculatrice mécanique).

Entre 1842 et 1843, Ada Lovelace traduit un article sur la machine analytique de Babbage. Ce dernier lui propose alors d’ajouter des notes pour développer et commenter le texte. S’ensuivit une collaboration étroite entre les deux scientifiques. Elle ajouta finalement sept notes représentant trois fois le volume du texte original. Sa dernière note porte sur un véritable algorithme permettant de calculer les nombres de Bernoulli avec la machine analytique. Le programme ainsi rédigé est considéré comme le premier véritable programme informatique jamais écrit car on y trouve un langage destiné à être exécuté sur une machine. Ada Lovelace, en plus d’être la première programmeuse au monde, suggère que la machine est un calculateur universel, préfigurant la notion de calculabilité.

David Hilbert, présente, lors du deuxième congrès international des mathématiciens tenu en 1900, une liste de 23 problèmes que l’on appelle aujourd’hui les problèmes de Hilbert. Le dixième problème de Hilbert s'énonce ainsi[10] :

« On se donne une équation diophantienne à un nombre quelconque d'inconnues et à coefficients entiers rationnels : On demande de trouver une méthode par laquelle, au moyen d'un nombre fini d'opérations, on pourra distinguer si l'équation est résoluble en nombres entiers rationnels. »

Ce problème requiert une méthode algorithmique générale qui décide si une équation diophantienne possède des solutions entières. Il s’agit du seul des 23 problèmes de Hilbert qui soit un problème de décision, c’est-à-dire un problème qui se décompose en une infinité de problèmes particuliers qui attendent une réponse par « oui » ou « non ». Une solution à un problème de décision est un algorithme qui, pour chaque entrée, fournit la réponse « oui » ou « non ». Cependant à l’époque où le dixième problème de Hilbert est formulé, il n’y a pas de définition rigoureuse de ce qu’est un algorithme.

De plus, à l’époque de la crise des fondements des mathématiques, David Hilbert s’oppose fermement à l’idée que certaines questions scientifiques restent sans réponse. Il croit au tiers exclu, un principe logique qui affirme qu’une proposition est soit démontrable, soit sa négation est démontrable. Pour régler le problème de ces fondements, il rédige un programme (qu’on appelle aujourd’hui programme de Hilbert) dont il établit les prémices en 1900 dans l’introduction à sa liste de problèmes. Il développe ensuite ce programme dans les années 1920 avec l’aide de Paul Bernays et Wilhelm Ackermann. Son idée est que tant que ce que l’on manipule est fini, les mathématiques sont sûres. Pour justifier l'utilisation d'objets abstraits ou idéaux, en particulier infinis, il suffit de montrer que la théorie qui les utilise est cohérente, mais bien sûr cette cohérence doit elle-même être démontrée par des moyens finis. On appelle cette approche le « formalisme ».

Kurt Gödel assiste à une conférence de David Hilbert sur la complétude et la cohérence des systèmes mathématiques lorsqu’il est encore étudiant. Il obtient son doctorat en 1929 grâce à sa thèse où il établit la complétude du calcul des prédicats du premier ordre (en termes intuitifs, ce théorème nous apporte que tout énoncé vrai est démontrable), résultat connu sous le nom de théorème de complétude de Gödel. Ce théorème va dans le sens de Hilbert.

Cependant, en 1931, il publie ses célèbres théorèmes d'incomplétude. Il y montre que pour toute théorie axiomatique non contradictoire de l'arithmétique, il existe des énoncés arithmétiques vrais qui ne sont pas démontrables dans cette théorie. Autrement dit, Gödel marque un tournant dans l’histoire de la logique puisqu’il anéantit la possibilité d'une démonstration de la cohérence des mathématiques énoncée vingt ans auparavant dans le programme de Hilbert. De plus, pour prouver son premier théorème d’incomplétude, il utilise le codage de Gödel et un argument diagonal (découvert par Georg Cantor en 1891) que la théorie de la calculabilité utilise beaucoup (notamment pour le problème de l'arrêt).

En 1933, Gödel part pour la première fois aux États-Unis. Il met au point l'idée de la calculabilité et étudie les fonctions récursives, si bien qu'il donne une conférence sur les fonctions récursives générales et le concept de vérité (voir : section Vérité et démontrabilité, Théorèmes d’incomplétude de Gödel). Ces travaux sont développés en utilisant la construction de la numérotation de Gödel.

Alan Turing ainsi que Alonzo Church montrent indépendamment l’indécidabilité du problème de la décision de Hilbert[2] :

• Church est connu pour le développement du lambda-calcul (premier formalisme définissant les fonctions récursives, qui a une grande importance dans la théorie de la calculabilité) pour la première démonstration de l’indécidabilité du problème de l'arrêt (un problème de décision particulier).
• Turing, quant à lui, caractérise un peu plus tard en 1936, dans son article « On Computable Numbers, with an Application to the Entscheidungsproblem », ce qu’est un procédé calculable. Pour cela, il imagine non pas une machine matérielle, mais un « être calculant » qui peut être un appareil logique très simple ou un humain bien discipliné appliquant des règles. On appellera cette machine, la machine de Turing. Dans le cours de son raisonnement, il démontre que le problème de l’arrêt d’une machine de Turing ne peut être résolu par algorithme : il n’est pas possible de décider avec un algorithme (c’est-à-dire avec une machine de Turing) si une machine de Turing donnée s’arrêtera. Son article présente également la notion de nombre réel calculable puisqu’il déduit de l'indécidabilité du problème de l'arrêt que l'on peut définir des nombres réels qui ne sont pas calculables. Turing introduit ainsi les concepts de programme et de programmation.

Kleene et Turing démontrent en 1938 que le lambda-calcul de Church, les fonctions générales récursives (modèle dit de Herbrand-Gödel) et les machines de Turing ont des capacités équivalentes. Cette équivalence démontre ensuite qu'un certain nombre de formalisations mathématiques de la notion de traitement par des processus mécaniques ont des aptitudes en tous points semblables à l'intuition de Church. Cette constatation aboutit à la thèse de Church (appelée aussi thèse de Church-Turing)[2].