Table des matières Chapitre 1 : Numérotations

Chapitre 0 : introduction

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 :

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 :

PNP

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

Lectures complémentaires conseillées