Auteur: Serge Boisse
Date: Le 26/03/2023 à 14:03
Type: web/MOC
Tags: maths,informatique,calculabilité
pub: oui
commentaires: ouiCopier

La non-calculabilité de théta(n)

théta(n) est la fonction N->N qui pour n donné renvoie la taille minimale d'une fonction qui retourne n. C'est donc une fonction de "compression" qui retourne la description la plus courte (en terme de programme d'ordinateur) que l'on peut faire du nombre n. Cette fonction possède une énorme importance théorique, en particulier les nombres n tels que théta(n) ~= nombre de bits de n sont les nombres incompressibles ou aléatoires. Tous les nombres ne sont pas aléatoires, mais la majorité des nombres l'est, bien qu'il soit impossible d'en exhiber un !

théta(n) dépend évidemment du langage utilisé, mais on démontre que les résultats sont identiques à une constante près quels que soient les langages et les ordinateurs utilisés. Du reste, je ne ferai pas d'hypothèse sur le langage ou la machine utilisée dans cette démonstration.

La démonstration est basée sur un célèbre paradoxe découvert par Bertrand Russel, et qui est à la base de la restructuration de la théorie des ensembles due à Zermelo-Fraenkel (la théorie "ZF" est celle qui est actuellement utilisée par tous les mathématiciens, sauf quelques logiciens coupeurs de cheveux en quatre).

Considérons le nombre n = 297297, et écrivons le en français : deux cent quatre vingt dix sept mille deux cent quatre ving dix sept. Ma description en français comporte treize mots. Or, et c'est facile à vérifier, tous les nombres inférieurs à 297297 s'écrivent en français en moins de treize mots. par conséquent, 297297 est "le plus petit nombre non descriptible en moins de treize mots".

Ce qui est intéressant, c'est que la phrase ci-dessus fait onze mots ! nous avons donc pu décrire 297297 en moins de treize mots ! Mais alors, quel est le plus petit nombre non descriptible en moins de onze mots ???

La solution de ce paradoxe passe par une définition stricte des niveaux de langage utilisé : le terme décrire peut s'appliquer à des nombres, mais pas a des descriptions, et ainsi de suite.

Il est intéressant de voir que l'on peut réaliser une version purement "informatique" de ce paradoxe :

Supposons donc la fonction n -> théta(n) calculable : cela signifie qu'il existe un programme de taille T0 qui implémente l'algorithme qui permet de calculer théta(n). Je vais montrer que cela est impossible car cela mène à une contradiction cause du paradoxe ci dessus.

Par ailleurs nous aurons besoin du lemme suivant :

Lemme 1

la fonction n->théta(n) peut prendre des valeurs arbitrairement élevées :

Preuve :

Si cela était faux, alors il existerait une borne supérieure à théta(n) . Soit B cette borne supérieure ; cela signifierait que tous les nombres n quels qu'il soient peuvent se décrire en moins de B bits (au sens ou on saurait construire un programme de moins de B bits qui retourne n). Or il n'existe au maximum que P = 2B programmes de moins de B bits, et donc ces P programmes devraient retourner tous les entiers ! Ceci est évidemment impossible, d'où le lemme.

Nous savons donc maintenant que , étant donné un nombre b quelconque de bits, il existe un nombre n tel que théta(n) > b

Considérons alors l'algorithme suivant :

Prendre en entrée un entier b
Soit n = 0
boucler :
   ajouter 1 à n
   si théta(m) > b alors afficher n
   sinon continuer la boucle
Copier

Cet algorithme possède une fin, en effet théta(m) est calculable (par hypothèse) et peut prendre des valeurs arbitrairement élevées (Lemme 1) ; par suite, il suffit d'énumérer les entiers jusqu'à ce que l'on tombe sur l'un d'eux tel que sont théta soit supérieure à b, et cela arrivera certainement.

Mais que fait cet algorithme ? Il cherche le premier nombre dont le théta soit supérieur à b, c'est à dire le premier nombre non descriptible en moins de b bits.

Posons par exemple b = T0+ 10 000 ; l'algorithme ce dessus nous calculera le plus petit nombre qui ne peut pas être décrit en moins de b bits, c'est à dire que tout programme qui afficherait ce nombre devrait avoir une taille supérieure à b bits. Or notre algorithme est très simple et a une taille de l'ordre de T0 + 100 (rappelons que T0 est la taille du code de la fonction theta()).

Il y a donc contradiction, cqfd.

< Retour à la page précédente