Predstavte si, že dostanete dva rôzne kódy. Prvý je len stokrát zopakovaná číslica 0, druhý je zdanlivo náhodná postupnosť číslic 1 a 0. Ktorý z nich je zložitejší, 000…000 alebo 001…110? Asi intuitívne tušíte, že ten druhý. Ako to však uchopiť matematicky?
O vhodnú definíciu sa postaral sovietsky matematik Andrej Nikolajevič Kolmogorov (1903 – 1987). Znie asi takto: zložitosť reťazca je úmerná najkratšiemu počítačovému programu, ktorý takýto reťazec dokáže vygenerovať. Kým prvý reťazec vytvoríte krátkym programom: napíš sto núl, ten druhý bude oveľa dlhší, napríklad: napíš 001…110.
Náhodnosť reťazcov
Poznať zložitosť reťazca je užitočné, dá sa tak šetriť miesto na disku. To je podstata kompresie súborov – veľmi dlhý reťazec jednotiek a núl, ktorý predstavuje napríklad fotografiu z dovolenky, počítač redukuje na kratší reťazec jednotiek a núl predstavujúci tú istú snímku. Využíva sa pritom štruktúra daných údajov, napríklad sa niektoré pixely opakujú, a tak stačí uložiť informáciu: toto zopakuj stokrát.
Zaujímavé je, že kolmogorovská zložitosť umožňuje definovať náhodnosť. Náhodný reťazec je taký, ktorý sa nedá skrátiť. V dokonale náhodnej postupnosti jednotiek a núl typicky nie je žiaden systém, ktorý by sa na zjednodušenie dal použiť. Má to však háčik – kolmogorovská zložitosť reťazca je vo všeobecnosti nespočítateľná.
Existuje k tomu pekný dôkaz. Keby sa dala spočítať, viedlo by to k paradoxným situáciám. Predstavte si napríklad najkratší reťazec, ktorý sa nedá opísať menej ako 60 znakmi. Môže existovať? Keby existoval, potom by ho takýto program dokázal opísať, čo je v spore s daným tvrdením. Keby mi niekto ukázal náhodnú postupnosť jednotiek a núl, neviem povedať, ako dokonale sa dá zredukovať.
Ťažko opísateľné štruktúry
Ako príklad uveďme tieto dva reťazce: 11, 00100 10000 11111 10110 10101 00010 00100 00101 10100 01100 00100 01101 00110 00100 11000 11001 10001 01000 10111 00000 a 11, 00100 10100 11111 10110 10101 00010 00100 00101 10100 01100 00100 01101 00110 00100 11000 11001 10001 01000 10111 00000.
Kým prvý sa dá napísať veľmi jednoducho ako π v binárnom zápise, pri tom druhom to nevieme. Zložitosť tohto reťazca vieme ohraničiť zhora, ak nájdeme predpis na jeho skrátenie, no nevieme povedať, či neexistuje ešte lepší predpis.
Ako to aplikovať na celý vesmír? Kým pri entropii vieme, že od počiatku vesmíru rastie, pri zložitosti je to zložitejšie. Zoberme si známy príklad s entropiou, keď premiešame kávu s mliekom, výsledný stav má väčšiu neusporiadanosť. Oba tieto stavy však majú nízku zložitosť. Prvý vieme opísať ako kávu a mlieko, druhý ako kávu s mliekom. Zložité je to uprostred, keď počas premiešavania v káve nachádzame rôzne víry a zložité, ťažko opísateľné štruktúry. Podobne bol vesmír jednoduchý na začiatku ako horúca homogénna plazma a bude jednoduchý na konci ako chladný prázdny priestor. Zložitosť v ňom existuje len teraz na pomedzí. Jednoduché, nie?
Samuel Kováčik
Fakulta matematiky, fyziky a informatiky
Univerzita Komenského v Bratislave
Viac podobných článkov nájdete na stránke vedator.space.
