La théorie de la calculabilité s'attaque à la question suivante :
Q1 : qu'est-ce qui est calculable (par une procédure
automatique),
et qu'est-ce qui ne l'est pas ?
Alors que la plupart des gens croient que ce type de question relève de conversations au "café du commerce" ("derrière l'ordinateur il y a l'homme", etc.) des réponses scientifiques fondamentales à cette question ont été fournies autour de 1935 par :
Alonzo Church, mathématicien américain professeur à Princeton, et père du λ-calcul ;
Kurt Gödel, célèbre pour avoir prouvé (entre autres) qu'il existe en arithmétique des propositions vraies et indémontrables ; ce mathématicien autrichien émigra aux USA en 1940 (un de ses maîtres avait été assassiné par un étudiant nazi en 1933) ;
Alan Turing, célèbre pour sa machine ; ce mathématicien anglais a eu un rôle majeur dans le déchiffrement des codes utilisés par l'armée allemande pendant la seconde guerre mondiale, ce qui n'empêcha pas un tribunal de son propre pays de le condamner en 1952 pour … homosexualité ! Bien que décédé en 1954, il a son propre site sur la toile !
Une caractéristique fondamentale des réponses ainsi apportées à Q1 est qu'elles sont indépendantes de la technologie : le modèle de calcul introduit par Church (λ-calcul) s'est révélé équivalent à celui de Turing, et à d'autres (fonctions récursives) proposés par les mêmes chercheurs et leurs proches.
Après la seconde guerre mondiale, les premiers ordinateurs furent construits, selon les principes d'architecture de John von Neumann. Cette architecture sert toujours de base aux ordinateurs modernes ; elle est caractérisée par un processeur, capable d'effectuer des opérations arithmétiques et logiques élémentaires sur des registres, et par une mémoire à accès direct. La mémoire contient à la fois des données et des instructions pour le processeur ; chaque mot a une adresse, et l'adresse de l'instruction à exécuter se trouve dans un registre du processeur (PC, program counter). Ce modèle de calcul est à son tour équivalent à ceux de Church et Turing.
Autour de 1970, Chaitin et Kolmogorov ont étendu considérablement les travaux de Gödel sur la distinction entre ce qui est vrai et ce qui est démontrable ; les recherches dans cette direction permettent de mieux comprendre ce qu'est le hasard, et pourquoi il y a des lois physiques simples et universelles.
A la même époque (autour de 1970), a été développée la théorie de la complexité, qui s'attaque à la question suivante :
Q2 : qu'est-ce qui est calculable
efficacement,
et qu'est-ce qui ne l'est pas ?
Pour fixer les idées, et bien distinguer les questions Q1 (théorie de la calculabilité) et Q2 (théorie de la complexité), notons qu'une Gsec (un milliard de secondes, soit 230 secondes), correspond à une durée de plus de trente ans ; comme l'âge de l'univers est d'environ 15 milliards d'années, un ordinateur fonctionnant à 2GHz depuis le début de l'univers n'aurait pas encore exécuté 290 instructions, disons 2100 pour être large… Or en théorie de la calculabilité on considère souvent des algorithmes qui parcourent toutes les données de taille n, et pour une modeste taille n de 1Ko on atteint déjà 28000 cas à parcourir !
Les considérations précédentes, quoique non dépourvues de bon sens, dépendent d'unités assez arbitraires pour mesurer l'efficacité ; au contraire la théorie de la complexité distingue deux classes fondamentales d'algorithmes :
Un algorithme non déterministe peut être simulé par un algorithme déterministe, mais au prix d'une perte radicale d'efficacité, car l'exploration de tous les choix possibles est en général de complexité exponentielle. On connaît beaucoup de problèmes naturels qui peuvent être résolus par un algorithme de la classe NP, mais pour lesquels aucun algorithme de la classe P n'est connu.
On pense donc tenir là une réponse indépendante de la technologie à la question Q2. Mais, surprise, malgré les efforts de nombreux chercheurs renommés depuis trente ans, et des débuts prometteurs (théorème de Cook), on reste incapable de prouver que les classes P et NP sont effectivement distinctes, si bien que la conjecture :
P ≠ NP
fait aujourd'hui partie de la liste des dix problèmes mathématiques non résolus les plus célèbres (sur le modèle du théorème de Fermat, sauf que ce dernier est "tombé" récemment).
Le théorème de Cook et les travaux qui en ont découlé fournissent quantité de problèmes, dits NP-complets, tels que la découverte d'un algorithme (déterministe) polynomial pour résoudre un seul d'entre eux prouverait (à la surprise générale) que P = NP.
En pratique, toute la cryptographie moderne repose sur la conviction qu'il existe des fonctions calculables efficacement, utilisées pour chiffrer (on dit aussi "crypter") des informations confidentielles, mais dont la fonction inverse, utilisée pour déchiffrer (décrypter) n'est pas calculable efficacement, sans une information supplémentaire, tenue secrète (clef de déchiffrement).
Introduction to the Theory of Computation, par Michael Sipser, professeur au MIT. Le style est très clair, et l'auteur est un des meilleurs spécialistes actuels de la théorie de la complexité.
Une première partie traite des automates (langages rationnels) et des grammaires (langages algébriques), non couverts par le présent cours.
La seconde partie, sur la calculabilité, adopte une approche différente de celle présentée ici. Sipser souhaite présenter à ses lecteurs les machines de Turing, dans le prolongement de la première partie (automates), puis les résultats classiques sur la décidabilité (ou non) de problèmes liés aux automates et aux grammaires algébriques (sections 4.1 et 5.1), non traités ici. Le traitement est très clair, et on y trouvera aussi le problème de correspondance de Post (section 5.2). Par contre le théorème de Rice est laissé en exercice (exercice 5.22), et la récursivité (self-reference) est traitée comme un "sujet avancé", ce qui découle du choix du modèle de calcul (machines de Turing), et me semble mal adapté à un public d'informaticiens. Du coup, comme dans beaucoup d'ouvrages de calculabilité, certaines constructions ou démonstrations sont inutilement compliquées, alors que les théorèmes fondamentaux deviennent élémentaires en utilisant un langage de programmation classique, comme C.
Cette seconde partie de l'ouvrage se termine par une introduction à deux sujets importants, très bien exposés : la section 6.2 traite de la décidabilité des théories logiques, en particulier du théorème de Gödel, et la section 6.4 de la complexité de Kolmogorov.
La troisième partie, sur la complexité, est la plus importante de l'ouvrage, car on y trouve exposés et démontrés très clairement de nombreux résultats importants et récents. Le modèle des machines de Turing est souvent indispensable dans cette partie, pour définir rigoureusement le temps de calcul et l'espace mémoire. Parmi les sujets traités, et non couverts ici, citons les classes L et NL (espace logarithmique), les théorèmes de hiérarchie, la relativisation, la complexité des circuits, et les systèmes de preuve interactifs (classe IP).
Automata and Computability, par Dexter Kozen, professeur à l'université Cornell.
Les leçons 3 à 18 traitent des automates (langages rationnels), et les leçons 19 à 27 des grammaires (langages algébriques), sujets non couverts par le présent cours.
Les leçons 28 à 39 traitent de la calculabilité. L'exposé commence classiquement par une présentation des machines de Turing ; la présentation reste concise, comme dans le livre de Sipser, mais est souvent plus détaillée (la théorie de la complexité n'est pas traitée). On y trouvera en particulier les compléments suivants au présent cours :