Úloha kompresie dát v najjednoduchšej forme môže súvisieť s číslami a ich označeniami. Čísla možno označovať číslovkami ("jedenásť" pre číslo 11), matematickými výrazmi ("dva na dvadsiatej" pre 1048576), reťazcovými výrazmi ("päť deviatok" pre 99999), vlastnými menami ("číslo šelmy" pre 666, "rok smrti Turinga" pre 1954), alebo ľubovoľnými ich kombináciami. Platí akékoľvek označenie, podľa ktorého bude môcť partner jednoznačne určiť, o akom čísle je reč. Je očividné, že oznámiť partnerovi "faktoriál ôsmich" je efektívnejšie než ekvivalentné označenie "štyridsať tisíc tridsať". Tu vzniká logická otázka: aké označenie pre dané číslo je najkratšie?
Filozof Bertrand Russell v roku 1908 publikoval , ktorý sa zaoberá otázkou označení čísel z opačnej strany: aké je najmenšie číslo, pre ktorého označenie nestačí osemdesiat písmen?
Také číslo musí existovať: z osemdesiatich ruských písmen a medzier možno vytvoriť len 3480 označení, takže pomocou osemdesiatich písmen možno označiť najviac 3480 čísel. To znamená, že nejaké číslo, ktoré nie je väčšie než 3480, možno takto označiť nemožno.
To znamená, že tomuto číslu bude zodpovedať označenie "najmenšie číslo, pre označenie ktorého nestačí osemdesiat písmen", v ktorom je len 78 písmen! Na jednej strane, toto číslo určite musí existovať; na druhej strane, ak toto číslo existuje, tak jeho označenie mu nezodpovedá. Paradox!
Najjednoduchší spôsob, ako sa zbaviť tohto paradoxu, je odkázanie na neformálnosť slovných označení. Akoby, keby v označeniach bolo povolené len konkrétne definované množstvo výrazov, potom "najmenšie číslo, pre označenie ktorého nestačí osemdesiat písmen" by nebolo prípustným označením, zatiaľ čo prakticky užitočné označenia typu "faktoriál ôsmich" by zostali prípustnými.
Existujú formálne spôsoby opisu sekvencie (algoritmu) akcií nad číslami? Áno, a hojne — volajú sa programovacie jazyky. Budeme namiesto slovných označení používať programy (napríklad v Pythone), ktoré vypisujú potrebné čísla. Napríklad, pre päť deviatok sa hodí program print("9"*5). Naďalej sa budeme zaujímať o najkratší program pre dané číslo. Dĺžku takého programu nazývame čísla; to je teoretická hranica, do ktorej sa dané číslo dá skomprimovať.
Namiesto Berrovho paradoxu môžeme teraz zvážiť podobné: aké je najmenšie číslo, na jehož výstup nestačí kilobajtový program?
Rovnice budeme zvažovať rovnako ako predtým: existuje 2561024 kilobajtových textov, teda pomocou kilobajtových programov nie je možné získať viac než 2561024 čísel. Znamená to, že nejaké číslo, ktoré nie je väčšie ako 2561024, nemožno takto získať.
Ale napíšeme program v Pythone, ktorý generuje všetky možné kilobajtové texty, vykonáva ich a ak poskytnú nejaké číslo – pridá toto číslo do slovníka dosiahnuteľných. Po kontrole všetkých 2561024 možností, akokoľvek dlho to potrvá – program hľadá najmenšie číslo, ktoré chýba v slovníku, a to číslo vypíše. Zdá sa, že taký program sa zmestí do kilobajtu kódu – a vypíše to známe číslo, ktoré nemožno získať kilobajtovým programom!
Kde je teda háčik teraz? Na neformálnosť označení sa už nemožno odvolávať!
Ak vás trápi, že náš program bude vyžadovať astronomické množstvo pamäte na prácu – slovník (alebo bitové pole) 2561024 prvkov – môžeme to všetko uskutočniť aj bez neho: pre každé z 2561024 čísel po jednom prehľadávať všetky 2561024 možné programy, kým nenájdeme vhodný. Nie je dôležité, že taký prehľad bude trvať veľmi dlho: po kontrole menej ako (2561024)2 párov číslo a program sa to predsa skončí a nájde to slávne číslo.
Ale skončí? Veď medzi všetkými programami, ktoré budú vyskúšané, sa objaví while True: pass (a jej funkčné analógy) – a ďalej overovanie takéhoto programu už nepôjde!
Na rozdiel od Berrovho paradoxu, kde bol háčik v neformálnosti označení, v druhom prípade máme dobre zamaskovanú reformuláciu . Faktom je, že podľa programu nemožno za konečný čas určiť jeho výstup. Osobitne, kolmogorovská zložitost : neexistuje žiaden algoritmus, ktorý by umožnil pre dané číslo nájsť dĺžku najkratšieho programu, ktorý toto číslo vypisuje; a teda, neexistuje ani riešenie pre úlohu Berry — nájsť pre dané číslo dĺžku najkratšieho slovného označenia.
Zdroj: habr.com
