Preuve élégante et théorème de Chaitin

N. Lygeros




Même si la notion d'élégance se trouve sous forme de germe dans l'oeuvre de Leibniz, elle est considérée comme formalisée qu'après les travaux de Chaitin. Ce dernier dans la continuation des recherches de Gödel mais aussi de Turing, a su mettre en évidence cette notion afin de la rendre opérationnelle. Pour se faire, il a utilisé la notion des programmes qui n'a pris véritablement son sens qu'à partir de la date de création des premiers ordinateurs. La définition de Chaitin est la suivante: Un programme élégant est le plus court programme à fournir une sortie donnée. Il s'agit donc d'une forme que nous qualifierons d'irréductible sur le plan mathématique. Le théorème de Chaitin peut s'énoncer de la manière suivante: Il n'est en général pas possible de déterminer si un programme donné est élégant ou pas. Ce qui est remarquable, c'est que la preuve de ce résultat a elle-même une forme d'élégance au sens large du terme et non dans celui de la définition de Chaitin. Il se démontre par l'absurde. En effet, nous considérons qu'il existe un programme E qui puisse tester l'élégance d'un programme donné. Nous construisons alors un programme B qui prend en entrée un entier naturel N et énumère tous les programmes possibles Pk qui sont plus longs que N. B en tant que programme peut faire tourner le programme E sur l'ensemble des programmes Pk qu'il a énumérés jusqu'a ce qu'il trouve un programme qui soit élégant. Alors B fait tourner ce programme et produit la même sortie que ce dernier. Considérons alors le terme suivant: B doit produire un résultat. Il est basé sur le fait qu'il existe une infinité de programmes élégants aussi si le programme E fonctionne comme il a été défini, alors il doit en trouver un, qui possède le résultat escompté. A présent activons le programme B avec l'entier N qui est cette fois égal à la longueur de B+1. B produira alors la même sortie qu'un programme Pk, qui a été déclaré comme élégant par le programme E. Mais Pk est plus long que B aussi Pk ne peut être élégant. Ainsi le programme E n'est pas un testeur d'élégance. Ce qui est absurde. De cette manière, nous voyons que la formalisation de cette notion quelque peu abstraite initialement permet d'obtenir un résultat d'ordre mathématique. Ce résultat montre indirectement qu'il est vraisemblable que les preuves par l'absurde soient plus courtes que les autres surtout si le théorème à démontrer est particulièrement informatif. Nous avons en réalité une sorte de complémentarité. Plus l'information est importante, plus la démonstration par l'absurde a son efficacité car elle utilisera le potentiel du théorème à démontrer. De façon plus générale encore la notion d'élégance permet d'établir une véritable hiérarchie, dans les démonstrations, et dans les stratégies qui sont des formes encore plus étendues puisqu'une démonstration écrite peut être considérée a posteriori comme l'ensemble d'instructions d'une tactique. La puissance de la notion d'élégance provient aussi du fait, qu'elle fonctionne indépendamment de toute connaissance de la distribution de la variable aléatoire. Nous sommes donc dans le contexte le plus général possible et c'est aussi pour cela que nous considérons les travaux comme la continuation des recherches de Turing sur sa machine universelle.







free counters


Opus