Het probleem van datacompressie, in zijn eenvoudigste vorm, kan betrekking hebben op getallen en hun notaties. Getallen kunnen worden aangegeven met cijfers ("elf" voor het getal 11), wiskundige uitdrukkingen ("twee in de twintigste" voor 1048576), tekenreeksexpressies ("vijf negens" voor 99999), eigennamen ("nummer van het beest" voor 666, "jaar van Turing's dood" voor 1954), of willekeurige combinaties daarvan. Elke aanduiding is geschikt waarmee de gesprekspartner duidelijk kan bepalen over welk nummer we het hebben. Vertel dit uiteraard aan uw gesprekspartner "Faculteit van acht" efficiënter dan gelijkwaardige notatie "veertigduizend driehonderdtwintig". Hier rijst een logische vraag: wat is de kortste notatie voor een bepaald getal?
De filosoof Bertrand Russell publiceerde in 1908 , dat de kwestie van getalnotatie van de andere kant raakt: Wat is het kleinste getal waarvoor geen tachtig letters nodig zijn?
Zo'n nummer moet bestaan: uit tachtig Russische letters en spaties kun je slechts 3480 aanduidingen verzinnen, wat betekent dat je met tachtig letters niet meer dan 3480 cijfers kunt aanduiden. Dit betekent dat het onmogelijk is om op deze manier een bepaald aantal van maximaal 3480 aan te duiden.
Dit betekent dat dit nummer overeenkomt met de aanduiding "het kleinste getal waarvoor tachtig letters niet genoeg zijn", die slechts 78 letters heeft! Enerzijds moet dit aantal bestaan; aan de andere kant, als dit nummer bestaat, komt de aanduiding er niet mee overeen. Paradox!
De eenvoudigste manier om deze paradox te verwerpen is door te verwijzen naar de informaliteit van verbale notaties. Als er bijvoorbeeld maar een specifiek gedefinieerde reeks uitdrukkingen in de notatie zou zijn toegestaan "het kleinste getal waarvoor tachtig letters niet genoeg zijn" zou geen geldige notatie zijn, terwijl praktisch bruikbare notaties zoals "Faculteit van acht" aanvaardbaar zou blijven.
Zijn er formele manieren om de volgorde (algoritme) van acties op getallen te beschrijven? Die zijn er, en in overvloed, ze worden programmeertalen genoemd. In plaats van verbale notaties zullen we programma's gebruiken (bijvoorbeeld in Python) die de vereiste getallen weergeven. Voor vijf negens is het programma bijvoorbeeld geschikt print("9"*5). Wij blijven geïnteresseerd in het kortste programma voor een bepaald aantal. De lengte van zo’n programma wordt genoemd cijfers; het is de theoretische limiet waartoe een bepaald getal kan worden gecomprimeerd.
In plaats van de paradox van Berry kunnen we nu een soortgelijke paradox overwegen: Wat is het kleinste getal waarvoor een kilobyteprogramma niet voldoende is om uit te voeren?
We zullen op dezelfde manier redeneren als voorheen: er zijn 2561024 kilobyte-teksten, wat betekent dat er niet meer dan 2561024 nummers kunnen worden uitgevoerd door kilobyte-programma's. Dit betekent dat een bepaald getal niet groter dan 2561024 op deze manier niet kan worden afgeleid.
Maar laten we een programma in Python schrijven dat alle mogelijke kilobyte-teksten genereert, deze uitvoert voor uitvoering, en als ze een getal uitvoeren, dit getal vervolgens toevoegt aan het woordenboek van bereikbare teksten. Na het controleren van alle 2561024 mogelijkheden, ongeacht hoe lang het duurt, zoekt het programma naar het kleinste getal dat ontbreekt in het woordenboek en drukt dat getal af. Het lijkt voor de hand liggend dat zo'n programma in een kilobyte code past - en precies dat getal zal uitvoeren dat niet door een kilobyteprogramma kan worden uitgevoerd!
Wat is nu het addertje onder het gras? Het kan niet langer worden toegeschreven aan de informaliteit van de notatie!
Als je in de war bent door het feit dat ons programma een astronomische hoeveelheid geheugen nodig heeft om te werken - een woordenboek (of bitarray) van 2561024 elementen - dan kun je hetzelfde doen zonder: voor elk van de 2561024 getallen, op zijn beurt Doorloop alle 2561024 mogelijke programma's, totdat er geen geschikt programma meer is. Het maakt niet uit dat zo'n zoektocht heel lang zal duren: na het controleren van minder dan (2561024) 2 paren van het nummer en het programma, zal het eindigen en dat zeer gekoesterde nummer vinden.
Of zal het niet eindigen? Van alle programma's die zullen worden uitgeprobeerd, zal er inderdaad een zijn while True: pass (en zijn functionele analogen) - en de zaak zal niet verder gaan dan het testen van zo'n programma!
In tegenstelling tot de paradox van Berry, waarbij het addertje onder het gras zat in de informaliteit van de notatie, hebben we in het tweede geval een goed verhulde herformulering . Het is een feit dat het onmogelijk is om de uitvoer ervan uit een programma in een eindige tijd te bepalen. In het bijzonder de complexiteit van Kolmogorov : er is geen algoritme dat voor een bepaald getal de lengte kan vinden van het kortste programma dat dit getal afdrukt; wat betekent dat er geen oplossing is voor het probleem van Berry: het vinden van de lengte van de kortste verbale aanduiding voor een bepaald getal.
Bron: www.habr.com