Datu saspieÅ”anas uzdevums savÄ visvienkÄrÅ”ÄkajÄ formÄ var attiekties uz skaitļiem un to apzÄ«mÄjumiem. Skaitļus var apzÄ«mÄt ar cipariem (āvienspadsmitā numuram 11), matemÄtiskÄm izteiksmÄm (ādivi divdesmitajÄā numuram 1048576), virknes izteiksmÄm (āpiecas devÄ«tniekusā numuram 99999), Ä«paÅ”vÄrdiem (ābeasts skaitsā numuram 666, āTjÅ«ringa nÄves gadsā numuram 1954), vai ar nejauÅ”u to kombinÄciju. Der jebkÄds apzÄ«mÄjums, ar kuru sarunbiedrs var viennozÄ«mÄ«gi noteikt, par kuru skaitli ir runa. AcÄ«mredzami, ka sazinÄties ar sarunbiedru par āastoÅu faktoriÄluā efektÄ«vÄk nekÄ ar ekvivalentu apzÄ«mÄjumu āÄetrdesmit tÅ«kstoÅ”i trÄ«sdesmitā. Å eit rodas loÄ£isks jautÄjums: kÄds apzÄ«mÄjums dotajam skaitlim ir Ä«sÄkais?
Filozofs Bertrands Rasels 1908. gadÄ publicÄja , kurÄ tiek apspriests apzÄ«mÄjumu jautÄjums no pretÄjÄs puses: kÄds ir viss mazÄkais skaitlis, kam apzÄ«mÄÅ”anai nepietiek ar astoÅdesmit burtiem?
Å Ädam skaitlim ir jÄnÄk eksistÄt: no astoÅdesmit krievu burtiem un atstarpÄm var izveidot tikai 3480 apzÄ«mÄjumus, lÄ«dz ar to, izmantojot astoÅdesmit burtus, nav iespÄjams apzÄ«mÄt vairÄk par 3480 skaitļiem. TÄtad skaitli, kas ir ne lielÄks par 3480, apzÄ«mÄt Å”ÄdÄ veidÄ nav iespÄjams.
TÄdÄjÄdi Å”im skaitlim atbilst apzÄ«mÄjums āviss mazÄkais skaitlis, kam apzÄ«mÄÅ”anai nepietiek ar astoÅdesmit burtiemā, kurÄ ir tikai 78 burti! No vienas puses, Å”im skaitlim ir jÄpastÄv; no otras puses, ja Å”is skaitlis pastÄv, tad tÄ apzÄ«mÄjums tam neatbilst. Paradoks!
VienkÄrÅ”Äkais veids, kÄ atrauties no Ŕī paradoksa, ir atsaukties uz neformÄlu vÄrdiski izteikumiem. Sakot, ja apzÄ«mÄjumos bÅ«tu pieļaujams tikai konkrÄti noteikts izteikumu kopums, tad āviss mazÄkais skaitlis, kam apzÄ«mÄÅ”anai nepietiek ar astoÅdesmit burtiemā nepietiekami apzÄ«mÄjums nebÅ«tu pieļaujams, kamÄr praktiski noderÄ«gi apzÄ«mÄjumi, piemÄram, āastoÅu faktoriÄluā paliktu pieļaujami.
Vai ir formÄli veidi, kÄ aprakstÄ«t secÄ«bu (algoritmu) darbÄ«bu ar skaitļiem? Ir, un to netrÅ«kst ā tos sauc par programmÄÅ”anas valodÄm. Izmantosim programmas (piemÄram, Python), lai izvadÄ«tu nepiecieÅ”amos skaitļus. PiemÄram, piecÄm devÄ«tniekus derÄs programma print("9"*5). MÄs joprojÄm interesÄjamies par Ä«sÄko programmu noteiktam skaitlim. Å Ädas programmas garumu sauc par skaitļa; tas ir teorÄtiskais limits, lÄ«dz kuram noteikto skaitli var saspiest.
Aiz Berija paradoksa tagad varam aplÅ«kot lÄ«dzÄ«gu: kÄds ir vissÄ«kÄkais skaitlis, kura izvadÄ«Å”anai nepietiek ar kilobaitiem kodu?
MÄs domÄsim tÄpat kÄ iepriekÅ”: ir 2561024 kilobaitu teksti, tÄdÄļ ar kilobaita programmÄm var izvadÄ«t ne vairÄk kÄ 2561024 skaitļus. TÄtad, ir kÄds skaitlis, kuru ne vairÄk par 2561024 nevar izvadÄ«t Å”ÄdÄ veidÄ.
TomÄr uzrakstÄ«sim Python programmu, kas Ä£enerÄ visus iespÄjamos kilobaitu tekstus, izpilda tos, un, ja tie izvada kÄdu skaitli ā pievieno Å”o skaitli sasniedzamo skaitļu vÄrdnÄ«cÄ. PÄc visu 2561024 iespÄju pÄrbaudes, neatkarÄ«gi no tÄ, cik ilgi tas prasÄ«s ā programma meklÄ, kurÅ” ir vissÄ«kÄkais skaitlis, kas trÅ«kst vÄrdnÄ«cÄ, un izvada Å”o skaitli. IzskatÄs acÄ«mredzami, ka Å”Äda programma iekļausies kilobaitÄ kodu ā un izvadÄ«s to paÅ”u skaitli, kuru nav iespÄjams izvadÄ«t ar kilobaita programmu!
Kur ir tagad viltÄ«ba? NeformÄlÄs apzÄ«mÄjumi vairs nav attaisnojums!
Ja jÅ«s mulsina tas, ka mÅ«su programma prasÄ«s astronomisku atmiÅas daudzumu darbam ā vÄrdnÄ«ca (vai bitu masÄ«vs) ar 2561024 elementiem ā tad to paÅ”u var izdarÄ«t arÄ« bez tÄ: katram no 2561024 skaitļiem secÄ«gi pÄrbaudÄ«t visas 2561024 iespÄjamÄs programmas, lÄ«dz atrodam piemÄrotu. Nav svarÄ«gi, ka Å”Äda pÄrbaude ilgs ļoti ilgi: pÄc mazÄk kÄ (2561024)2 pÄru skaitļa un programmas pÄrbaudes, tÄ beigsies un atradÄ«s to paÅ”u svÄto skaitli.
Vai arÄ« nebeigsies? Jo starp visÄm programmÄm, kas tiks izmÄÄ£inÄtas, tiks sastapts while True: pass (un tÄs funkcionÄlÄs analoÄ£ijas) ā un tÄlÄk Å”Ädas programmas pÄrbaude vairs neies tÄlÄk!
AtŔķirÄ«bÄ no Berija paradoksa, kur viltÄ«ba bija neformÄlajos apzÄ«mÄjumos, otrajÄ gadÄ«jumÄ mÄs saskaramies ar labi maskÄtu pÄrformulÄjumu . ProblÄma ir tÄda, ka no programmas nav iespÄjams noteikt tÄs izvadÄ«jumu ierobežotÄ laikÄ. It Ä«paÅ”i, Kolmogorova sarežģītÄ«ba : nav nekÄds algoritms, kas ļautu noteikt Ä«sÄkÄs programmas garumu, kas izvada dotu skaitli; tÄtad, nav arÄ« risinÄjuma Berija uzdevumam ā atrast dotajam skaitlim Ä«sÄkÄ vÄrdiskÄ apzÄ«mÄjuma garumu.
Avots: habr.com
Russian
Italian
German
Polish
Estonian
Albanian
Bulgarian
Croatian
Czech
Danish
Dutch
English
French
Hungarian
Latvian
Lithuanian
Norwegian
Portuguese
Romanian
Slovak
Slovenian
Spanish
Swedish