Úloha komprese dat v její nejjednodušší podobě může souviset s čísly a jejich označeními. Čísla lze označovat číslovkami („jedenáct“ pro číslo 11), matematickými výrazy („dva na dvacátou“ pro 1048576), řetězcovými výrazy („pět devítek“ pro 99999), vlastními jmény („číslo šelmy“ pro 666, „rok smrti Turinga“ pro 1954), nebo libovolnými jejich kombinacemi. Platí jakékoli označení, podle něhož může protistrana jednoznačně určit, o jakém čísle je řeč. Je jasné, že sdělit protistraně „faktoriál osmi“ je efektivnější než ekvivalentní označení „čtyřicet tisíc tři sta dvacet“. Zde vyvstává logická otázka: které označení pro dané číslo je nejkratší?
Filozof Bertrand Russell publikoval v roce 1908 , který se týká označování čísel z opačné strany: jaké je to nejmenší číslo, pro jehož označení není dostatek osmdesáti písmen?
Takové číslo musí existovat: z osmdesáti ruských písmen a mezer lze vytvořit jen 3480 označení, tedy při použití osmdesáti písmen lze označit maximálně 3480 čísel. To znamená, že nějaké číslo, které není větší než 3480, není možné tímto způsobem označit.
To znamená, že tomuto číslu bude odpovídat označení „nejmenší číslo, pro jehož označení není dostatek osmdesáti písmen“, ve kterém je celkem 78 písmen! Na jedné straně, toto číslo musí existovat; na druhé straně, pokud toto číslo existuje, pak mu neodpovídá jeho označení. Paradox!
Nejjednodušší způsob, jak se tohoto paradoxu zbavit, je odkázat na neformálnost slovních označení. Prý, pokud by byla v označeních povolena pouze konkrétně definovaná skupina výrazů, pak „nejmenší číslo, pro jehož označení není dostatek osmdesáti písmen“ by to nebylo přípustné označení, zatímco prakticky užitečná označení typu „faktoriál osmi“ by zůstala přípustná.
Existují formální způsoby popisu posloupnosti (algoritmu) činností s čísly? Ano, a v hojném počtu — nazývají se programovacími jazyky. Budeme místo slovních označení používat programy (například v Pythonu), které vygenerují potřebná čísla. Například pro pět devítek se hodí program print("9"*5). Budeme se opět zajímat o nejkratší program pro dané číslo. Délka takového programu se nazývá čísla; to je teoretická hranice, do které lze dané číslo stlačit.
Místo Berryho paradoxu nyní můžeme zvážit analogické: jaké je nejmenší číslo, pro jehož výstup není dostatečný kilobajtový program?
Budeme uvažovat stejně jako dříve: existuje 2561024 kilobajtových textů, což znamená, že kilobajtovými programy nelze vyprodukovat více než 2561024 čísel. To znamená, že nějaké číslo, které není větší než 2561024, nelze tímto způsobem vyprodukovat.
Ale napišeme program v Pythonu, který generuje všechny možné kilobajtové texty, spouští je a pokud některý z nich vyprodukuje nějaké číslo, přidá toto číslo do slovníku dosažitelných. Po kontrole všech 2561024 možností, bez ohledu na to, jak dlouho to zabere — program hledá, které nejmenší číslo chybí ve slovníku, a vyprodukuje toto číslo. Zdá se být zřejmé, že takový program se vejde do kilobajtu kódu — a vyprodukuje to číslo, které není možné vyprodukovat kilobajtovým programem!
Kde je tedy teď háček? Není možné to převést na neformálnost znaků!
Pokud vás zmátlo to, že náš program bude vyžadovat astronomické množství paměti pro práci — slovník (nebo bitové pole) o 2561024 elementech — pak lze to samé uskutečnit i bez něj: pro každé z 2561024 čísel postupně procházet všechny 2561024 možné programy, dokud nenajdeme ten pravý. Není důležité, že takový prohledávací proces potrvá velmi dlouho: po kontrole méně než (2561024)2 párů čísla a programu se přece jen ukončí a najde to tajné číslo.
Nebo se neukončí? Vždyť mezi všemi programy, které budou vyzkoušeny, se objeví while True: pass (a její funkční analogy) — a dál už s kontrolou takového programu ničemu nepomůžeme!
Na rozdíl od Berryho paradoxu, kde byl háček v neformálnosti znaků, v druhém případě máme dobře zamaskovanou přeformulaci . Fakt je ten, že není možné v konečném čase určit výstup programu. Zejména kolmogorovská složitost : neexistuje žádný algoritmus, který by umožnil najít délku nejkratšího programu, který toto číslo vytiskne; proto neexistuje ani řešení pro úlohu Berry — najít délku nejkratšího slovního vyjádření pro dané číslo.
Zdroj: habr.com
