Le problème de la compression des données, dans sa forme la plus simple, peut concerner les nombres et leurs notations. Les nombres peuvent être désignés par des chiffres ("onze" pour le nombre 11), des expressions mathématiques ("deux dans le vingtième" pour 1048576), expressions de chaîne ("cinq neuf" pour 99999), noms propres ("numéro de la bête" pour 666, "l'année de la mort de Turing" pour 1954), ou des combinaisons arbitraires de ceux-ci. Toute désignation convient par laquelle l'interlocuteur peut déterminer clairement de quel numéro nous parlons. Évidemment, parlez-en à votre interlocuteur "factoriel de huit" plus efficace que la notation équivalente "quarante mille trois cent vingt". Une question logique se pose ici : quelle est la notation la plus courte pour un nombre donné ?
Le philosophe Bertrand Russell publié en 1908 , qui aborde la question de la notation des nombres du côté opposé : Quel est le plus petit nombre qui ne nécessite pas quatre-vingts lettres ?
Un tel nombre doit exister : à partir de quatre-vingts lettres et espaces russes, vous ne pouvez composer que 3480 3480 désignations, ce qui signifie qu'en utilisant quatre-vingts lettres, vous ne pouvez désigner que 3480 XNUMX chiffres. Cela signifie qu'il est impossible de désigner de cette manière un certain nombre ne dépassant pas XNUMX.
Cela signifie que ce numéro correspondra à la désignation "le plus petit nombre pour lequel quatre-vingts lettres ne suffisent pas", qui ne comporte que 78 lettres ! D'une part, ce numéro doit exister ; en revanche, si ce numéro existe, alors sa désignation ne lui correspond pas. Paradoxe!
La manière la plus simple d’écarter ce paradoxe est de faire référence au caractère informel des notations verbales. Par exemple, si seul un ensemble d’expressions spécifiquement défini était autorisé dans la notation, alors "le plus petit nombre pour lequel quatre-vingts lettres ne suffisent pas" ne serait pas une notation valide, alors que des notations pratiquement utiles comme "factoriel de huit" resterait acceptable.
Existe-t-il des moyens formels de décrire la séquence (algorithme) des actions sur les nombres ? Il y en a, et en abondance, on les appelle des langages de programmation. Au lieu de notations verbales, nous utiliserons des programmes (par exemple en Python) qui affichent les nombres requis. Par exemple, pour cinq neuf, le programme convient print("9"*5). Nous continuerons à nous intéresser au programme le plus court pour un numéro donné. La durée d'un tel programme est appelée Nombres; c'est la limite théorique à laquelle un nombre donné peut être compressé.
Au lieu du paradoxe de Berry, nous pouvons désormais en considérer un similaire : Quel est le plus petit nombre qu’un programme de kilo-octets ne suffit pas à générer ?
Nous raisonnerons de la même manière que précédemment : il y a 2561024 kilo-octets de textes, ce qui signifie que pas plus de 2561024 nombres peuvent être générés par des programmes kilo-octets. Cela signifie qu'un certain nombre ne dépassant pas 2561024 ne peut pas être dérivé de cette manière.
Mais écrivons un programme en Python qui génère tous les textes possibles en kilo-octets, les exécute pour exécution, et s'ils génèrent un nombre, ajoute ensuite ce nombre au dictionnaire des nombres accessibles. Après avoir vérifié les 2561024 XNUMX XNUMX possibilités, peu importe le temps que cela prend, le programme recherche le plus petit nombre manquant dans le dictionnaire et imprime ce nombre. Il semble évident qu'un tel programme tiendra dans un kilo-octet de code - et produira le nombre même qui ne peut pas être généré par un programme kilo-octet !
Quel est le problème maintenant ? Cela ne peut plus être attribué au caractère informel de la notation !
Si vous êtes confus 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 - alors vous pouvez faire la même chose sans cela : pour chacun des 2561024 nombres, à tour de rôle , parcourez les 2561024 programmes possibles, jusqu'à ce qu'il n'y en ait plus un qui convienne. Peu importe qu'une telle recherche dure très longtemps : après avoir vérifié moins de (2561024)2 paires du numéro et du programme, elle se terminera et trouvera ce numéro très précieux.
Ou ça ne finira pas ? En effet, parmi tous les programmes qui seront essayés, il y aura while True: pass (et ses analogues fonctionnels) - et l'affaire n'ira pas plus loin que tester un tel programme !
Contrairement au paradoxe de Berry, où le problème résidait dans le caractère informel de la notation, dans le second cas nous avons une reformulation bien déguisée . Le fait est qu’il est impossible de déterminer le résultat d’un programme dans un temps fini. En particulier, la complexité de Kolmogorov : il n'existe pas d'algorithme qui permettrait, pour un nombre donné, de trouver la longueur du programme le plus court qui imprime ce nombre ; ce qui signifie qu'il n'y a pas de solution au problème de Berry : trouver la longueur de la désignation verbale la plus courte pour un nombre donné.
Source: habr.com