Problem sažimanja podataka, u svom najjednostavnijem obliku, može se odnositi na brojeve i njihove zapise. Brojevi se mogu označiti brojevima ("jedanaest" za broj 11), matematički izrazi ("dva u dvadesetom" za 1048576), niz izraza ("pet devetki" za 99999), vlastita imena ("broj zvijeri" za 666, "godina Turingove smrti" za 1954), ili njihove proizvoljne kombinacije. Prikladna je svaka oznaka kojom sugovornik može jasno odrediti o kojem broju govorimo. Očito, recite svom sugovorniku "faktorijel od osam" učinkovitiji od ekvivalentne notacije "četrdeset tisuća tristo dvadeset". Ovdje se postavlja logično pitanje: koji je najkraći zapis za određeni broj?
Filozof Bertrand Russell objavio je 1908 , koji problematiku zapisivanja brojeva dotiče 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 sastaviti samo 3480 oznaka, što znači da pomoću osamdeset slova možete označiti najviše 3480 brojeva. To znači da je nemoguće na ovaj način označiti određeni broj ne većim od 3480.
To znači da će ovaj broj odgovarati oznaci "najmanji broj za koji nije dovoljno osamdeset slova", koji ima samo 78 slova! S jedne strane, ovaj broj mora postojati; s druge strane, ako taj broj postoji, onda mu njegova oznaka ne odgovara. Paradoks!
Najlakši način da odbacite ovaj paradoks je pozvati se na neformalnost verbalnih notacija. Kao, kad bi u zapisu bio dopušten samo specifično definiran skup izraza "najmanji broj za koji nije dovoljno osamdeset slova" ne bi bila valjana notacija, dok praktično korisne notacije poput "faktorijel od osam" bi ostala prihvatljiva.
Postoje li formalni načini da se opiše niz (algoritam) radnji na brojevima? Ima ih, i to u izobilju - zovu se programski jezici. Umjesto verbalnih zapisa koristit ćemo programe (npr. u Pythonu) koji prikazuju tražene brojeve. Na primjer, za pet devetki program je prikladan print("9"*5). I dalje ćemo biti zainteresirani za najkraći program za određeni broj. Duljina takvog programa naziva se brojevi; to je teorijska granica do koje se dati broj može sabiti.
Umjesto Berryjeva paradoksa, sada možemo razmotriti sličan: Koji je najmanji broj koji kilobajtni program nije dovoljan za ispis?
Rezonirati ćemo na isti način kao i prije: postoje 2561024 kilobajta teksta, što znači da programi kilobajta ne mogu ispisati više od 2561024 broja. To znači da se određeni broj ne veći od 2561024 ne može izvesti na ovaj način.
Ali napišimo program u Pythonu koji generira sve moguće kilobajtne tekstove, pokreće ih za izvršenje, i ako izlaze broj, dodaje taj broj u rječnik dostupnih. Nakon provjere svih 2561024 mogućnosti, koliko god to trajalo, program traži najmanji broj koji nedostaje u rječniku i ispisuje taj broj. Čini se očiglednim da će takav program stati u kilobajt koda - i da će ispisati upravo onaj broj koji ne može ispisati program od kilobajta!
U čemu je sada caka? Ne može se više pripisati neformalnosti notacije!
Ako ste zbunjeni činjenicom da će naš program zahtijevati astronomsku količinu memorije za rad - rječnik (ili niz bitova) od 2561024 elementa - onda možete učiniti istu stvar bez njega: za svaki od 2561024 broja, redom , prođite kroz svih 2561024 mogućih programa, sve dok nema odgovarajućeg. Nije bitno da će takva potraga trajati jako dugo: nakon provjere manje od (2561024) 2 para iz broja i programa, završit će i pronaći taj vrlo cijenjeni broj.
Ili neće završiti? Dapače, među svim programima koji će biti isprobani bit će while True: pass (i njegovi funkcionalni analozi) - i stvar neće ići dalje od testiranja takvog programa!
Za razliku od Berryjeva paradoksa, gdje je kvaka bila u neformalnosti notacije, u drugom slučaju imamo dobro prikrivenu reformulaciju . Činjenica je da je nemoguće odrediti njegov izlaz iz programa u konačnom vremenu. Konkretno, Kolmogorovljeva složenost : ne postoji algoritam koji bi omogućio, za zadani broj, pronaći duljinu najkraćeg programa koji ispisuje taj broj; što znači da ne postoji rješenje za Berryjev problem - pronaći duljinu najkraće verbalne oznake za dati broj.
Izvor: www.habr.com