O problema da compressão de dados, na sua forma mais simples, pode estar relacionado com números e suas notações. Os números podem ser denotados por numerais ("onze" para o número 11), expressões matemáticas ("dois no vigésimo" para 1048576), expressões de string ("cinco noves" para 99999), nomes próprios ("número da besta" para 666, "ano da morte de Turing" para 1954), ou combinações arbitrárias dos mesmos. É adequada qualquer designação pela qual o interlocutor possa determinar claramente de que número estamos falando. Obviamente, diga ao seu interlocutor "fatorial de oito" mais eficiente que a notação equivalente "quarenta mil trezentos e vinte". Surge aqui uma questão lógica: qual é a notação mais curta para um determinado número?
O filósofo Bertrand Russell publicou em 1908 , que aborda a questão da notação numérica do lado oposto: Qual é o menor número que não requer oitenta letras?
Esse número deve existir: de oitenta letras e espaços russos, você pode formar apenas 3480 designações, o que significa que usando oitenta letras você não pode designar mais do que 3480 números. Isso significa que é impossível designar um determinado número não superior a 3480 dessa forma.
Isso significa que este número corresponderá à designação "o menor número para o qual oitenta letras não são suficientes", que tem apenas 78 letras! Por um lado, este número deve existir; por outro lado, se este número existir, então a sua designação não lhe corresponde. Paradoxo!
A maneira mais fácil de descartar este paradoxo é referir-se à informalidade das notações verbais. Tipo, se apenas um conjunto especificamente definido de expressões fosse permitido na notação, então "o menor número para o qual oitenta letras não são suficientes" não seria uma notação válida, enquanto notações praticamente úteis como "fatorial de oito" permaneceria aceitável.
Existem maneiras formais de descrever a sequência (algoritmo) de ações em números? Existem, e em abundância - são chamadas de linguagens de programação. Em vez de notações verbais, usaremos programas (por exemplo, em Python) que exibem os números necessários. Por exemplo, para cinco noves o programa é adequado print("9"*5). Continuaremos interessados no programa mais curto para um determinado número. A duração de tal programa é chamada números; é o limite teórico até o qual um determinado número pode ser comprimido.
Em vez do paradoxo de Berry, podemos agora considerar um semelhante: Qual é o menor número que um programa de kilobytes não é suficiente para gerar?
Raciocinaremos da mesma forma que antes: existem 2561024 textos de kilobytes, o que significa que não mais do que 2561024 números podem ser gerados por programas de kilobytes. Isto significa que um certo número não superior a 2561024 não pode ser derivado desta forma.
Mas vamos escrever um programa em Python que gere todos os textos de kilobytes possíveis, execute-os para execução e, se eles gerarem um número, adicione esse número ao dicionário de textos alcançáveis. Depois de verificar todas as 2561024 possibilidades, não importa quanto tempo demore, o programa procura o menor número que falta no dicionário e imprime esse número. Parece óbvio que tal programa caberá em um quilobyte de código - e produzirá exatamente o número que não pode ser gerado por um programa de quilobyte!
Qual é o problema agora? Não pode mais ser atribuído à informalidade da notação!
Se você está confuso com o fato de que nosso programa exigirá uma quantidade astronômica de memória para funcionar - um dicionário (ou matriz de bits) de 2561024 elementos - então você pode fazer a mesma coisa sem ele: para cada um dos 2561024 números, por sua vez , percorra todos os 2561024 programas possíveis, até que não haja nenhum adequado. Não importa que tal pesquisa dure muito tempo: depois de verificar menos de (2561024)2 pares do número e do programa, ela terminará e encontrará aquele número tão querido.
Ou não terminará? Na verdade, entre todos os programas que serão testados, haverá while True: pass (e seus análogos funcionais) - e o assunto não irá além de testar tal programa!
Ao contrário do paradoxo de Berry, onde o problema estava na informalidade da notação, no segundo caso temos uma reformulação bem disfarçada . O fato é que é impossível determinar a saída de um programa em um tempo finito. Em particular, a complexidade de Kolmogorov : não existe um algoritmo que permita, para um determinado número, encontrar o comprimento do programa mais curto que imprime esse número; o que significa que não há solução para o problema de Berry - encontrar o comprimento da designação verbal mais curta para um determinado número.
Fonte: habr.com