El problema de la compresión de datos, en su forma más simple, puede estar relacionado con los números y sus notaciones. Los números se pueden indicar mediante números ("once" para el número 11), expresiones matemáticas ("dos en el vigésimo" para 1048576), expresiones de cadena ("cinco nueves" para 99999), nombres propios ("Número de la bestia" por 666, "año de la muerte de Turing" para 1954), o combinaciones arbitrarias de los mismos. Cualquier designación es adecuada mediante la cual el interlocutor pueda determinar claramente de qué número estamos hablando. Obviamente, díselo a tu interlocutor. "factorial de ocho" más eficiente que la notación equivalente "cuarenta mil trescientos veinte". Aquí surge una pregunta lógica: ¿cuál es la notación más corta para un número dado?
El filósofo Bertrand Russell publicó en 1908. , que toca la cuestión de la notación numérica desde el lado opuesto: ¿Cuál es el número más pequeño que no requiere ochenta letras?
Tal número debe existir: de ochenta letras y espacios rusos solo se pueden formar 3480 designaciones, lo que significa que con ochenta letras no se pueden designar más de 3480 números. Esto significa que es imposible designar un número determinado de esta manera no más de 3480.
Esto significa que este número corresponderá a la designación. "el número más pequeño para el cual ochenta letras no son suficientes", que tiene sólo 78 letras! Por un lado, este número debe existir; en cambio, si este número existe, entonces su designación no le corresponde. ¡Paradoja!
La forma más fácil de descartar esta paradoja es hacer referencia a la informalidad de las notaciones verbales. Por ejemplo, si solo se permitiera un conjunto de expresiones específicamente definido en la notación, entonces "el número más pequeño para el cual ochenta letras no son suficientes" no sería una notación válida, mientras que notaciones prácticamente útiles como "factorial de ocho" seguiría siendo aceptable.
¿Existen formas formales de describir la secuencia (algoritmo) de acciones sobre números? Los hay, y en abundancia, se les llama lenguajes de programación. En lugar de notaciones verbales, usaremos programas (por ejemplo, en Python) que muestren los números requeridos. Por ejemplo, para cinco nueves el programa es adecuado. print("9"*5). Seguiremos interesados en el programa más corto para un número determinado. La duración de dicho programa se llama números; es el límite teórico al que se puede comprimir un número determinado.
En lugar de la paradoja de Berry, ahora podemos considerar una similar: ¿Cuál es el número más pequeño que un programa de kilobytes no puede generar?
Razonaremos de la misma manera que antes: hay 2561024 kilobytes de texto, lo que significa que los programas de kilobytes no pueden generar más de 2561024 números. Esto significa que no se puede derivar de esta manera un número determinado que no sea mayor que 2561024.
Pero escribamos un programa en Python que genere todos los textos en kilobytes posibles, los ejecute para su ejecución y, si generan un número, agregue este número al diccionario de los accesibles. Después de comprobar las 2561024 posibilidades, no importa cuánto tiempo lleve, el programa busca el número más pequeño que falta en el diccionario e imprime ese número. Parece obvio que un programa de este tipo cabe en un kilobyte de código y generará el mismo número que no puede generar un programa de kilobyte.
¿Cuál es el problema ahora? ¡Ya no se puede atribuir a la informalidad de la notación!
Si le confunde el hecho de que nuestro programa requerirá una cantidad astronómica de memoria para funcionar (un diccionario (o matriz de bits) de 2561024 elementos), puede hacer lo mismo sin él: para cada uno de los 2561024 números, por turno. , revise todos los 2561024 programas posibles, hasta que no encuentre ninguno adecuado. No importa que dicha búsqueda dure mucho tiempo: después de verificar menos de (2561024)2 pares del número y el programa, finalizará y encontrará ese número tan preciado.
¿O no terminará? De hecho, entre todos los programas que se probarán, habrá while True: pass (y sus análogos funcionales), ¡y el asunto no irá más allá de probar dicho programa!
A diferencia de la paradoja de Berry, donde el problema estaba en la informalidad de la notación, en el segundo caso tenemos una reformulación bien disimulada . El hecho es que es imposible determinar el resultado de un programa en un tiempo finito. En particular, la complejidad de Kolmogorov. : no existe ningún algoritmo que permita, para un número dado, encontrar la longitud del programa más corto que imprime este número; lo que significa que no hay solución al problema de Berry: encontrar la longitud de la designación verbal más corta para un número dado.
Fuente: habr.com