El problema de la compressió de dades, en la seva forma més simple, pot relacionar-se amb els nombres i les seves anotacions. Els nombres es poden indicar amb xifres ("onze" per al número 11), expressions matemàtiques ("dos al vintè" per a 1048576), expressions de cadena ("cinc nou" per a 99999), noms propis ("nombre de la bèstia" per 666, "any de la mort de Turing" per a 1954), o combinacions arbitràries d'aquests. Qualsevol designació és adequada per la qual l'interlocutor pugui determinar clarament de quin número estem parlant. Evidentment, digues-ho al teu interlocutor "factorial de vuit" més eficient que la notació equivalent "quaranta mil tres-cents vint". Aquí sorgeix una pregunta lògica: quina és la notació més curta per a un nombre determinat?
El filòsof Bertrand Russell va publicar el 1908 , que toca el tema de la notació numèrica des del costat oposat: Quin és el nombre més petit que no requereix vuitanta lletres?
Aquest nombre ha d'existir: a partir de vuitanta lletres i espais russos només podeu fer 3480 designacions, el que significa que amb vuitanta lletres no podeu designar més de 3480 números. Això vol dir que és impossible designar un nombre determinat no més de 3480 d'aquesta manera.
Això vol dir que aquest número correspondrà a la designació "el nombre més petit per al qual vuitanta lletres no són suficients", que només té 78 lletres! D'una banda, aquest nombre ha d'existir; en canvi, si aquest número existeix, la seva designació no li correspon. Paradoxa!
La manera més fàcil de descartar aquesta paradoxa és referir-se a la informalitat de les notacions verbals. Com, si només es permetés un conjunt d'expressions específicament definits a la notació, aleshores "el nombre més petit per al qual vuitanta lletres no són suficients" no seria una notació vàlida, mentre que les anotacions pràcticament útils com "factorial de vuit" continuaria sent acceptable.
Hi ha maneres formals de descriure la seqüència (algorisme) d'accions sobre nombres? Hi ha, i en abundància, s'anomenen llenguatges de programació. En lloc de les anotacions verbals, utilitzarem programes (per exemple, en Python) que mostren els números requerits. Per exemple, per a cinc nou el programa és adequat print("9"*5). Continuarem interessats en el programa més curt per a un nombre determinat. La durada d'aquest programa s'anomena nombres; és el límit teòric al qual es pot comprimir un nombre determinat.
En lloc de la paradoxa de Berry, ara podem considerar-ne una de semblant: Quin és el nombre més petit que un programa de kilobytes no és suficient per produir?
Raonarem de la mateixa manera que abans: hi ha textos de 2561024 kilobytes, la qual cosa significa que els programes de kilobytes no poden sortir més de 2561024 números. Això vol dir que no es pot derivar d'aquesta manera un nombre determinat no superior a 2561024.
Però anem a escriure un programa en Python que generi tots els textos possibles en kilobytes, els executi per a l'execució i, si produeixen un número, afegeix aquest número al diccionari dels accessibles. Després de comprovar les 2561024 possibilitats, per molt que trigui, el programa cerca el nombre més petit que falta al diccionari i imprimeix aquest número. Sembla obvi que un programa d'aquest tipus s'adaptarà a un kilobyte de codi, i sortirà el mateix nombre que un programa de kilobytes no pot sortir!
Quina és la trampa ara? Ja no es pot atribuir a la informalitat de la notació!
Si esteu confós pel fet que el nostre programa necessitarà una quantitat astronòmica de memòria per funcionar, un diccionari (o matriu de bits) de 2561024 elements, podeu fer el mateix sense ell: per a cadascun dels 2561024 números, al seu torn , passeu per tots els 2561024 programes possibles, fins que no n'hi hagi cap adequat. No importa que aquesta recerca duri molt de temps: després de comprovar menys de (2561024)2 parells del número i del programa, acabarà i trobarà aquest número molt estimat.
O no acabarà? Efectivament, entre tots els programes que es provaran, n'hi haurà while True: pass (i els seus anàlegs funcionals) - i l'assumpte no anirà més enllà de provar aquest programa!
A diferència de la paradoxa de Berry, on la trampa estava en la informalitat de la notació, en el segon cas tenim una reformulació ben dissimulada. . El fet és que és impossible determinar la seva sortida d'un programa en un temps finit. En particular, Kolmogorov complexitat : no hi ha cap algorisme que permeti, per a un nombre determinat, trobar la durada del programa més curt que imprimeix aquest número; el que significa que no hi ha solució al problema de Berry: trobar la longitud de la designació verbal més curta per a un nombre determinat.
Font: www.habr.com