Magazine Insolite

Paradoxes du compresseur

Publié le 20 février 2009 par Galaxiedesparadoxes@orange.fr

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.

    Fichier compressé

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


    Vous pourriez être intéressé par :

    Retour à La Une de Logo Paperblog

    Ces articles peuvent vous intéresser :

    • Les paradoxes du progrès

      Nul doute que n’importe qui sache se servir d’un briquet ou d’une allumette, d’un appareil photo numérique ou d’un téléphone portable. Lire la suite

      Par  Galaxiedesparadoxes@orange.fr
      INSOLITE
    • Les paradoxes de mai 68

      Les événements de mai 1968 ont des slogans parmi les plus originaux… Il est interdit d’interdire ! Soyons réalistes : demandons l’impossible. L’alcool tue.... Lire la suite

      Par  Galaxiedesparadoxes@orange.fr
      INSOLITE
    • Deux paradoxes sur les États-Unis

      On critique les États-Unis pour leur propension à intervenir de façon intempestive sur les points chauds de la planète (Vietnam, Afghanistan, Irak…). Lire la suite

      Par  Galaxiedesparadoxes@orange.fr
      INSOLITE
    • Quelques petits paradoxes pour la route

      Quelques petits paradoxes pour route

      Oyez oyez amateurs de paradoxes. Voici un savoureux mets concocté par Jean-Paul Delahaye et à déguster sans plus attendre (sous forme de PDF) à cette adresse ! Lire la suite

      Par  Galaxiedesparadoxes@orange.fr
      INSOLITE
    • Le Codex Seraphinianus

      Codex Seraphinianus

      Le Codex seraphinianus est un livre écrit vers la fin des années 1970 par Luigi Serafini et publié en 1981 par l’éditeur à Franco Maria Ricci dans sa... Lire la suite

      Par  Scriiipt
      INSOLITE, TALENTS
    • Mini éolienne WaterSeer

      Mini éolienne WaterSeer

      Dans le monde éolien voici la mini éolienne WaterSeer qui est une invention écologique et ingénieuse, dont le projet est développé par la société américaine... Lire la suite

      Par  Tonton
      INSOLITE
    • [Dossier] 10 Pères Noël incontournables du cinéma et des séries TV

      [Dossier] Pères Noël incontournables cinéma séries

      25 Déc 2016 Gilles Rolland DOSSIERS 0 commentaire Partager la publication "[Dossier] 10 Pères Noël incontournables du cinéma et des séries TV" FacebookTwitter L... Lire la suite

      Par  Onrembobine
      INSOLITE

    Magazine