Paradoxes sur la compression des données

La tâche de compression des données, dans sa forme la plus simple, peut se référer aux nombres et à leurs désignations. Les nombres peuvent être désignés par des numéraux («onze» pour le nombre 11), par des expressions mathématiques («deux à la vingtième» pour 1048576), par des expressions textuelles («cinq nines» pour 99999), par des noms propres («le nombre de la bête» pour 666, «l'année de la mort de Turing» pour 1954), ou par des combinaisons arbitraires de ceux-ci. Toute désignation qui permet à l'interlocuteur d'identifier sans ambiguïté de quel nombre il s'agit est valable. Il est évident qu'il est plus efficace de dire à l'interlocuteur «le facteuriel de huit» que la désignation équivalente «quarante mille trois cent vingt». La question qui se pose ici est : quelle désignation pour un nombre donné est la plus courte ?

Le philosophe Bertrand Russell a publié en 1908 le «paradoxe de Berry», qui aborde la question des désignations des nombres sous un angle opposé : quel est le plus petit nombre pour lequel il n’est pas suffisant d’utiliser quatre-vingts lettres ?
Un tel nombre doit exister : avec quatre-vingts lettres russes et espaces, on peut composer seulement 3480 désignations, donc, avec l'utilisation de quatre-vingts lettres, il est impossible de désigner plus de 3480 nombres. Ainsi, un nombre ne pouvant pas être désigné de cette façon ne dépassera pas 3480.

Donc, ce nombre sera désigné par «le plus petit nombre pour lequel il n’est pas suffisant d’utiliser quatre-vingts lettres», qui contient seulement 78 lettres ! D'une part, ce nombre doit exister ; d'autre part, si ce nombre existe, alors sa désignation ne lui correspond pas. Un paradoxe !

La façon la plus simple de balayer ce paradoxe est de faire référence à l'informalité des désignations verbales. On pourrait dire que si seules un ensemble spécifiquement défini d'expressions était autorisé alors «le plus petit nombre pour lequel il n’est pas suffisant d’utiliser quatre-vingts lettres» cela ne constituerait pas une désignation valide, tandis que des désignations pratiquement utiles comme «le facteuriel de huit» resteraient valides.

Existe-t-il des moyens formels pour décrire la séquence (algorithme) d'actions sur les nombres ? Oui, et en abondance — on les appelle des langages de programmation. Utilisons des programmes au lieu de désignations verbales (par exemple, en Python), pour afficher les nombres nécessaires. Par exemple, pour cinq nines, le programme suivant convient : print("9"*5). Nous allons continuer à nous intéresser à la plus courte programme pour un nombre donné. On appelle la longueur d'un tel programme la complexité de Kolmogorov .; c'est la limite théorique à laquelle un nombre donné peut être compressé.

Au lieu du paradoxe de Berry, on peut maintenant envisager un analogue : quel est le plus petit nombre pour lequel un programme de moins d'un kilo-octet n'est pas suffisant ?

Nous allons raisonner de la même manière qu'auparavant : il existe 2561024 textes d'un kilo-octet, donc, avec des programmes d'un kilo-octet, on peut produire au maximum 2561024 nombres. Il existe donc un certain nombre, qui ne dépasse pas 2561024, qui ne peut pas être produit de cette manière.

Mais écrivons un programme en Python qui génère tous les textes d'un kilo-octet possibles, les exécute, et si l'un d'eux produit un nombre, ajoute ce nombre à un dictionnaire d'atteignabilité. Après avoir vérifié toutes les 2561024 possibilités, peu importe le temps que cela prendra — le programme cherche quel est le plus petit nombre absent du dictionnaire et l'affiche. Il semble évident qu'un tel programme tiendra dans un kilo-octet de code — et affichera ce nombre qui est impossible à produire avec un programme d'un kilo-octet !

Quel est donc le piège maintenant ? Avec une telle formalisation, on ne peut plus passer à la légère sur les notations !

Si vous êtes dérangé par le fait que notre programme nécessitera une quantité astronomique de mémoire pour fonctionner — un dictionnaire (ou un tableau de bits) de 2561024 éléments — on peut faire tout cela sans lui : parcourir chacun des 2561024 nombres un par un en testant tous les 2561024 programmes possibles jusqu'à ce que l'on trouve le bon. Peu importe que ce processus prenne beaucoup de temps : après avoir vérifié moins de (2561024)2 paires du nombre et du programme, il doit se terminer et trouver ce nombre tant convoité.

Ou ne se terminera-t-il pas ? Car parmi tous les programmes qui seront testés, on rencontrera while True: pass et ses analogues fonctionnels — et ensuite, la vérification d'un tel programme n'avancera plus !

Contrairement au paradoxe de Berry, où le piège résidait dans la non-formalisation des notations, dans le second cas, nous avons une reformulation bien masquée "du problème de l'arrêt". En effet, il est impossible de déterminer la sortie d'un programme dans un temps fini. En particulier, la complexité de Kolmogorov est non calculable.: il n'existe aucun algorithme permettant de trouver, pour un nombre donné, la longueur du programme le plus court affichant ce nombre ; par conséquent, il n'y a pas de solution non plus pour le problème de Berry — trouver, pour un nombre donné, la longueur de la représentation verbale la plus courte.

Source : habr.com