Il-problema tal-kompressjoni tad-dejta, fil-forma l-aktar sempliċi tagħha, tista 'tirrelata man-numri u n-notazzjonijiet tagħhom. In-numri jistgħu jiġu indikati b'numri ("ħdax" għan-numru 11), espressjonijiet matematiċi ("tnejn fl-għoxrin" għal 1048576), espressjonijiet ta' string ("ħames disgħa" għal 99999), ismijiet proprji ("numru tal-kruha" għal 666, "is-sena tal-mewt ta' Turing" għall-1954), jew kombinazzjonijiet arbitrarji tagħhom. Kwalunkwe nomina hija adattata li biha l-interlokutur jista 'jiddetermina b'mod ċar liema numru qed nitkellmu. Ovvjament, għid lill-interlokutur tiegħek "fattur ta' tmienja" aktar effiċjenti minn notazzjoni ekwivalenti "erbgħin elf tliet mija għoxrin". Hawnhekk tqum mistoqsija loġika: x'inhi l-iqsar notazzjoni għal numru partikolari?
Il-filosfu Bertrand Russell ippubblikat fl-1908 , li tmiss il-kwistjoni tan-notazzjoni tan-numri min-naħa opposta: X'inhu l-iżgħar numru li ma jeħtieġx tmenin ittra?
Tali numru għandu jeżisti: minn tmenin ittra u spazji Russi tista 'tagħmel biss 3480 nomina, li jfisser li billi tuża tmenin ittra tista' tinnomina mhux aktar minn 3480 numri. Dan ifisser li huwa impossibbli li jiġi indikat ċertu numru mhux aktar minn 3480 b'dan il-mod.
Dan ifisser li dan in-numru se jikkorrispondi għad-deżinjazzjoni "l-iżgħar numru li għalih tmenin ittra mhumiex biżżejjed", li għandha biss 78 ittra! Minn naħa, dan in-numru għandu jeżisti; min-naħa l-oħra, jekk dan in-numru jeżisti, allura l-isem tiegħu ma jikkorrispondix miegħu. Paradoss!
L-eħfef mod biex tiċħad dan il-paradoss huwa li tirreferi għall-informalità tan-notazzjonijiet verbali. Bħal, jekk biss sett speċifikament definit ta 'espressjonijiet kienu permessi fin-notazzjoni, allura "l-iżgħar numru li għalih tmenin ittra mhumiex biżżejjed" ma tkunx notazzjoni valida, filwaqt li notazzjonijiet prattikament utli bħal "fattur ta' tmienja" jibqa' aċċettabbli.
Hemm modi formali biex tiddeskrivi s-sekwenza (algoritmu) ta' azzjonijiet fuq in-numri? Hemm, u fl-abbundanza - huma msejħa lingwi ta 'programmar. Minflok notazzjonijiet verbali, se nużaw programmi (per eżempju, f'Python) li juru n-numri meħtieġa. Per eżempju, għal ħames nines il-programm huwa adattat print("9"*5). Se nkomplu nkunu interessati fl-iqsar programm għal numru partikolari. It-tul ta 'tali programm jissejjaħ numri; huwa l-limitu teoretiku li għalih numru partikolari jista' jiġi kkompressat.
Minflok il-paradoss ta’ Berry, issa nistgħu nikkunsidraw wieħed simili: X'inhu l-iżgħar numru li programm kilobyte mhuwiex biżżejjed biex joħroġ?
Aħna se nirraġunaw bl-istess mod bħal qabel: hemm 2561024 testi kilobyte, li jfisser li mhux aktar minn 2561024 numri jistgħu joħorġu minn programmi kilobyte. Dan ifisser li ċertu numru mhux akbar minn 2561024 ma jistax jiġi derivat b'dan il-mod.
Imma ejja nikteb programm f'Python li jiġġenera t-testi kilobyte kollha possibbli, imexxihom għall-eżekuzzjoni, u jekk joħorġu numru, imbagħad iżid dan in-numru mad-dizzjunarju ta 'dawk li jistgħu jintlaħqu. Wara li ċċekkja l-2561024 possibbiltajiet kollha, irrispettivament minn kemm idum, il-programm ifittex l-iżgħar numru nieqes mid-dizzjunarju u jistampa dak in-numru. Jidher ovvju li programm bħal dan jidħol f'kilobyte ta' kodiċi - u joħroġ in-numru stess li ma jistax joħroġ minn programm kilobyte!
X'inhi l-qabda issa? Ma jistax jiġi attribwit aktar għall-informalità tan-notazzjoni!
Jekk inti konfuż mill-fatt li l-programm tagħna se jeħtieġ ammont astronomiku ta 'memorja biex jaħdem - dizzjunarju (jew firxa ta' bits) ta '2561024 elementi - allura tista' tagħmel l-istess ħaġa mingħajrha: għal kull wieħed mill-2561024 numri, imbagħad , jgħaddu mill-2561024 programmi kollha possibbli, sakemm ma jkunx hemm wieħed adattat. Ma jimpurtax li tfittxija bħal din se ddum żmien twil ħafna: wara li tiċċekkja inqas minn (2561024)2 pari min-numru u l-programm, tispiċċa u ssib dak in-numru għażiż ħafna.
Jew mhux se jispiċċa? Tabilħaqq, fost il-programmi kollha li se jiġu ppruvati, se jkun hemm while True: pass (u l-analogi funzjonali tiegħu) - u l-kwistjoni mhux se tmur lil hinn milli tittestja programm bħal dan!
B'differenza mill-paradoss ta' Berry, fejn il-qabda kienet fl-informalità tan-notazzjoni, fit-tieni każ għandna riformulazzjoni moħbija sew . Il-fatt hu li huwa impossibbli li jiġi determinat l-output tiegħu minn programm fi żmien finit. B'mod partikolari, Kolmogorov kumplessità : m'hemm l-ebda algoritmu li jippermetti, għal numru partikolari, li jinstab it-tul tal-iqsar programm li jistampa dan in-numru; li jfisser li m'hemm l-ebda soluzzjoni għall-problema ta 'Berry - biex issib it-tul tal-iqsar nomina verbali għal numru partikolari.
Sors: www.habr.com