Problém kompresie údajov sa vo svojej najjednoduchšej forme môže týkať čísel a ich zápisov. Čísla môžu byť označené číslicami ("jedenásť" pre číslo 11), matematické výrazy ("dva v dvadsiatom" pre 1048576), reťazcové výrazy ("päť deviatok" pre 99999), vlastné mená ("číslo šelmy" za 666, "rok Turingovej smrti" za rok 1954) alebo ich ľubovoľné kombinácie. Vhodné je akékoľvek označenie, pomocou ktorého môže partner jasne určiť, o akom čísle hovoríme. Samozrejme, povedzte to svojmu partnerovi "faktor ôsmich" efektívnejšie ako ekvivalentná notácia "štyridsaťtisíc tristo dvadsať". Vzniká tu logická otázka: aký je najkratší zápis daného čísla?
Filozof Bertrand Russell publikoval v roku 1908 , ktorý sa dotýka problematiky zápisu čísel z opačnej strany: Aké je najmenšie číslo, ktoré nevyžaduje osemdesiat písmen?
Takéto číslo musí existovať: z osemdesiatich ruských písmen a medzier môžete vytvoriť iba 3480 označení, čo znamená, že pomocou osemdesiatich písmen nemôžete označiť viac ako 3480 čísel. To znamená, že týmto spôsobom nie je možné určiť určité číslo nie viac ako 3480.
To znamená, že toto číslo bude zodpovedať označeniu "najmenšie číslo, na ktoré osemdesiat písmen nestačí", ktorý má len 78 písmen! Na jednej strane toto číslo musí existovať; na druhej strane, ak toto číslo existuje, tak jeho označenie mu nezodpovedá. Paradox!
Najjednoduchší spôsob, ako tento paradox vyvrátiť, je odkázať na neformálnosť verbálnych zápisov. Ako keby bola v zápise povolená iba špecificky definovaná množina výrazov "najmenšie číslo, na ktoré osemdesiat písmen nestačí" by nebola platná notácia, zatiaľ čo prakticky užitočné notácie ako "faktor ôsmich" by zostalo prijateľné.
Existujú formálne spôsoby, ako opísať postupnosť (algoritmus) akcií na číslach? Existujú a v hojnom množstve - nazývajú sa programovacie jazyky. Namiesto verbálnych zápisov použijeme programy (napríklad v Pythone), ktoré zobrazia požadované čísla. Napríklad pre piatich deviatakov je program vhodný print("9"*5). Naďalej nás bude zaujímať najkratší program pre daný počet. Dĺžka takéhoto programu je tzv čísla; je to teoretická hranica, na ktorú je možné dané číslo stlačiť.
Namiesto Berryho paradoxu môžeme teraz uvažovať o podobnom: Aké najmenšie číslo nestačí na výstup kilobajtového programu?
Budeme uvažovať rovnakým spôsobom ako predtým: existuje 2561024 kilobajtových textov, čo znamená, že kilobajtovými programami nemožno vytlačiť viac ako 2561024 čísel. To znamená, že určité číslo nie väčšie ako 2561024 nemožno týmto spôsobom odvodiť.
Ale napíšme program v Pythone, ktorý vygeneruje všetky možné kilobajtové texty, spustí ich na vykonanie, a ak vydajú číslo, potom toto číslo pridá do slovníka dostupných. Po skontrolovaní všetkých 2561024 XNUMX XNUMX možností, bez ohľadu na to, ako dlho to trvá, program vyhľadá najmenšie číslo chýbajúce v slovníku a toto číslo vypíše. Zdá sa zrejmé, že takýto program sa zmestí do kilobajtu kódu - a vypíše práve to číslo, ktoré kilobajtový program vygenerovať nemôže!
V čom je teraz háčik? Nedá sa to už pripisovať neformálnosti zápisu!
Ak ste zmätení skutočnosťou, že náš program bude vyžadovať astronomické množstvo pamäte, aby fungoval - slovník (alebo bitové pole) 2561024 prvkov - potom môžete urobiť to isté bez neho: pre každé z 2561024 čísel postupne , prejdite všetkých 2561024 možných programov, kým nenájdete žiadny vhodný. Nezáleží na tom, že takéto vyhľadávanie bude trvať veľmi dlho: po skontrolovaní menej ako (2561024) 2 párov z čísla a programu sa skončí a nájde to veľmi obľúbené číslo.
Alebo to neskončí? Vskutku, medzi všetkými programami, ktoré sa budú skúšať, bude while True: pass (a jeho funkčné analógy) - a záležitosť nebude ďalej ako testovanie takéhoto programu!
Na rozdiel od Berryho paradoxu, kde bol háčik v neformálnosti zápisu, máme v druhom prípade dobre zamaskovanú preformuláciu . Faktom je, že je nemožné určiť jeho výstup z programu v konečnom čase. Najmä zložitosť Kolmogorova : neexistuje žiadny algoritmus, ktorý by umožňoval pre dané číslo nájsť dĺžku najkratšieho programu, ktorý toto číslo vypíše; čo znamená, že neexistuje riešenie Berryho problému - nájsť dĺžku najkratšieho slovného označenia pre dané číslo.
Zdroj: hab.com