Paradoksi oko kompresije podataka

Problem kompresije podataka, u svom najjednostavnijem obliku, može se odnositi na brojeve i njihove oznake. Brojevi se mogu označiti brojevima ("jedanaest" za broj 11), matematički izrazi ("dva u dvadesetom" za 1048576), string izrazi ("pet devetki" za 99999), vlastita imena ("broj zveri" za 666, "godina Turingove smrti" za 1954.) ili njihove proizvoljne kombinacije. Pogodna je svaka oznaka po kojoj sagovornik može jasno odrediti o kojem broju govorimo. Očigledno, recite svom sagovorniku "faktorijal od osam" efikasnije od ekvivalentne notacije "četrdeset hiljada trista dvadeset". Ovdje se postavlja logično pitanje: koja je najkraća notacija za dati broj?

Filozof Bertrand Rasel objavio je 1908 "Berijev paradoks", koji se dotiče pitanja zapisivanja brojeva sa suprotne strane: Koji je najmanji broj za koji nije potrebno osamdeset slova?
Takav broj mora postojati: od osamdeset ruskih slova i razmaka možete napraviti samo 3480 oznaka, što znači da pomoću osamdeset slova možete označiti ne više od 3480 brojeva. To znači da je nemoguće odrediti određeni broj ne veći od 3480 na ovaj način.

To znači da će ovaj broj odgovarati oznaci "najmanji broj za koji osamdeset slova nije dovoljno", koji ima samo 78 slova! S jedne strane, ovaj broj mora postojati; s druge strane, ako ovaj broj postoji, onda mu njegova oznaka ne odgovara. Paradoks!

Najlakši način da se odbaci ovaj paradoks je da se pozovete na neformalnost verbalnih notacija. Na primjer, kada bi u notaciji bio dozvoljen samo posebno definiran skup izraza "najmanji broj za koji osamdeset slova nije dovoljno" ne bi bila valjana notacija, dok su praktično korisne notacije poput "faktorijal od osam" bi ostala prihvatljiva.

Postoje li formalni načini da se opiše redoslijed (algoritam) akcija na brojeve? Ima ih, i to u izobilju - zovu se programski jezici. Umjesto verbalnih notacija koristićemo programe (na primjer, u Pythonu) koji prikazuju tražene brojeve. Na primjer, za pet devetki program je prikladan print("9"*5). I dalje ćemo biti zainteresovani za najkraći program za određeni broj. Dužina takvog programa se zove Kolmogorovljeva složenost brojevi; to je teorijska granica do koje se dati broj može komprimirati.

Umjesto Berryjevog paradoksa, sada možemo razmotriti sličan: Koji je najmanji broj za koji kilobajtni program nije dovoljan za izlaz?

Rezonovaćemo na isti način kao i ranije: postoji 2561024 kilobajtnih tekstova, što znači da programi od kilobajta ne mogu izbaciti više od 2561024 brojeva. To znači da se određeni broj ne veći od 2561024 ne može izvesti na ovaj način.

Ali hajde da napišemo program u Pythonu koji generiše sve moguće tekstove od kilobajta, pokreće ih za izvršenje i ako daju broj, onda dodaje ovaj broj u rečnik dostupnih. Nakon provjere svih 2561024 mogućnosti, bez obzira koliko dugo traje, program traži najmanji broj koji nedostaje u rječniku i ispisuje taj broj. Čini se očiglednim da će se takav program uklopiti u kilobajt koda - i da će izbaciti baš onaj broj koji ne može da izbaci program od kilobajta!

U čemu je sada kvaka? To se više ne može pripisati neformalnosti notacije!

Ako ste zbunjeni činjenicom da će našem programu biti potrebna astronomska količina memorije za rad - rječnik (ili niz bitova) od 2561024 elemenata - onda možete učiniti istu stvar bez njega: za svaki od 2561024 brojeva, zauzvrat , prođite kroz svih 2561024 mogućih programa, dok ne nađete nijedan odgovarajući. Nema veze što će takva pretraga trajati jako dugo: nakon provjere manje od (2561024)2 para iz broja i programa, završit će se i pronaći taj vrlo dragi broj.

Ili se neće završiti? Zaista, među svim programima koji će biti isprobani, biće ih while True: pass (i njegovi funkcionalni analozi) - i stvar neće ići dalje od testiranja takvog programa!

Za razliku od Berryjevog paradoksa, gdje je kvaka bila u neformalnosti notacije, u drugom slučaju imamo dobro prikrivenu reformulaciju "problemi zaustavljanja". Činjenica je da je nemoguće odrediti njegov izlaz iz programa u konačnom vremenu. Konkretno, složenost Kolmogorova incomputable: ne postoji algoritam koji bi omogućio da se za dati broj pronađe dužina najkraćeg programa koji ispisuje ovaj broj; što znači da nema rješenja za Berryjev problem - pronaći dužinu najkraće verbalne oznake za dati broj.

izvor: www.habr.com