Zadatak kompresije podataka u svom najjednostavnijem obliku može se odnositi na brojeve i njihove oznake. Brojevi se mogu označavati brojkama („jedanaest“ za broj 11), matematičkim izrazima („dva u dvadesetoj“ za 1048576), string izrazima („pet devetki“ za 99999), vlastitim imenima („broj zvijeri“ za 666, „godina Turingove smrti“ za 1954.), ili proizvoljnim njihovim kombinacijama. Svaka oznaka koja omogućava sugovorniku da jednoznačno odredi o kojem broju se radi je prihvatljiva. Očito je da je učinkovitije reći sugovorniku „faktorijal osam“ nego ekvivalentna oznaka „četrdeset tisuća trideset“. Ovdje se postavlja logično pitanje: koja je oznaka za zadani broj najkraća?
Filozof Bertrand Russell je 1908. godine objavio , koji se bavi pitanjem oznaka brojeva s suprotne strane: koji je najmanji broj za čiju oznaku nije dovoljno osamdeset slova?
Takav broj mora postojati: od osamdeset ruskih slova i razmaka može se sastaviti samo 3480 oznaka, stoga se pomoću osamdeset slova može označiti najviše 3480 brojeva. To znači da nije moguće označiti neko broj, koje je ne veće od 3480, na taj način.
Dakle, toj broj će odgovarati oznaka „najmanji broj za čiju oznaku nije dovoljno osamdeset slova“, koja sadrži samo 78 slova! S jedne strane, ovaj broj mora postojati; s druge strane, ako ovaj broj postoji, njegova oznaka mu ne odgovara. Paradoks!
Najjednostavniji način da se odbaci ovaj paradoks je pozvati se na neformalnost usmenih oznaka. Kažu da, da su u oznakama dopušteni samo konkretno određeni setovi izraza, tada „najmanji broj za čiju oznaku nije dovoljno osamdeset slova“ ne bi bila dopuštena oznaka, dok su praktične korisne oznake poput „faktorijal osam“ ostale bile dopuštene.
Postoje li formalni načini za opisivanje sekvenci (algoritama) radnji s brojevima? Ima, i u obilju — nazivaju se programskim jezicima. Umjesto usmenih oznaka koristit ćemo programe (na primjer, u Pythonu) koji ispisuju potrebne brojeve. Na primjer, za pet devetki odgovarat će program print("9"*5). I dalje ćemo se zanimati za najkraći program za zadani broj. Dužina takvog programa naziva se broja; to je teorijska granica do koje se zadani broj može komprimirati.
Umjesto Berryjeva paradoksa sada možemo razmotriti sličnu situaciju: koji je najmanji broj za čije ispisivanje nije dovoljna kilobajtna programa?
Razmišljat ćemo na isti način kao prije: postoji 2561024 kilobajtnih tekstova, što znači da se kilobajtnih programa može koristiti za ispisivanje najviše 2561024 brojeva. Dakle, neki broj, koji nije veći od 2561024, ne može se na taj način ispisati.
Ali napisat ćemo program na Pythonu koji generira sve moguće kilobajtne tekstove, izvršava ih, a ako ispisuju neki broj — taj broj dodaje u rječnik dostupnih. Nakon provjere svih 2561024 mogućnosti, koliko god vremena to trajalo — program traži koji je najmanji broj koji nedostaje u rječniku, i ispisuje taj broj. Čini se očitim da će takav program stati u kilobajt koda — i ispisati onaj broj koji se ne može ispisati kilobajtnim programom!
U čemu je sada zamka? Na neformalnost oznaka se više ne može svesti!
Ako vas muči to što će naš program zahtijevati astronomski količinu memorije za rad — rječnik (ili bitna polja) od 2561024 elemenata — to se sve može postići i bez njega: za svako od 2561024 brojeva redom provjeravati svih 2561024 mogućih programa, dok se ne nađe odgovarajući. Nije važno što će takvo pretraživanje trajati jako dugo: nakon provjere manje od (2561024)2 parova broja i programa, to će se završiti i naći onaj dragocjeni broj.
Ili se možda neće završiti? Jer među svim programima koji će biti isprobani naletit ćemo na while True: pass (i njezine funkcionalne analoge) — i dalje provjere takvog programa nećemo moći doći do kraja!
Za razliku od Berryjeva paradoksa, gdje je zamka bila u neformalnosti oznaka, u drugom slučaju imamo dobro maskiranu preformulaciju . Radi se o tome da se za program u konačnom vremenu ne može odrediti njegovo ispisivanje. Konkretno, kolmogorovska složenost : ne postoji algoritam koji bi omogućio da se za dano broj odredi duljina najkraćeg programa koji ispisuje taj broj; što znači da rješenja za Berryjev problem također nema — pronaći duljinu najkraćeg verbalnog označavanja za dano broj.
Izvor: habr.com
