Tatizo la ukandamizaji wa data, kwa fomu yake rahisi, inaweza kuhusiana na nambari na maelezo yao. Nambari zinaweza kuonyeshwa kwa nambari ("kumi na moja" kwa nambari 11), maneno ya hisabati ("mbili katika ishirini" kwa 1048576), maneno ya kamba ("tisa tano" kwa 99999), majina sahihi ("idadi ya mnyama" kwa 666, "Mwaka wa kifo cha Turing" kwa 1954), au mchanganyiko wake wa kiholela. Uteuzi wowote unafaa ambayo mpatanishi anaweza kuamua wazi ni nambari gani tunazungumza. Ni wazi, mwambie mpatanishi wako "kiwanda cha nane" ufanisi zaidi kuliko nukuu sawa "elfu arobaini na mia tatu ishirini". Swali la kimantiki linatokea hapa: ni nukuu gani fupi zaidi ya nambari fulani?
Mwanafalsafa Bertrand Russell alichapishwa mnamo 1908 , ambayo inagusa suala la nukuu ya nambari kutoka upande wa pili: Ni nambari gani ndogo zaidi ambayo haihitaji herufi themanini?
Nambari kama hiyo lazima iwepo: kutoka kwa herufi na nafasi themanini za Kirusi unaweza kutengeneza majina 3480 tu, ambayo inamaanisha kuwa kwa kutumia herufi themanini unaweza kutaja nambari zisizo zaidi ya 3480. Hii ina maana kwamba haiwezekani kuteua idadi fulani si zaidi ya 3480 kwa njia hii.
Hii inamaanisha kuwa nambari hii italingana na jina "idadi ndogo ambayo herufi themanini hazitoshi", ambayo ina herufi 78 tu! Kwa upande mmoja, nambari hii lazima iwepo; kwa upande mwingine, ikiwa nambari hii iko, basi jina lake halifanani nayo. Kitendawili!
Njia rahisi ya kutupilia mbali kitendawili hiki ni kurejelea kutokuwa rasmi kwa nukuu za maneno. Kama, ikiwa tu seti maalum ya misemo iliruhusiwa katika nukuu, basi "idadi ndogo ambayo herufi themanini hazitoshi" haitakuwa nukuu halali, ilhali nukuu muhimu kama vile "kiwanda cha nane" ingebaki kukubalika.
Kuna njia rasmi za kuelezea mlolongo (algorithm) ya vitendo kwenye nambari? Kuna, na kwa wingi - huitwa lugha za programu. Badala ya nukuu za maneno, tutatumia programu (kwa mfano, katika Python) zinazoonyesha nambari zinazohitajika. Kwa mfano, kwa nines tano mpango huo unafaa print("9"*5). Tutaendelea kupendezwa na mpango mfupi zaidi wa nambari fulani. Urefu wa programu kama hiyo inaitwa nambari; ni kikomo cha kinadharia ambacho nambari fulani inaweza kubanwa.
Badala ya kitendawili cha Berry, sasa tunaweza kufikiria sawa: Ni nambari gani ndogo zaidi ambayo programu ya kilobyte haitoshi kutoa?
Tutasababu kwa njia sawa na hapo awali: kuna maandishi ya kilobyte 2561024, ambayo inamaanisha kuwa hakuna zaidi ya nambari 2561024 zinaweza kutolewa kwa programu za kilobyte. Hii ina maana kwamba nambari fulani isiyo zaidi ya 2561024 haiwezi kupatikana kwa njia hii.
Lakini hebu tuandike programu katika Python ambayo hutoa maandishi yote ya kilobyte iwezekanavyo, inaendesha kwa utekelezaji, na ikiwa hutoa nambari, basi inaongeza nambari hii kwenye kamusi ya zile zinazoweza kufikiwa. Baada ya kuangalia uwezekano wote 2561024, haijalishi inachukua muda gani, programu hutafuta nambari ndogo zaidi ambayo haipo kwenye kamusi na kuchapisha nambari hiyo. Inaonekana dhahiri kuwa programu kama hiyo itatoshea katika kilobyte ya nambari - na itatoa nambari ambayo haiwezi kutolewa na programu ya kilobyte!
Nini cha kukamata sasa? Haiwezi tena kuhusishwa na kutokuwa rasmi kwa nukuu!
Ikiwa umechanganyikiwa na ukweli kwamba programu yetu itahitaji kiasi cha kumbukumbu ya unajimu kufanya kazi - kamusi (au safu kidogo) ya vitu 2561024 - basi unaweza kufanya kitu kimoja bila hiyo: kwa kila nambari 2561024, kwa upande wake. , pitia programu zote 2561024 zinazowezekana, mpaka hakuna moja inayofaa. Haijalishi kwamba utafutaji huo utaendelea muda mrefu sana: baada ya kuangalia chini ya (2561024) jozi 2 kutoka kwa nambari na programu, itaisha na kupata nambari hiyo inayopendwa sana.
Au si kumaliza? Hakika, kati ya programu zote ambazo zitajaribiwa, kutakuwa na while True: pass (na analogues zake za kazi) - na jambo hilo halitakwenda zaidi kuliko kupima programu hiyo!
Tofauti na kitendawili cha Berry, ambapo samaki walikuwa katika hali isiyo rasmi ya nukuu, katika kesi ya pili tunayo urekebishaji uliojificha vizuri. . Ukweli ni kwamba haiwezekani kuamua matokeo yake kutoka kwa programu kwa muda mfupi. Hasa, utata wa Kolmogorov : hakuna algorithm ambayo ingeruhusu, kwa nambari fulani, kupata urefu wa programu fupi zaidi inayochapisha nambari hii; ambayo inamaanisha kuwa hakuna suluhu kwa tatizo la Berry - kupata urefu wa jina fupi zaidi la maneno kwa nambari fulani.
Chanzo: mapenzi.com