Datu saspiešanas problēma visvienkāršākajā veidā var būt saistīta ar skaitļiem un to apzīmējumiem. Ciparus var apzīmēt ar cipariem ("vienpadsmit" skaitlim 11), matemātiskās izteiksmes ("divi divdesmitajos" priekš 1048576), virknes izteiksmes ("pieci deviņi" par 99999), īpašvārdi ("zvēra numurs" par 666, "Tjūringa nāves gads" par 1954. gadu) vai to patvaļīgas kombinācijas. Jebkurš apzīmējums ir piemērots, lai sarunu biedrs varētu skaidri noteikt, par kādu numuru mēs runājam. Acīmredzot, pastāstiet savam sarunu biedram "astoņu faktors" efektīvāka par līdzvērtīgu apzīmējumu "četrdesmit tūkstoši trīs simti divdesmit". Šeit rodas loģisks jautājums: kāds ir konkrētā skaitļa īsākais apzīmējums?
Filozofs Bertrāns Rasels publicēja 1908. gadā , kas skar skaitļu apzīmējuma jautājumu no pretējās puses: Kāds ir mazākais cipars, kuram nav nepieciešami astoņdesmit burti?
Šādam skaitlim ir jābūt: no astoņdesmit krievu burtiem un atstarpēm jūs varat izveidot tikai 3480 apzīmējumus, kas nozīmē, ka, izmantojot astoņdesmit burtus, jūs varat apzīmēt ne vairāk kā 3480 ciparus. Tas nozīmē, ka šādā veidā nav iespējams norādīt noteiktu skaitli, kas nepārsniedz 3480.
Tas nozīmē, ka šis skaitlis atbildīs apzīmējumam "mazākais skaitlis, kuram nepietiek ar astoņdesmit burtiem", kurā ir tikai 78 burti! No vienas puses, šim skaitlim ir jābūt; savukārt, ja šis skaitlis eksistē, tad tā apzīmējums tam neatbilst. Paradokss!
Vienkāršākais veids, kā noraidīt šo paradoksu, ir atsaukties uz verbālo apzīmējumu neformalitāti. Tāpat kā, ja apzīmējumā būtu atļauta tikai īpaši definēta izteiksmju kopa, tad "mazākais skaitlis, kuram nepietiek ar astoņdesmit burtiem" nebūtu derīgs apzīmējums, savukārt praktiski noderīgi apzīmējumi, piemēram, "astoņu faktors" paliktu pieņemams.
Vai ir formāli veidi, kā aprakstīt darbību secību (algoritmu) ar skaitļiem? Ir, un pārpilnībā - tās sauc par programmēšanas valodām. Verbālo apzīmējumu vietā izmantosim programmas (piemēram, Python), kas parāda vajadzīgos skaitļus. Piemēram, pieciem deviņiem programma ir piemērota print("9"*5). Mēs turpināsim interesēties par īsāko programmu konkrētam numuram. Šādas programmas garums tiek saukts skaitļi; tā ir teorētiskā robeža, līdz kurai var saspiest doto skaitli.
Berija paradoksa vietā tagad varam apsvērt līdzīgu: Kāds ir mazākais skaitlis, kura izvadīšanai nepietiek ar kilobaitu programmu?
Spriedīsim tāpat kā iepriekš: ir 2561024 kilobaitu teksti, kas nozīmē, ka kilobaitu programmas var izvadīt ne vairāk par 2561024 skaitļiem. Tas nozīmē, ka šādā veidā nevar iegūt noteiktu skaitli, kas nav lielāks par 2561024.
Bet uzrakstīsim programmu Python, kas ģenerē visus iespējamos kilobaitu tekstus, palaiž tos izpildei un, ja tie izvada skaitli, pievieno šo numuru sasniedzamo vārdnīcai. Pēc visu 2561024 XNUMX XNUMX iespēju pārbaudes, neatkarīgi no tā, cik ilgi tas aizņem, programma meklē mazāko vārdnīcā trūkstošo skaitli un izdrukā šo skaitli. Šķiet pašsaprotami, ka šāda programma ietilps koda kilobaitā – un izvadīs tieši to skaitu, ko nevar izvadīt kilobaitu programma!
Kas tagad ir nozveja? To vairs nevar attiecināt uz apzīmējuma neformalitāti!
Ja jūs mulsina fakts, ka mūsu programmas darbībai būs nepieciešams astronomisks atmiņas apjoms - vārdnīca (vai bitu masīvs) no 2561024 elementiem -, tad to pašu var izdarīt arī bez tās: katram no 2561024 cipariem, savukārt , izejiet cauri visām 2561024 iespējamām programmām, kamēr nav piemērotas. Nav svarīgi, ka šāda meklēšana ilgs ļoti ilgu laiku: pēc mazāk nekā (2561024)2 pāru pārbaudīšanas no numura un programmas tas beigsies un atradīs šo ļoti loloto skaitli.
Vai arī tas nepabeigs? Patiešām, starp visām programmām, kuras tiks izmēģinātas, būs while True: pass (un tā funkcionālie analogi) - un lieta netiks tālāk par šādas programmas testēšanu!
Atšķirībā no Berija paradoksa, kur nozveja bija apzīmējuma neformalitātē, otrajā gadījumā mums ir labi slēpta pārformulācija. . Fakts ir tāds, ka nav iespējams noteikt tās izvadi no programmas ierobežotā laikā. Jo īpaši Kolmogorova sarežģītība : nav algoritma, kas ļautu noteiktam skaitlim atrast īsākās programmas garumu, kas izdrukā šo skaitli; kas nozīmē, ka Berija problēmai nav risinājuma – atrast konkrētam numuram īsākā verbālā apzīmējuma garumu.
Avots: www.habr.com