Naloga kompresije podatkov v svoji najpreprostejši obliki se lahko nanaša na številke in njihove označbe. Številke je mogoče označevati s številčnimi vrednostmi („enajst“ za številko 11), matematičnimi izrazi („dva na dvajset“ za 1048576), niznimi izrazi („pet devetk“ za 99999), lastnimi imeni („število zveri“ za 666, „leto smrti Turinga“ za 1954), ali poljubnimi njih kombinacijami. Ustrezna je katera koli oznaka, s katero lahko sogovornik nedvoumno določi, o kateri številki govorimo. Očitno je, da je bolj učinkovito sporočiti sogovorniku „faktorial osem“ kot ekvivalentno oznako „štirideset tisoč trideset“. Tukaj se pojavi logično vprašanje: katera oznaka za dano številko je najkrajša?
Filozof Bertrand Russell je leta 1908 objavil , ki se dotika vprašanja označevanja števil z druge strani: katero je najmanjše število, za katerega ni dovolj osemdeset črk za njegovo označevanje?
Takšno število mora obstajati: iz osemdesetih ruskih črk in presledkov je mogoče sestaviti le 3480 oznak, kar pomeni, da je mogoče s pomočjo osemdesetih črk označiti največ 3480 števil. To pomeni, da nekega števila, ki ni večje od 3480, na ta način označiti ni mogoče.
To pomeni, da bo temu številu ustrezala oznaka „najmanjše število, za označevanje katerega ni dovolj osemdeset črk“, v kateri je skupaj 78 črk! Po eni strani mora to število obstajati; po drugi strani, če to število obstaja, njegova oznaka zanj ne ustreza. Paradoks!
Najenostavnejši način, da se odmaknemo od tega paradoksa, je, da se sklicujemo na neformalnost besednih označb. Pravi, da če bi v označbah bil dovoljen le konkretno določen nabor izrazov, potem „najmanjše število, za označevanje katerega ni dovolj osemdeset črk“ ne bi bilo dopustne oznake, medtem ko bi praktično uporabne oznake, kot so „faktorial osem“ ostale dopustne.
Ali obstajajo formalni načini opisovanja zaporedja (algoritma) dejanj nad številkami? Da, in v obilju — imenujejo se programski jeziki. Uporabimo lahko namesto besednih oznak programe (na primer v Pythonu), ki izpišejo želeno številko. Na primer, za pet devetk bo ustrezal program print("9"*5)Še vedno nas zanima najkrajši program za dano število. Dolžina takega programa se imenuje številke; to je teoretična meja, do katere je dano število mogoče stisniti.
Namesto Berryjevega paradoksa lahko razmislimo o podobnem: katero je najmanjše število, za katerega ni dovolj kilobajtnega programa?
Razmišljali bomo tako kot prej: obstaja 2561024 kilobajtnih besedil, kar pomeni, da s kilobajtni programi ne moremo izpisati več kot 2561024 števil. Torej ni mogoče na noben način zapisati nekega števila, ki je manjše od 2561024.
Toda napišimo Python program, ki generira vse možne kilobajtne tekste, jih zažene, in če izpišejo neko število — to število doda v slovar dosegljivih števil. Po preverjanju vseh 2561024 možnosti, kolikor časa že bo trajalo — program poišče, katero je najmanjše število, ki manjka v slovarju, in izpiše to število. Zdi se očitno, da bo tak program maširal v kilobajt kodiranja — in izpisal točno tisto število, ki ga ni mogoče izpisati s kilobajtno programsko kodo!
Kje pa je zdaj zvijača? Z neformalnostjo oznak tega ne moremo več odpraviti!
Če vas zmoti, da bo naš program potreboval astronomsko količino pomnilnika za delovanje — slovar (ali bitno polje) z 2561024 elementi — lahko vse to dosežemo tudi brez njega: za vsako od 2561024 števil po vrsti preizkusimo vse 2561024 možne programe, dokler ne najdemo ustreznega. Ni važno, da bo to preizkušanje trajalo zelo dolgo: po preverjanju manj kot (2561024)2 parov števila in programa se bo namreč zaključilo in našlo to zaželeno število.
Ali pa se ne bo završilo? Saj med vsemi programi, ki bodo preizkušeni, naletimo na while True: pass (in njene funkcionalne analoge) — in nadaljnje preverjanje takega programa se ne bo zgodilo!
Za razliko od Berryjevega paradoksa, kjer je bil trik v neformalnosti oznak, imamo v drugem primeru dobro prikrito preoblikovanje . Gre namreč za to, da po programu ni mogoče v končnem času določiti njegovega izhoda. Še posebej, Kolmogorovska kompleksnost : ne obstaja noben algoritem, ki bi omogočil najti dolžino najkrajšega programa, ki izpisuje dano število; torej tudi ni rešitve za Berryjev problem — najti dolžino najkrajšega besednega označevalca za dano število.
Izvor: habr.com
