Limites de l’informatique

22 novembre 2003

En informatique, on dit qu’une opération est « complexe » si elle est logiquement possible mais irréalisable en pratique.

Une première forme de « complexité » informatique provient de la représentation des nombres dans la mémoire de l’ordinateur. Celle-ci ne pouvant contenir qu’une quantité limitée de chiffres, les calculs informatisés portent sur un sous-ensemble des nombres rationnels, approximations des nombres réels. La précision des calculs est donc limitée même si le nombre de chiffres que contient la mémoire est élevé. Il en résulte de grandes difficultés mathématiques[1].

Une deuxième forme de « complexité » informatique est liée au nombre de calculs élémentaires que nécessite une opération. En notant n le cardinal de l’ensemble sur lequel on travaille, on dira que la « complexité » est linéaire si elle demande de l’ordre de n calculs, quadratique si elle en demande de l’ordre de n², « exponentielle » si elle en demande de l’ordre de eⁿ ou, pire, de nⁿ.

Si par exemple il faut réaliser le calcul élémentaire sur chaque couple d’éléments de l’ensemble, la « complexité » est quadratique car le nombre des couples est égal à n(n -1)/2. S’il faut calculer sur chacune des parties de l’ensemble, la « complexité » est exponentielle car le nombre des parties est égal à 2ⁿ. Enfin, si l’on doit calculer sur chacune des permutations des éléments de l’ensemble dont le nombre est n ! (factorielle de n), la « complexité » est alors de l'ordre de nⁿ car n! ~ (2πn)^½(n/e)ⁿ (formule de Stirling[2]).

Certains problèmes à la formulation simple peuvent exiger une durée de calcul de l’ordre de l’âge de l’univers : c’est le cas du « problème du commis voyageur » dès que n atteint quelques dizaines[3] (pour trouver l’itinéraire optimal passant par plusieurs villes il faut calculer la longueur de n! itinéraires).

La « complexité » permet d’évaluer la faisabilité d’un calcul : si n dépasse quelques centaines (c’est le cas de la plupart des bases de données d’une entreprise), un calcul linéaire sera facile, un calcul quadratique difficile et un calcul exponentiel impossible. Le programmeur qualifié arrive parfois à rendre possible un traitement qui, programmé de façon sommaire, aurait été impossible ou difficile : s’il s’agit par exemple de faire un tri, un calcul rustique sera quadratique mais un calcul bien conçu sera d’ordre nLog(n) seulement.

Ces deux formes de « complexité » informatique n’ont rien à voir avec la complexité du réel qu’aucun système fini ne peut décrire[4]. En effet, même si l’opération qui consiste à répéter un grand nombre de fois un calcul élémentaire demande un temps très long, elle n’est pas au plan logique plus complexe que le calcul élémentaire lui-même et celui-ci est aussi simple que l’idée qui a guidé sa conception. Il en est de même pour les difficultés mathématiques liées à la représentation des nombres réels par des nombres rationnels. La « complexité » informatique est un homonyme de la complexité du réel. C’est pourquoi nous avons utilisé les guillemets pour la noter.

Par contre la troisième forme de « complexité » informatique provient des limites de la logique elle-même : comme l'a démontré Gödel, aucun système logique ne peut contenir la démonstration de toutes les vérités. Le domaine de la pensée pure est lui aussi complexe puisque aucun système fini ne peut en rendre compte (il résulte du théorème de Gödel qu'il est impossible de mettre au point un programme capable de vérifier tous les programmes).  

Théorème de Gödel

Gödel a démontré que si l’on construit un système logique pour formaliser la théorie des nombres entiers, ce système contient au moins une formule A telle que ni A, ni sa négation non-A ne peuvent être démontrées dans le cadre du système. Russell et Whitehead avaient tenté de fonder l'ensemble de la logique sur une base axiomatique[5]. Le théorème de Gödel[6] prouve que ce but est hors d'atteinte : quel que soit le nombre (fini) des axiomes retenus pour fonder un système logique, il existera toujours des propositions vraies qu’il sera impossible de démontrer dans le cadre de ce système. 

