Problem stiskanja podatkov se v najpreprostejši obliki lahko nanaša na števila in njihove zapise. Številke lahko označimo s številkami ("enajst" za število 11), matematične izraze ("dva v dvajsetem" za 1048576), nizovni izrazi ("pet devetk" za 99999), lastna imena ("število zveri" za 666, "leto Turingove smrti" za leto 1954) ali njihove poljubne kombinacije. Primerna je katera koli oznaka, s katero lahko sogovornik jasno ugotovi, o kateri številki govorimo. Očitno povejte sogovorniku "faktoriel osem" učinkovitejši od enakovrednega zapisa "štirideset tisoč tristo dvajset". Tu se pojavi logično vprašanje: kakšen je najkrajši zapis za dano število?
Filozof Bertrand Russell je leta 1908 objavil , ki se problematike zapisa števil dotika z nasprotne strani: Katero je najmanjše število, ki ne zahteva osemdeset črk?
Takšna številka mora obstajati: iz osemdesetih ruskih črk in presledkov lahko sestavite samo 3480 oznak, kar pomeni, da z osemdesetimi črkami lahko označite največ 3480 številk. To pomeni, da je nemogoče na ta način določiti določeno število, ki ne presega 3480.
To pomeni, da bo ta številka ustrezala oznaki "najmanjše število, za katerega ni dovolj osemdeset črk", ki ima le 78 črk! Po eni strani mora ta številka obstajati; po drugi strani pa, če ta številka obstaja, potem njena oznaka ne ustreza njej. Paradoks!
Ta paradoks najlažje zavrnemo s sklicevanjem na neformalnost besednih zapisov. Na primer, če bi bil v zapisu dovoljen samo posebej definiran nabor izrazov "najmanjše število, za katerega ni dovolj osemdeset črk" ne bi bil veljaven zapis, medtem ko praktično uporabni zapisi, kot je "faktoriel osem" bi ostalo sprejemljivo.
Ali obstajajo formalni načini za opis zaporedja (algoritma) dejanj na številkah? Obstajajo in v izobilju - imenujejo se programski jeziki. Namesto besednih zapisov bomo uporabili programe (na primer v Pythonu), ki prikazujejo zahtevana števila. Na primer, za pet devetk je program primeren print("9"*5). Še naprej nas bo zanimal najkrajši program za določeno številko. Dolžina takega programa se imenuje številke; je teoretična meja, do katere je mogoče stisniti dano število.
Namesto Berryjevega paradoksa lahko zdaj razmislimo o podobnem: Katero je najmanjše število, ki ga kilobajtni program ne more izpisati?
Razmišljali bomo na enak način kot prej: besedila so velika 2561024 kilobajtov, kar pomeni, da programi ne morejo izpisati več kot 2561024 številk. To pomeni, da na ta način ni mogoče izpeljati določenega števila, ki ni večje od 2561024.
Toda napišimo program v Pythonu, ki generira vsa možna kilobajtna besedila, jih požene za izvedbo in če izpišejo številko, doda to številko v slovar dosegljivih. Po preverjanju vseh 2561024 možnosti, ne glede na to, koliko časa traja, program poišče najmanjšo številko, ki manjka v slovarju, in to številko natisne. Zdi se očitno, da bo tak program ustrezal kilobajtu kode - in bo izpisal prav tisto število, ki ga kilobajtni program ne more izpisati!
V čem je zdaj fora? Ne gre več pripisovati neformalnosti zapisa!
Če vas bega dejstvo, da bo naš program za delovanje potreboval astronomsko količino pomnilnika - slovar (ali bitni niz) 2561024 elementov - potem lahko storite isto stvar brez njega: za vsako od 2561024 številk po vrsti , pojdite skozi vseh 2561024 možnih programov, dokler ne najdete nobenega primernega. Ni pomembno, da bo takšno iskanje trajalo zelo dolgo: po preverjanju manj kot (2561024) 2 parov iz številke in programa se bo končalo in našlo to zelo cenjeno številko.
Ali pa se ne bo končalo? Med vsemi programi, ki jih bodo preizkusili, bo namreč while True: pass (in njegovi funkcionalni analogi) - in zadeva ne bo šla dlje od testiranja takšnega programa!
Za razliko od Berryjevega paradoksa, kjer je bila kvaka v neformalnosti zapisa, imamo v drugem primeru dobro prikrito preoblikovanje . Dejstvo je, da je nemogoče določiti njegov rezultat iz programa v končnem času. Zlasti kompleksnost Kolmogorova : ni algoritma, ki bi za dano število omogočil najti dolžino najkrajšega programa, ki to število izpiše; kar pomeni, da ni rešitve Berryjevega problema - najti dolžino najkrajše besedne oznake za dano število.
Vir: www.habr.com