La tâche de compression des données dans sa forme la plus simple peut concerner les nombres et leur notation. 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), des expressions de chaîne (
«cinq neuf» pour 99999), des noms propres (
«le nombre de la bête» pour 666,
«l'année de la mort de Turing»). " Pour 1954), ou leurs combinaisons arbitraires. Toute désignation par laquelle l'interlocuteur peut déterminer sans ambiguïté quel type de discours convient convient. De toute évidence, informer l'interlocuteur du
«huit factoriel» est plus efficace que l'appellation équivalente
«quarante mille trois cent vingt» . Cela soulève la question logique: quelle est la désignation la plus courte pour un nombre donné?
Le philosophe Bertrand Russell a publié en 1908 le
«Berry Paradox», qui aborde la question de la notation des nombres de l'autre côté:
quel est le plus petit nombre pour indiquer quelles quatre-vingts lettres ne suffisent pas?Un tel nombre doit exister: sur quatre-vingts lettres et espaces russes, vous pouvez faire un total de 34
80 désignations, ce qui signifie qu'en utilisant quatre-vingt lettres, vous ne pouvez pas désigner plus de 34
80 chiffres. Par conséquent, un certain nombre, pas plus de 34
80 , ne peut pas être désigné de cette manière.
Cela signifie que la désignation
«le plus petit nombre pour lequel quatre-vingts lettres ne suffit pas» correspondra à ce numéro, dans lequel il n'y a que 78 lettres! D'une part, ce nombre doit exister; d'autre part, si ce nombre existe, alors sa désignation ne lui correspond pas. Paradoxe!
Le moyen le plus simple de rejeter ce paradoxe est de se référer à l'informalité des désignations verbales. Par exemple, si seul un ensemble d'expressions spécifiques était autorisé dans la notation, alors
«le plus petit nombre pour lequel quatre-vingt lettres ne
suffisent pas
» ne serait pas une désignation valide, tandis que les désignations pratiquement utiles du
type «huit factoriel» resteraient valides.
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 la notation verbale, nous utiliserons des programmes (par exemple, en Python) qui affichent les nombres nécessaires. Par exemple, pour cinq neuf, le programme d'
print("9"*5) convient. Nous continuerons de nous intéresser au programme le plus court pour un nombre donné. La longueur d'un tel programme s'appelle la
complexité de Kolmogorov du nombre; Il s'agit de la limite théorique à laquelle un nombre donné peut être compressé.
Au lieu du paradoxe du Berry, on peut maintenant envisager un semblable:
quel est le plus petit nombre pour lequel un programme en kilo-octets ne suffit pas?Nous discuterons de la même manière que précédemment: il y a
256,1024 kilo-octets, ce qui signifie que pas plus de
256,224 nombres peuvent être affichés dans les programmes en kilo-octets. Cela signifie qu'un certain nombre, ne dépassant pas 256
1024 , ne peut pas être déduit de cette manière.
Mais nous écrivons en Python un programme qui génère tous les textes possibles en kilo-octets, les lance pour exécution, et s'ils impriment un certain nombre, il ajoute ce nombre au dictionnaire accessible. Après avoir vérifié toutes les 256
1024 possibilités, peu importe le temps que cela prend - le programme recherche le plus petit nombre qui ne figure pas dans le dictionnaire et affiche 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 affiché dans un programme en kilo-octets!
Quelle est la prise maintenant? Il ne peut plus être attribué à l'informalité de la notation!
Si vous êtes confus que notre programme nécessitera une quantité astronomique de mémoire pour fonctionner - un dictionnaire (ou bitmap) de 256
1024 éléments - alors vous pouvez faire la même chose sans lui: pour chacun des 256
1024 numéros, parcourez les 256
1024 possibles jusqu'à ce qu'un programme approprié soit trouvé. Peu importe qu'une telle énumération dure très longtemps: après avoir vérifié moins de (256
1024 )
2 paires du nombre et du programme, elle se terminera et trouvera ce nombre très apprécié.
Ou cela ne prendra-t-il pas fin? En effet, parmi tous les programmes qui seront essayés, il y aura
while True: pass (et ses homologues fonctionnels) - et les choses n'iront pas au-delà de la vérification d'un tel programme!
Contrairement au paradoxe du Berry, où la capture était informelle de la notation, dans le deuxième cas, nous avons une reformulation bien déguisée du
«problème d'arrêt» . Le fait est que selon le programme, il est impossible de déterminer sa conclusion dans un temps fini. En particulier, la complexité de Kolmogorov n'est pas
calculable : il n'y a pas d'algorithme qui permettrait à un nombre donné de trouver la longueur du programme le plus court qui produit ce nombre; ce qui signifie qu'il n'y a pas de solution au problème Berry - pour trouver pour un nombre donné la longueur de la désignation de mot la plus courte.