La tarea de compresión de datos en su forma más simple puede referirse a números y sus designaciones. Los números pueden ser representados por numerales («once» para el número 11), expresiones matemáticas («dos a la veinte» para 1048576), expresiones en cadena («cinco nueves» para 99999), nombres propios («el número de la bestia» para 666, «el año de la muerte de Turing» para 1954), o combinaciones arbitrarias de estos. Cualquier designación que permita al interlocutor identificar de manera inequívoca de qué número se trata es válida. Es evidente que comunicar al interlocutor «el factorial de ocho» es más eficiente que la designación equivalente «cuarenta mil trescientos veinte». Surge la pregunta lógica: ¿cuál designación es la más corta para un número dado?
El filósofo Bertrand Russell publicó en 1908 , que aborda la cuestión de las designaciones de números desde el lado opuesto: ¿cuál es el número más pequeño para el cual no hay suficientes letras para su designación?
Tal número debe existir: de ochenta letras rusas y espacios se pueden formar solo 3480 designaciones, por lo que usando ochenta letras no se puede designar más de 3480 números. Por lo tanto, hay un número que no puede ser designado de esta manera, que es a lo sumo 3480.
Por lo tanto, a este número le corresponderá la designación «el número más pequeño para el cual no hay suficientes letras para su designación», que contiene solo 78 letras. ¡Por un lado, este número debe existir; por otro, si este número existe, entonces su designación no le corresponde. ¡Paradoja!
La manera más sencilla de deshacerse de esta paradoja es referirse a la informalidad de las designaciones verbales. Se diría que si solo se permitieran un conjunto específico de expresiones, entonces «el número más pequeño para el cual no hay suficientes letras para su designación» no sería una designación permisible, mientras que designaciones prácticamente útiles como «el factorial de ocho» seguirían siendo permisibles.
¿Existen formas formales de describir una secuencia (algoritmo) de acciones sobre números? Sí, y en abundancia: se denominan lenguajes de programación. En lugar de designaciones verbales, utilizaremos programas (por ejemplo, en Python) que generen los números necesarios. Por ejemplo, para cinco nueves se puede usar el programa print("9"*5). Seguiremos interesados en el programa más corto para un número dado. La longitud de dicho programa se llama del número; este es el límite teórico al que se puede comprimir un número dado.
En lugar del paradoja de Berry, ahora podemos considerar uno similar: ¿cuál es el número más pequeño que no puede ser producido por un programa de kilobyte?
Razonaremos de la misma manera que antes: existen 2561024 textos de kilobyte, lo que significa que con programas de kilobyte se pueden producir no más de 2561024 números. Por lo tanto, existe un número, no mayor que 2561024, que no se puede generar de esta manera.
Pero escribamos un programa en Python que genere todos los textos posibles de kilobyte, los ejecute, y si producen algún número, lo agregue al diccionario de alcanzables. Después de verificar todas las 2561024 posibilidades, por mucho tiempo que tome, el programa busca cuál es el número más pequeño que falta en el diccionario y lo imprime. Parece obvio que tal programa cabría en un kilobyte de código y produciría ese número que no se puede generar con programas de kilobyte.
¿Cuál es entonces el truco ahora? ¡No se puede atribuir esto a la informalidad de los términos!
Si te preocupa que nuestro programa requiera una cantidad astronómica de memoria para funcionar —un diccionario (o un array de bits) de 2561024 elementos— se puede hacer todo lo mismo sin ello: para cada uno de los 2561024 números, probar uno a uno todos los 2561024 programas posibles, hasta encontrar uno que funcione. No importa que tal esfuerzo dure mucho tiempo: tras comprobar menos de (2561024)2 pares de números y programas, el proceso terminará y encontrará ese número tan anhelado.
¿O no terminará? Después de todo, entre todos los programas que se probarán, se encontrará while True: pass y sus análogos funcionales —y ahí se detendrá cualquier verificación de dicho programa!
A diferencia de la paradoja de Berry, donde el truco estaba en la informalidad de los términos, en este segundo caso tenemos una reformulación bien disfrazada de El hecho es que no se puede determinar su salida en un tiempo finito. En particular, la complejidad de Kolmogorov : no hay ningún algoritmo que permita, para un número dado, encontrar la longitud del programa más corto que produzca ese número; por lo tanto, no hay solución para el problema de Berry: encontrar la longitud de la representación verbal más corta de un número dado.
Fuente: habr.com
