The task of data compression in its simplest form can relate to numbers and their representations. Numbers can be represented by numerals ("eleven" for the number 11), mathematical expressions ("two to the twentieth" for 1048576), string expressions ("five nines" for 99999), proper names ("the number of the beast" for 666, "the year of Turing's death" for 1954), or any arbitrary combinations of these. Any representation by which the interlocutor can unambiguously determine which number is being referred to is acceptable. Clearly, telling an interlocutor "the factorial of eight" is more effective than the equivalent representation "forty thousand three hundred twenty". This raises a logical question: what representation for a given number is the shortest?
Philosopher Bertrand Russell published in 1908 , which addresses the issue of number representations from the opposite side: what is the smallest number for which eighty letters are insufficient for representation?
Such a number must exist: with eighty Russian letters and spaces, only 3480 representations can be formed, meaning that using eighty letters, no more than 3480 numbers can be represented. Therefore, a certain number, no greater than 3480, cannot be represented in this way.
Thus, this number will correspond to the representation "the smallest number for which eighty letters are insufficient for representation", which contains only 78 letters! On one hand, this number must exist; on the other hand, if this number exists, then its representation is not adequate for it. A paradox!
The simplest way to brush off this paradox is to refer to the informality of verbal representations. It may be argued that if only a specifically defined set of expressions were allowed in representations, then "the smallest number for which eighty letters are insufficient for representation" it would not be an allowable representation, whereas practically useful representations like "the factorial of eight" would remain permissible.
Are there formal ways to describe a sequence (algorithm) of operations on numbers? Yes, and in abundance—they are called programming languages. Instead of verbal representations, we will use programs (for example, in Python) to output the necessary numbers. For instance, for five nines, the following program will do: print("9"*5)We will still be interested in the shortest program for a given number. The length of such a program is called of the number; this is the theoretical limit to which a given number can be compressed.
Instead of Berry's paradox, we can consider a similar one: what is the smallest number for which a kilobyte program is insufficient to output?
We will reason the same way as before: there are 2561024 kilobyte texts, so kilobyte programs can output no more than 2561024 numbers. Therefore, some number, not greater than 2561024, cannot be output in this way.
But let's write a Python program that generates all possible kilobyte texts, executes them, and if they output a number, it adds that number to the list of reachable numbers. After checking all 2561024 possibilities, no matter how long it takes, the program looks for the smallest number missing from the list and outputs that number. It seems obvious that such a program will fit within a kilobyte of code — and will output that very number that cannot be output by a kilobyte program!
So what's the catch now? It can't be attributed to the informality of the notation anymore!
If you're concerned that our program will require an astronomical amount of memory to operate — a dictionary (or bit array) of 2561024 elements — then all the same can be achieved without it: for each of the 2561024 numbers, we can sequentially check all 2561024 possible programs until we find a suitable one. It doesn't matter that such a search will take a very long time: after checking less than (2561024)² pairs of numbers and programs, it will indeed finish, and find that elusive number.
Or will it not finish? After all, among all the programs that will be tried, there will be while True: pass (and its functional analogs) — and further checking of such a program won't progress!
Unlike Berry's paradox, where the catch lay in the informality of the notation, in the second case we have a well-masked reformulation of the . The fact is, it's impossible to determine the output of a program in a finite amount of time. In particular, Kolmogorov complexity : there is no algorithm that allows finding the length of the shortest program that outputs a given number; therefore, there is no solution for Berry's problem either — to find the length of the shortest verbal representation for a given number.
Source: habr.com
