O problema da compresión de datos, na súa forma máis sinxela, pode relacionarse cos números e as súas notacións. Os números pódense indicar con números ("once" para o número 11), expresións matemáticas ("dous no vixésimo" para 1048576), expresións de cadea ("cinco nove" para 99999), nomes propios ("número da besta" para 666, "ano da morte de Turing" para 1954), ou combinacións arbitrarias dos mesmos. Calquera designación é adecuada pola cal o interlocutor poida determinar claramente de que número estamos a falar. Obviamente, dille ao seu interlocutor "factorial de oito" máis eficiente que a notación equivalente "corenta mil trescentos vinte". Aquí xorde unha pregunta lóxica: cal é a notación máis curta para un determinado número?
O filósofo Bertrand Russell publicou en 1908 , que toca o tema da notación numérica do lado oposto: Cal é o número máis pequeno que non require oitenta letras?
Tal número debe existir: a partir de oitenta letras e espazos rusos só podes facer 3480 designacións, o que significa que usando oitenta letras non podes designar máis de 3480 números. Isto significa que é imposible designar un determinado número non superior a 3480 deste xeito.
Isto significa que este número corresponderá á designación "o número máis pequeno para o que non son suficientes oitenta letras", que só ten 78 letras! Por unha banda, este número debe existir; en cambio, se existe este número, non lle corresponde a súa designación. Paradoxo!
O xeito máis sinxelo de descartar este paradoxo é referirse á informalidade das notacións verbais. Como, se só se permitise un conxunto de expresións especificamente definidas na notación, entón "o número máis pequeno para o que non son suficientes oitenta letras" non sería unha notación válida, mentres que as notacións practicamente útiles como "factorial de oito" seguiría sendo aceptable.
Existen formas formais de describir a secuencia (algoritmo) de accións sobre números? Hai, e en abundancia, chámanse linguaxes de programación. En lugar de notacións verbais, utilizaremos programas (por exemplo, en Python) que amosan os números necesarios. Por exemplo, para cinco nove o programa é axeitado print("9"*5). Seguiremos interesados no programa máis curto para un determinado número. A duración deste programa chámase números; é o límite teórico ao que se pode comprimir un determinado número.
En lugar do paradoxo de Berry, agora podemos considerar outro semellante: Cal é o número máis pequeno que un programa de kilobytes non é suficiente para emitir?
Razoaremos do mesmo xeito que antes: hai textos de 2561024 kilobytes, o que significa que os programas de kilobytes non poden saír máis de 2561024 números. Isto significa que un determinado número non superior a 2561024 non se pode derivar deste xeito.
Pero imos escribir un programa en Python que xere todos os textos posibles en kilobytes, execútaos para a súa execución e, se saen un número, engade este número ao dicionario dos accesibles. Despois de comprobar as 2561024 posibilidades, por moito que tarde, o programa busca o número máis pequeno que falta no dicionario e imprime ese número. Parece obvio que un programa deste tipo encaixará nun kilobyte de código, e sairá o mesmo número que un programa de kilobytes non pode emitir.
Cal é a trampa agora? Xa non se pode atribuír á informalidade da notación!
Se estás confundido polo feito de que o noso programa necesitará unha cantidade astronómica de memoria para funcionar, un dicionario (ou matriz de bits) de 2561024 elementos, podes facer o mesmo sen el: para cada un dos 2561024 números, á súa vez , percorre todos os 2561024 programas posibles, ata que non haxa ningún axeitado. Non importa que esa busca dure moito tempo: despois de comprobar menos de (2561024)2 pares do número e do programa, rematará e atopará ese número moi prezado.
Ou non rematará? Efectivamente, entre todos os programas que se probarán, haberá while True: pass (e os seus análogos funcionais) - e o asunto non irá máis aló de probar un programa deste tipo!
A diferenza do paradoxo de Berry, onde a captura estaba na informalidade da notación, no segundo caso temos unha reformulación ben disimulada. . O feito é que é imposible determinar a súa saída dun programa nun tempo finito. En particular, Kolmogorov complexidade : non existe un algoritmo que permita, para un número determinado, atopar a lonxitude do programa máis curto que imprime este número; o que significa que non hai solución ao problema de Berry: atopar a lonxitude da designación verbal máis curta para un número determinado.
Fonte: www.habr.com