De taak van gegevenscompressie kan in zijn eenvoudigste vorm betrekking hebben op getallen en hun aanduidingen. Getallen kunnen worden aangeduid met numerieke uitdrukkingen (âelfâ voor het getal 11), wiskundige uitdrukkingen (âtwee tot de twintigsteâ voor 1048576), stringuitdrukkingen (âvijf negensâ voor 99999), eigennamen (âhet getal van het beestâ voor 666, âhet jaar van de dood van Turingâ voor 1954), of willekeurige combinaties daarvan. Elk aanduiding is geschikt, mits de gesprekspartner duidelijk kan bepalen over welk getal het gaat. Het is duidelijk dat het efficiĂ«nter is om de gesprekspartner âde faculteit van achtâ te melden dan de equivalente aanduiding âveertig duizend driehonderd twintigâ. Hier rijst de logische vraag: wat is de kortste aanduiding voor een gegeven getal?
De filosoof Bertrand Russell publiceerde in 1908 de , die de kwestie van aanduidingen van getallen vanuit een andere kant aanraakt: wat is het kleinste getal waarvoor niet genoeg achtien letters zijn om het aan te duiden?
Zulk een getal moet bestaan: met de tachtig Russische letters en spaties kunnen in totaal slechts 3480 aanduidingen worden gemaakt, wat betekent dat met gebruik van tachtig letters niet meer dan 3480 getallen kunnen worden aangeduid. Dat betekent dat een bepaald getal, niet groter dan 3480, op deze manier niet kan worden aangeduid.
Dus moet er corresponderen met dit getal de aanduiding zijn âhet kleinste getal waarvoor niet genoeg tachtig letters zijn om het aan te duidenâ, waarin in totaal 78 letters zitten! Enerzijds moet dit getal bestaan; anderzijds, als dit getal bestaat, dan komt de aanduiding niet overeen met het getal. Paradox!
De eenvoudigste manier om deze paradox te negeren, is te verwijzen naar de informaliteit van verbale aanduidingen. Het idee is dat als in de aanduidingen slechts een specifieke set uitdrukkingen was toegestaan, dat âhet kleinste getal waarvoor niet genoeg tachtig letters zijn om het aan te duidenâ geen geldige aanduiding zou zijn, terwijl praktisch nuttige aanduidingen zoals âde faculteit van achtâ geldig zouden blijven.
Zijn er formele manieren om een reeks (algoritme) van handelingen met getallen te beschrijven? Ja, die zijn er volop â ze worden programmeertalen genoemd. Laten we in plaats van verbale aanduidingen programma's gebruiken (bijvoorbeeld in Python) die de benodigde getallen genereren. Bijvoorbeeld, voor vijf negens zou het programma werken 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 the Berry paradox, we can now consider a similar one: what is the smallest number for which there is not enough of a kilobyte program to output it?
We will reason as before: there are 2561024 kilobyte texts, which means that kilobyte programs can output no more than 2561024 numbers. This means that there is some number, not greater than 2561024, that cannot be outputted in this way.
But letâs write a Python program that generates all possible kilobyte texts, runs them, and if they output a number, it adds that number to a dictionary of achievable numbers. After checking all 2561024 possibilities, no matter how long it takes â the program searches for the smallest number that is absent from the dictionary and outputs that number. It seems obvious that such a program would fit in a kilobyte of code â and would output that very number which cannot be outputted by a kilobyte program!
So what is the catch now? It can no longer be blamed on the informality of the notation!
If you are worried that our program will require an astronomical amount of memory to run â a dictionary (or bit array) of 2561024 elements â then all the same can be accomplished without it: for each of the 2561024 numbers, we can sequentially check all 2561024 possible programs until a suitable one is found. It doesnât matter that such a search will take a very long time; after checking less than (2561024)2 pairs of number and program, it will indeed complete and find that coveted number.
Or will it not complete? After all, among all the programs that will be tried, we will encounter while True: pass (and its functional analogs) â and further checks of such a program will go nowhere!
Unlike the Berry paradox, where the catch lay in the informality of the notation, in the second case we have a well-masked reformulation of the . The point is that it is impossible to determine the output of a program within a finite timeframe. In particular, Kolmogorov complexity : er is geen algoritme dat het mogelijk maakt om voor een gegeven getal de lengte van het kortste programma te vinden dat dat getal uitvoert; daarom is er ook geen oplossing voor het Berry-probleem â om voor een gegeven getal de lengte van de kortste verbale notatie te vinden.
Bron: habr.com
