Théorie de la calculabilité

La théorie de la calculabilité (appelée aussi parfois théorie de la récursion) est un domaine de la logique mathématique et de l'informatique théorique qui vise à identifier les limites de ce qui peut être calculé par un algorithme. Cette théorie s'est développée dans les années 1930 lorsqu'ont été proposées pour la première fois des définitions formelles d'un algorithme, et des méthodes pour montrer que certains problèmes ne peuvent pas être résolus algorithmiquement.

La calculabilité ne se préoccupe pas de l'efficacité des algorithmes, qui est l'objet de la théorie de la complexité, mais seulement de l'existence ou de la non-existence d'un algorithme qui résout un problème donné, sur un ordinateur idéalisé tel qu'une machine de Turing, démontrée équivalente en possibilités à tous les ordinateurs existants.

La notion la plus centrale de la calculabilité est celle de fonction calculable. Son intérêt est justifié par la thèse de Church, qui affirme que les fonctions calculables avec la définition formelle correspondent exactement aux fonctions qui peuvent être calculées par un humain ou une machine, dans le monde physique.

Cependant, la calculabilité ne se limite pas à séparer les fonctions calculables des fonctions non-calculables, mais cherche aussi à comparer les fonctions non-calculables entre elles, en s'appuyant sur la notion de réduction pour affirmer (informellement) que certaines fonctions sont « plus incalculables » que d'autres. Les niveaux d'incalculabilité sont appelés degrés de Turing, et une partie de la calculabilité consiste à étudier leur structure.

Définition d'une fonction calculable

Intuitivement, une fonction $f$ est une fonction calculable s'il existe une méthode précise qui, étant donné un argument $x$, permet d'obtenir l'image $f(x)$ en un nombre fini d'étapes. Plusieurs formalisations mathématiques de ce que peut être une méthode de calcul existent et on peut montrer qu'un grand nombre d'entre elles (fonctions récursives, machine de Turing, lambda-calcul, machine à compteurs, automate cellulaire, etc.) sont équivalentes, c'est-à-dire qu'elles définissent exactement les mêmes fonctions calculables. Formellement, une fonction calculable est donc une fonction calculable selon l'une de ces définitions, par exemple le lambda-calcul.

La thèse de Church énonce que les définitions mathématiques équivalentes ci-dessus capturent bien le concept intuitif de méthode de calcul défini par des moyens finis, dit d'une autre façon « N'importe quel moyen raisonnable de formaliser la notion d'« algorithme » est, en fait, équivalent à la notion de machine de Turing ».

Définition d'un nombre calculable

Alan Turing définit un nombre réel calculable comme étant un nombre dont l'expression décimale est calculable avec des moyens finis. Autrement dit, il existe une machine de Turing qui permet d'énumérer la suite de tous les chiffres de ce nombre (en un temps infini).

Par extension, un nombre complexe est calculable si sa partie réelle et sa partie imaginaire sont simultanément calculables.

Existence de fonctions non calculables

Il peut être démontré qu'il existe des fonctions $f$ qui sont incalculables, c’est-à-dire dont, étant donné $x$, la valeur $f(x)$ ne peut être calculée par des moyens finis par aucun algorithme que l'on aurait associé à $f$. En effet, il y a un nombre dénombrable d'algorithmes (un algorithme peut toujours être représenté par un mot fini sur un alphabet fini), donc il y a seulement un nombre dénombrable de fonctions calculables. En revanche, les fonctions (partielles ou pas) sur un domaine infini ne sont pas dénombrables, par le théorème de Cantor. Ceci fournit une preuve de l'existence de fonctions incalculables.

