Paradoxes du compresseur

Le paradoxe du compresseur s’applique à tout compresseur de données informatiques sans perte. Il exprime qu’un compresseur sans perte universel ne peut pas exister. Plus précisément, pour tout compresseur sans perte, on est certain que :

il est impossible de compresser strictement tous les mots ;

s’il existe un mot qui est strictement compressé alors il existe un autre mot dont la version compressée est strictement plus grande que le mot lui-même ;

pour n’importe quel mot de départ auquel on applique de manière répétée le compresseur, on est nécessairement dans l’un des cas de figure suivants :
- soit une suite de mots se répète infiniment,
- soit les mots successifs obtenus atteignent des tailles arbitrairement grandes.

Un autre paradoxe célèbre concernant les compresseurs est le suivant :
pour tout mot, il existe un compresseur qui le compresse en un mot de 1 bit.

Cela rappelle qu’une signification n’est pas portée par un message en soi, mais par un doublet message/décodeur. Ces idées ont été poussées très loin avec la théorie de la complexité de Kolmogorov.

[Cet article est une ébauche en cours d’amélioration]