Problém komprese dat se ve své nejjednodušší podobě může týkat čísel a jejich zápisů. Čísla mohou být označena číslicemi ("jedenáct" pro číslo 11), matematické výrazy ("dva ve dvacátém" pro 1048576), řetězcové výrazy ("pět devítek" pro 99999), vlastní jména ("číslo šelmy" za 666, "rok Turingovy smrti" pro rok 1954), nebo jejich libovolné kombinace. Vhodné je jakékoli označení, pomocí kterého může partner jasně určit, o jakém čísle mluvíme. Samozřejmě to řekněte svému partnerovi "faktor osmi" efektivnější než ekvivalentní zápis "čtyřicet tisíc třista dvacet". Nabízí se zde logická otázka: jaký je nejkratší zápis daného čísla?
Filozof Bertrand Russell publikoval v roce 1908 , který se dotýká problematiky zápisu čísel z opačné strany: Jaké je nejmenší číslo, které nevyžaduje osmdesát písmen?
Takové číslo musí existovat: z osmdesáti ruských písmen a mezer můžete vytvořit pouze 3480 označení, což znamená, že pomocí osmdesáti písmen můžete označit nejvýše 3480 čísel. To znamená, že tímto způsobem nelze určit určité číslo nejvýše 3480.
To znamená, že toto číslo bude odpovídat označení "nejmenší číslo, na které nestačí osmdesát písmen", která má pouze 78 písmen! Na jedné straně toto číslo musí existovat; na druhou stranu, pokud toto číslo existuje, pak mu jeho označení neodpovídá. Paradox!
Nejjednodušší způsob, jak tento paradox rozptýlit, je odkázat na neformálnost verbálních zápisů. Jako kdyby byla v zápisu povolena pouze specificky definovaná množina výrazů "nejmenší číslo, na které nestačí osmdesát písmen" by nebyl platný zápis, zatímco prakticky užitečné zápisy jako "faktor osmi" by zůstalo přijatelné.
Existují formální způsoby, jak popsat posloupnost (algoritmus) akcí na číslech? Existují a v hojné míře se jim říká programovací jazyky. Místo slovních zápisů použijeme programy (například v Pythonu), které zobrazí požadovaná čísla. Například pro pět devítek je program vhodný print("9"*5). Nadále nás bude zajímat nejkratší program pro daný počet. Délka takového programu se nazývá čísla; je to teoretická mez, na kterou lze dané číslo stlačit.
Místo Berryho paradoxu můžeme nyní uvažovat o podobném: Jaké je nejmenší číslo, které nestačí vypsat kilobajtový program?
Budeme uvažovat stejným způsobem jako dříve: existuje 2561024 kilobajtových textů, což znamená, že kilobajtovými programy nelze vytisknout více než 2561024 čísel. To znamená, že tímto způsobem nelze odvodit určité číslo, které není větší než 2561024.
Ale pojďme napsat program v Pythonu, který vygeneruje všechny možné kilobajtové texty, spustí je ke spuštění, a pokud vydají číslo, přidá toto číslo do slovníku dosažitelných. Po kontrole všech 2561024 XNUMX XNUMX možností, bez ohledu na to, jak dlouho to trvá, program vyhledá nejmenší číslo, které ve slovníku chybí, a toto číslo vypíše. Zdá se zřejmé, že takový program se vejde do kilobajtu kódu - a vypíše přesně to číslo, které nemůže být vydáno kilobajtovým programem!
V čem je teď háček? Už to nelze přičítat neformálnosti zápisu!
Pokud jste zmateni skutečností, že náš program bude vyžadovat astronomické množství paměti, aby fungoval - slovník (nebo bitové pole) 2561024 prvků - pak můžete udělat totéž bez něj: pro každé z 2561024 čísel postupně , projděte všech 2561024 možných programů, dokud nenajdete žádný vhodný. Nezáleží na tom, že takové hledání bude trvat velmi dlouho: po kontrole méně než (2561024)2 párů z čísla a programu skončí a najde to velmi oblíbené číslo.
Nebo to neskončí? Mezi všemi programy, které budou vyzkoušeny, skutečně bude while True: pass (a jeho funkční analogy) - a záležitost nepůjde dál než k testování takového programu!
Na rozdíl od Berryho paradoxu, kde byl háček v neformálnosti zápisu, máme v druhém případě dobře zamaskovanou reformulaci . Faktem je, že je nemožné určit jeho výstup z programu v konečném čase. Zejména složitost Kolmogorova : neexistuje žádný algoritmus, který by umožnil pro dané číslo najít délku nejkratšího programu, který toto číslo vytiskne; což znamená, že neexistuje žádné řešení Berryho problému - najít délku nejkratšího slovního označení pro dané číslo.
Zdroj: www.habr.com