On connaît de nombreux exemples explicites de fonctions incalculables. Le plus courant est celui du problème de l'arrêt : il n'existe pas de programme universel qui prenne n'importe quel programme en argument et qui, en temps fini, renvoie « oui » si l'exécution du programme reçu en argument finit par s'arrêter et « non » s'il ne finit pas. Un autre exemple d'une fonction non calculable, plus perturbante dans un certain sens, est celle dite du castor affairé. Il s'agit d'une fonction bien définie, ayant une valeur pour chaque entier, mais on ne peut pas la calculer pour les entiers suffisamment grands. Gregory Chaitin a introduit un nombre Ω qui a, entre autres, la particularité d'être parfaitement défini, mais dont la suite des décimales ne peut pas être donnée par une fonction calculable.

Histoire

Alors que la notion intuitive de fonction calculable est aussi vieille que les mathématiques, la formalisation de ces notions a commencé dans la décennie 1930 (voir Logique et théorie des ensembles) afin de répondre à des problèmes fondamentaux de logique mathématique, dont celui énoncé par David Hilbert et appelé Entscheidungsproblem ou problème de la décision.

Développement des machines à calculer

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..

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.

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).

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^{[Selon qui ?][réf. nécessaire]}.

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é^{[réf. nécessaire]}.

Développement de la théorie de la calculabilité et des modèles de calcul

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 :

« 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 :

• 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).

Modèles de calcul

Plusieurs modèles de calcul sont utilisés en calculabilité :

• les fonctions récursives ;
• le lambda-calcul ;
• les machines de Turing ;
• les machines à compteurs ;
• les automates cellulaires ;
• les circuits booléens ;
• les machines parallèle à accès arbitraire ou PRAM ;
• les Random access machines ou RAM ;
• les machines de Blum-Shub-Smale.

Malgré la diversité de ces modèles, la classe de fonctions calculables par chacun de ceux-ci est unique et cette constatation est le fondement de la thèse de Church.

Organisations professionnelles

La principale organisation professionnelle pour la théorie de la récursivité est l'Association for Symbolic Logic (ASL), qui publie de nombreux ouvrages académiques et revues universitaires. L'association Computability in Europe (CiE) organise une série de conférences annuelles.

Bibliographie

 : document utilisé comme source pour la rédaction de cet article.

• « [PDF] Complexité et calculabilité, université de Bordeaux ». 
• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• Jean-Michel Autebert, Calculabilité et décidabilité, Dunod, 1992 (ISBN 978-2225826320)
• Pierre Wolper, Introduction à la calculabilité, Dunod, 2006, 3^e éd. (ISBN 978-2100499816)
• (en) George Boolos, John P. Burgess et Richard Jeffrey, Computability and Logic, Cambridge, 2007, 5^e éd. (ISBN 978-0521701464)
• Daniel Lacombe, « La théorie des fonctions récursives et ses applications (Exposé d’information générale) », Bulletin de la Société mathématique de France, vol. 88,‎ 1960, p. 393-468 (lire en ligne)
• (en) Alan Turing, « On Computable Numbers, with an Application to the Entscheidungsproblem », Proceedings of the London Mathematical Society, London Mathematical Society, 1937
• (en) S. Barry Cooper, Computability Theory, Chapman & Hall / CRC, 2004 (ISBN 1-58488-237-9).
• Benoît Monin et Ludovic Patey, Calculabilité, Calvage et Mounet, avril 2022, 828 p. (ISBN 978-2-916352-96-1). — Ouvrage très complet qui aborde des sujets avancés comme la la théorie algorithmique de l'aléatoire, les mathématiques à rebours et l'hypercalculabilité.
• Michel Bourdeau et Jean Mosconi, Anthologie de la calculabilité, recueil de textes, édition Cassini, ouvrage en attente de publication depuis décembre 2020.
• René Cori et Daniel Lascar, Logique mathématique II. Fonctions récursives, théorème de Gödel, théorie des ensembles, théorie des modèles [détail des éditions]

Voir aussi

Articles connexes

• Suite d'entiers
• Théorème de récursion de Kleene
• Hiérarchie arithmétique
• Nombre réel calculable
• Computationnalisme
• Théorème de Rice
• Oméga de Chaitin