A tarefa de compressão de dados em sua forma mais simples pode se referir a números e suas denominações. Números podem ser representados por numerais («onze» para o número 11), expressões matemáticas («dois à vigésima» 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 delas. Qualquer denominação que permita ao interlocutor identificar claramente de qual número se trata é válida. É evidente que comunicar ao interlocutor «fatorial de oito» é mais eficaz do que a denominação equivalente «quarenta mil trezentos e vinte». Surge, então, uma questão lógica: qual é a denominação mais curta para um determinado número?
O filósofo Bertrand Russell publicou em 1908 o , que aborda a questão das denominações de números sob outra perspectiva: qual é o menor número para o qual não há denominação suficiente utilizando oitenta letras? Esse número deve existir: com oitenta letras russas e espaços, é possível formar apenas 3480 denominações, portanto, usando oitenta letras, não é possível denominar mais de 3480 números. Assim, existe um número que não pode ser representado dessa forma e é igual ou inferior a 3480.
Portanto, para esse número será correspondente a denominação
«o menor número para o qual não há denominação suficiente utilizando oitenta letras» , na qual há apenas 78 letras! Por um lado, esse número deve existir; por outro, se esse número existir, sua representação não corresponde a ele. Um paradoxo!, onde existem apenas 78 letras! Por um lado, esse número deve existir; por outro, se esse número existe, sua representação não corresponde a ele. Um paradoxo!
A maneira mais simples de ignorar esse paradoxo é referir-se à informalidade das denominações verbais. Ora, se apenas um conjunto especificamente definido de expressões fosse permitido nas denominações, então , na qual há apenas 78 letras! Por um lado, esse número deve existir; por outro, se esse número existir, sua representação não corresponde a ele. Um paradoxo! não seria uma denominação aceitável, enquanto denominações praticamente úteis, como «fatorial de oito» permaneceriam aceitáveis.
Existem maneiras formais de descrever a sequência (algoritmo) de ações sobre números? Existem, e em abundância — elas são chamadas de linguagens de programação. Vamos usar programas (por exemplo, em Python) em vez de denominações verbais para gerar os números desejados. Por exemplo, para cinco noves, o programa adequado seria print("9"*5). Continuaremos a nos interessar pelo programa mais curto para um número dado. O comprimento de tal programa é chamado de do número; esse é o limite teórico até onde um número dado pode ser comprimido.
Em vez do paradoxo de Berry, agora podemos considerar um análogo: qual é o menor número para o qual não é suficiente um programa de um kilobyte para ser gerado?
Vamos raciocinar da mesma forma que antes: existem 2561024 textos de um kilobyte, portanto, programas de um kilobyte podem gerar no máximo 2561024 números. Assim, algum número, não maior que 2561024, não pode ser gerado por esse método.
Mas vamos escrever um programa em Python que gera todos os textos possíveis de um kilobyte, os executa e, se eles geram algum número — adiciona esse número ao dicionário de alcançáveis. Depois de verificar todas as 2561024 possibilidades, quanto tempo isso levar, o programa busca qual é o menor número ausente no dicionário e o exibe. Parece evidente que tal programa se encaixaria em um kilobyte de código — e geraria aquele número que não pode ser gerado por um programa de um kilobyte!
Qual é, então, a pegadinha agora? Não pode mais ser atribuído à informalidade das denominações!
Se você está preocupado que nosso programa exigirá uma quantidade astronômica de memória para funcionar — um dicionário (ou array de bits) com 2561024 elementos — tudo isso pode ser feito sem ele: para cada um dos 2561024 números, devemos testar todas as 2561024 possíveis programas, até encontrar o certo. Não importa que essa busca dure muito tempo: depois de testar menos de (2561024)2 pares de número e programa, ela terminará, encontrando aquele número tão desejado.
Ou não irá terminar? Afinal, entre todos os programas que serão testados, aparecerá while True: pass e seus equivalentes funcionais — e então as verificações desse programa não irão mais adiante!
Diferente do paradoxo de Berry, onde o truque estava na informalidade das denominações, neste segundo caso temos uma reformulação bem disfarçada . A questão é que não é possível determinar a saída de um programa em tempo finito. Em particular, a complexidade de Kolmogorov : não existe nenhum algoritmo que permita, para um dado número, encontrar o comprimento do programa mais curto que gera esse número; portanto, não há solução para o problema de Berry — encontrar o comprimento da representação verbal mais curta para um número dado.
Fonte: habr.com
