A tarefa de compactação de dados em sua forma mais simples pode estar relacionada a números e sua notação. Os números podem ser indicados por números (
"onze" para o número 11), expressões matemáticas (
"dois no vigésimo" para 1048576), expressões de seqüência de caracteres (
"cinco noves" para 99999), nomes próprios (
"o número da besta" para 666,
"ano da morte de Turing") " Para 1954), ou suas combinações arbitrárias. Qualquer designação pela qual o interlocutor possa determinar inequivocamente que tipo de fala é adequada é adequada. Obviamente, informar o interlocutor do
“fatorial oito” é mais eficaz que a designação equivalente
“quarenta mil trezentos e vinte” . Isso levanta a questão lógica: qual é a designação mais curta para um determinado número?
O filósofo Bertrand Russell publicou em 1908 o
"Berry Paradox", que trata da questão da notação de números do lado oposto:
qual é o menor número para indicar que oitenta letras não são suficientes?Esse número deve existir: de oitenta letras e espaços russos, você pode fazer um total de 34
80 designações, o que significa que, usando oitenta letras, você pode designar não mais que 34
80 números. Portanto, um determinado número, não superior a 34
80 , não pode ser designado dessa maneira.
Isso significa que a designação
“o menor número para o qual oitenta letras não é suficiente” corresponderá a esse número, no qual existem apenas 78 letras! Por um lado, esse número deve existir; por outro lado, se esse número existir, sua designação não corresponde a ele. Paradoxo!
A maneira mais fácil de descartar esse paradoxo é se referir à informalidade das designações verbais. Por exemplo, se apenas um conjunto específico de expressões fosse permitido na notação,
“o menor número para o qual oitenta letras não
são suficientes” não seria uma designação válida, enquanto as designações praticamente úteis do tipo
“fatorial oito” permaneceriam válidas.
Existem maneiras formais de descrever a sequência (algoritmo) de ações em números? Existem, e em abundância - eles são chamados de linguagens de programação. Em vez de notação verbal, usaremos programas (por exemplo, em Python) que imprimem os números necessários. Por exemplo, durante cinco noves, o programa de
print("9"*5) adequado. Continuaremos interessados no programa mais curto para um determinado número. A duração desse programa é chamada de
complexidade do número de
Kolmogorov ; Esse é o limite teórico no qual um determinado número pode ser compactado.
Em vez do paradoxo de Berry, pode-se agora considerar um semelhante:
qual é o menor número para o qual um programa de kilobyte não é suficiente?Argumentaremos da mesma maneira que antes: existem
256.1024 textos de kilobytes, o que significa que não mais que
256.224 números podem ser exibidos em programas de kilobytes. Isso significa que um determinado número, não superior a 256
1024 , não pode ser deduzido dessa maneira.
Mas escrevemos no Python um programa que gera todos os textos possíveis de kilobytes, os lança para execução e, se eles imprimem um determinado número, adiciona esse número ao dicionário possível. Após verificar todas as 256
1024 possibilidades, não importa quanto tempo leve - o programa procura o menor número que não está no dicionário e exibe esse número. Parece óbvio que esse programa cabe em um kilobyte de código - e gera o número exato que não pode ser exibido em um programa de kilobyte!
Qual é o problema agora? Não pode mais ser atribuído à informalidade da notação!
Se você está confuso de que nosso programa exigirá uma quantidade astronômica de memória para funcionar - um dicionário (ou bitmap) de 256
1024 elementos - você poderá fazer o mesmo sem ele: para cada um dos 256
1024 números, repita todos os 256
1024 possíveis programas até encontrar um adequado. Não importa que essa enumeração dure muito tempo: depois de verificar menos de (256
1024 )
2 pares do número e do programa, ela terminará e encontrará esse número muito estimado.
Ou não vai acabar? De fato, entre todos os programas que serão tentados, haverá o
while True: pass (e seus equivalentes funcionais) - e as coisas não vão além da verificação de um programa assim!
Diferentemente do paradoxo de Berry, onde a captura estava na informalidade da notação, no segundo caso, temos uma reformulação bem disfarçada do
"problema de parada" . O fato é que, de acordo com o programa, é impossível determinar sua conclusão em um tempo finito. Em particular, a complexidade de Kolmogorov não é
computável : não existe um algoritmo que permita que um determinado número encontre a duração do programa mais curto que gera esse número; o que significa que não há solução para o problema de Berry - encontrar para um determinado número o comprimento da designação mais curta das palavras.