La tarea de compresión de datos en su forma más simple puede relacionarse con los números y su notación. Los números se pueden denotar por 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 (
"el número de la bestia" para 666,
"el año de la muerte de Turing" " Para 1954), o sus combinaciones arbitrarias. Cualquier designación mediante la cual el interlocutor puede determinar inequívocamente qué tipo de discurso es adecuado es adecuado. Obviamente, informar al interlocutor de
"factorial ocho" es más efectivo que la designación equivalente
"cuarenta mil trescientos veinte" . Esto plantea la pregunta lógica: ¿cuál es la designación más corta para un número dado?
El filósofo Bertrand Russell en 1908 publicó la
"Paradoja de Berry", que aborda el tema de la notación de números en el lado opuesto:
¿cuál es el número más pequeño para indicar qué ochenta letras no son suficientes?Tal número debe existir: de ochenta letras y espacios rusos puede hacer un total de 34
80 designaciones, lo que significa que usando ochenta letras puede designar no más de 34
80 números. Por lo tanto, un cierto número, no más de 34
80 , no puede designarse de esta manera.
¡Esto significa que la designación
“el número más pequeño para el que ochenta letras no son suficientes” corresponderá a este número, en el que solo hay 78 letras! Por un lado, este número debe existir; por otro lado, si este número existe, entonces su designación no le corresponde. Paradoja!
La forma más fácil de descartar esta paradoja es referirse a la informalidad de las designaciones verbales. Por ejemplo, si solo se permitiera un conjunto específico de expresiones en la notación, entonces
"el número más pequeño para el que ochenta letras no
son suficientes" no sería una designación válida, mientras que las designaciones prácticamente útiles del tipo
"factorial ocho" seguirían siendo válidas.
¿Hay formas formales de describir la secuencia (algoritmo) de acciones en números? Hay, y en abundancia, se llaman lenguajes de programación. En lugar de la notación verbal, usaremos programas (por ejemplo, en Python) que imprimen los números necesarios. Por ejemplo, para cinco nueves, el programa de
print("9"*5) adecuado. Seguiremos interesados en el programa más corto para un número determinado. La longitud de dicho programa se llama la
complejidad Kolmogorov del número; Este es el límite teórico al que se puede comprimir un número dado.
En lugar de la paradoja de Berry, ahora se puede considerar una similar:
¿cuál es el número más pequeño para el que un programa de kilobytes no es suficiente?Argumentaremos de la misma manera que antes: hay
256,1024 kilobytes de texto, lo que significa que no se pueden mostrar más de
256,224 números en programas de kilobytes. Esto significa que un cierto número, no mayor que 256
1024 , no puede deducirse de esta manera.
Pero escribimos en Python un programa que genera todos los textos de kilobytes posibles, los lanza para su ejecución y, si imprimen un cierto número, agrega este número al diccionario alcanzable. Después de verificar todas las posibilidades de 256
1024 , no importa cuánto tiempo tome: el programa busca el número más pequeño que no está en el diccionario y muestra este número. Parece obvio que dicho programa cabe en un kilobyte de código, ¡y generará el mismo número que no se puede mostrar en un programa de kilobyte!
¿Cuál es el truco ahora? ¡Ya no se puede atribuir a la informalidad de la notación!
Si está confundido de que nuestro programa requerirá una cantidad astronómica de memoria para funcionar (un diccionario (o mapa de bits) de 256
1024 elementos), puede hacer lo mismo sin él: para cada uno de los 256
1024 números, repita los 256
1024 posibles programas hasta encontrar uno adecuado. No importa que tal enumeración dure mucho tiempo: después de marcar menos de (256
1024 )
2 pares del número y el programa, finalizará y encontrará ese número muy preciado.
¿O no terminará? De hecho, entre todos los programas que se probarán, habrá
while True: pass (y sus contrapartes funcionales), ¡y las cosas no irán más allá de verificar dicho programa!
A diferencia de la paradoja de Berry, donde la captura estaba en la informalidad de la notación, en el segundo caso tenemos una reformulación bien encubierta del
"problema de detención" . El hecho es que, según el programa, es imposible determinar su conclusión en un tiempo finito. En particular, la complejidad de Kolmogorov no es
computable : no existe un algoritmo que permita que un número determinado encuentre la longitud del programa más corto que genera este número; lo que significa que no hay solución para el problema de Berry: encontrar para un número determinado la longitud de la designación de palabra más corta.