Calculabilité

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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. La calculabilité cherche d'une part à identifier la classe des fonctions qui peuvent être calculées à l'aide d'un algorithme et d'autre part à appliquer ces concepts à des questions fondamentales des mathématiques. Une bonne appréhension de ce qui est calculable et de ce qui ne l'est pas permet de voir les limites des problèmes que peuvent résoudre les ordinateurs.

Mais la notion de calculabilité ne se limite pas aux fonctions. On peut parler également de nombres calculables (réels ou complexes).

Définition d'une fonction calculable[modifier | modifier le code]

Intuitivement, une fonction est une fonction calculable s'il existe une méthode précise qui, étant donné un argument , permet d'obtenir l'image 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[1].

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 fonctionnant en temps fini.

Définition d'un nombre calculable[modifier | modifier le code]

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[modifier | modifier le code]

Il peut être démontré qu'il existe des fonctions qui sont incalculables, c’est-à-dire dont, étant donné , la valeur ne peut être calculée en un temps fini par aucun algorithme que l'on aurait associé à . 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, de par le théorème de Cantor[2]. 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[modifier | modifier le code]

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[3][modifier | modifier le code]

Bien avant de théoriser ce qu’est la calculabilité, les scientifiques ont commencé à développer des machines à calculer.

Le premier à imaginer une « machine » à calculer mécanique est Wilhelm Schickard au XVIIe siècle avec une horloge à calculer qui utiliserait un système de rouages. Cependant, ce projet dépasse les capacités techniques des artisans de l’époque et n’a jamais pu voir le jour (voir Calculatrice_mécanique#Horloges_à_calculer_imparfaites).

La première machine à calculer opérationnelle du XVIIe 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) (voir Calculatrice_mécanique#Premières_machines_à_calculer).

Au XIXe siècle, Joseph Marie Jacquard met au point le métier à Tisser Jacquard. Il est le premier système mécanique programmable avec cartes perforées et à 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 qui contient une unité de contrôle, une unité de calcul, une mémoire et une entrée-sortie, est le précurseur des ordinateurs d’aujourd’hui (voir Calculatrice_mécanique#XIXe_siècle_-_Le_début_de_la_production_industrielle).

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 au final 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 au monde car on y trouve un langage destiné à être exécuté sur une machine. Ada Lovelace, en plus d’être considérée comme le premier programmeur au monde, pense même que la machine est un calculateur universel. Cette manière de penser préfigure la notion de calculabilité.

Développement de la théorie de la calculabilité et des modèles de calcul[3][modifier | modifier le code]

David Hilbert, présente une liste de 23 problèmes (que l’on appelle aujourd’hui problèmes de Hilbert) que les mathématiciens peinent à résoudre lors du deuxième congrès international des mathématiciens tenu en 1900. Le dixième problème de Hilbert est le suivant :

« On donne une équation de Diophante à 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 demande de trouver une méthode algorithmique générale qui puisse décider si une équation diophantienne possède des solutions entières. Il s’agit du seul des 23 problèmes de Hilbert qui est un problème de décision, c’est-à-dire un problème qui se décompose en une infinité de problèmes particuliers qui demandent une réponse par « oui » ou « non ». Une solution d’un problème de décision est donnée sous la forme d’un algorithme qui, pour chaque entrée donnée, doit fournir la réponse « oui » ou « non ». Cependant à l’époque où le dixième problème de Hilbert est posé, il n’y avait 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 vraie, soit fausse. 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émisses 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 la suivante : 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 semble aller 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 arithmétique non contradictoire, 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[modifier | modifier le code]

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

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.

Notes et références[modifier | modifier le code]

  1. Historiquement, la première caractérisation formelle et mathématique des algorithmes (Origins of Recursive Function Theory dans Annals of the History of Computing, Vol. 3 No 1, janvier 1981).
  2. [PDF] Peut-on tout programmer ? Cours de l'université de Lille.
  3. a et b « [PDF] Complexité et calculabilité, université de Bordeaux »

Références[modifier | modifier le code]

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]