La démonstration de Gödel est technique. Voici une description schématique de son raisonnement :

1) Supposons qu’il existe une Théorie Complète (TC) fondée sur un nombre fini d'axiomes et permettant, si l’on considère une phrase quelconque, de décider sans jamais se tromper si cette phrase est vraie ou non.

2) Considérons la phrase « TC ne dira jamais que la présente phrase est vraie ». Nommons cette phrase G, ce que nous noterons : G = « TC ne dira jamais que G est vraie ».

3) Soumettons G à TC et demandons à TC de dire si G est vraie ou non.

4) Si TC dit que G est vraie, alors G est fausse. Mais alors comme TC a dit que G était vraie, TC a commis une erreur. Cependant par hypothèse TC ne se trompe jamais. Donc TC ne dira jamais que G est vraie.

5) Si « TC ne dit jamais que G est vraie », G est vraie. Mais d'après ce que nous venons de voir TC ne pourra jamais le dire. 

6) Il ne peut donc pas exister de Théorie Complète, c’est-à-dire de théorie permettant, quelle que soit la phrase que l'on considère, de dire si elle est vraie ou non.

Ce raisonnement rappelle le paradoxe fameux qui met en scène un Crétois disant : « Les Crétois ne disent que des mensonges ».  

Application du théorème de Gödel à l'informatique

Un des résultats les plus importants de la théorie de l'informatique[7], c'est qu'il est impossible de concevoir un programme capable de vérifier tous les programmes. 

Supposons en effet qu'un tel programme P existe. 

1) Si le programme A est juste, P(A) = v (v pour « vrai »). 

2) Soumettons à P le programme G = « P(G) = f » (f pour « faux »).  

3) Si P(G) = v, le programme P(G) = f est faux ; donc P[P(G) = f ] = P(G) = f, ce qui est contraire à l'hypothèse. Si P(G) = f, alors on a P[P(G) = f ] = P(G) = v, ce qui est encore contraire à l'hypothèse. 

4) Ainsi G ne peut pas être vérifié par P.

Il ne peut donc pas exister de programme capable de vérifier tous les programmes. Certes on peut définir des méthodes de vérification efficaces et les outiller de sorte qu'elles soient faciles à utiliser. Mais ces méthodes, aussi efficaces soient-elles, ne garantissent pas que tous les programmes qu'elles valident soient corrects : « Program testing can be used to show the presence of bugs, but never to show their absence[8] ».

Commentaire de : Michael Sipser, Introduction to the Theory of Computation, PWS 1997

Ce livre présente la théorie de l'informatique : la machine de Turing, la théorie des langages, les algorithmes, la décidabilité, le fait qu'il n'existe pas de programme qui sache vérifier les programmes, le cryptage à clé publique, les ordres de grandeur qui distinguent le faisable (polynomial) de l'impossible (exponentiel), etc.

Définitions, lemmes et théorèmes s'enchaînent. Sipser est un grand pédagogue. Sans renoncer à la rigueur, il conduit son lecteur le long d'un chemin facile, vérifiable ; en partant d'automates simples il fait découvrir les langages, les grammaires, la machine de Turing, la décidabilité, la récursion, la complexité dans le temps (durée des calculs) et dans l'espace (taille de la mémoire nécessaire), etc. Il est vrai qu'il faut  revenir souvent sur ses pas pour se remémorer les résultats acquis, mais c'est le moindre des efforts que l'on puisse consentir.

Sipser écrit deux fois la même démonstration : une fois en langage courant pour donner une idée générale (ce qu'il appelle « proof ideas »). ; la deuxième fois en notation formelle. Lorsqu’on lit un chapitre la première fois, on se contente des « proof ideas » pour avoir une idée d'ensemble. Puis on lit les démonstrations en entier pour se familiariser avec les notations.