Məlumatların sıxılması problemi, ən sadə formada, rəqəmlər və onların qeydləri ilə əlaqəli ola bilər. Rəqəmlər rəqəmlərlə işarələnə bilər ("on bir" 11 rəqəmi üçün), riyazi ifadələr ("İyirmincidə iki" 1048576 üçün), sətir ifadələri ("beş doqquz" 99999 üçün), xüsusi adlar ("heyvanın sayı" 666 üçün, "Türinqin ölüm ili" 1954-cü il üçün) və ya onların ixtiyari birləşmələri. Həmsöhbətin hansı nömrə haqqında danışdığımızı aydın şəkildə müəyyən edə biləcəyi hər hansı bir təyinat uyğun gəlir. Aydındır ki, həmsöhbətinizə deyin "səkkiz faktorial" ekvivalent qeyddən daha səmərəlidir "qırx min üç yüz iyirmi". Burada məntiqi sual yaranır: verilmiş ədəd üçün ən qısa qeyd hansıdır?
Filosof Bertrand Russell 1908-ci ildə nəşr etdi , əks tərəfdən ədədlərin qeyd edilməsi məsələsinə toxunur: Səksən hərf tələb etməyən ən kiçik ədəd hansıdır?
Belə bir rəqəm mövcud olmalıdır: səksən rus hərfindən və boşluqlarından cəmi 3480 işarə təşkil edə bilərsiniz, yəni səksən hərfdən istifadə edərək 3480-dən çox olmayan rəqəm təyin edə bilərsiniz. Bu o deməkdir ki, bu şəkildə 3480-dən çox olmayan müəyyən bir nömrə təyin etmək mümkün deyil.
Bu o deməkdir ki, bu nömrə təyinata uyğun olacaq "səksən hərfin kifayət etmədiyi ən kiçik rəqəm", cəmi 78 hərfdən ibarət! Bir tərəfdən, bu rəqəm mövcud olmalıdır; digər tərəfdən, əgər bu nömrə varsa, onun təyinatı ona uyğun gəlmir. Paradoks!
Bu paradoksu aradan qaldırmağın ən asan yolu şifahi qeydlərin qeyri-rəsmiliyinə istinad etməkdir. Məsələn, qeyddə yalnız xüsusi olaraq müəyyən edilmiş ifadələr toplusuna icazə verilsəydi "səksən hərfin kifayət etmədiyi ən kiçik rəqəm" kimi praktiki olaraq faydalı qeydlər etibarlı notation olmazdı "səkkiz faktorial" məqbul olaraq qalacaqdı.
Rəqəmlər üzərində hərəkətlərin ardıcıllığını (alqoritmini) təsvir etməyin formal yolları varmı? Var və bolca - onlara proqramlaşdırma dilləri deyilir. Şifahi qeydlər əvəzinə biz tələb olunan nömrələri göstərən proqramlardan (məsələn, Python dilində) istifadə edəcəyik. Məsələn, beş doqquz üçün proqram uyğundur print("9"*5). Verilmiş nömrə üçün ən qısa proqramla maraqlanmağa davam edəcəyik. Belə bir proqramın uzunluğu deyilir nömrələri; verilmiş ədədin sıxıla biləcəyi nəzəri hədddir.
Berri paradoksu əvəzinə indi oxşar bir paradoksu nəzərdən keçirə bilərik: Kilobaytlıq proqramın çıxması üçün kifayət etmədiyi ən kiçik rəqəm hansıdır?
Əvvəlki kimi əsaslandıracağıq: 2561024 kilobayt mətnlər var, yəni kilobayt proqramları ilə 2561024-dən çox rəqəm çıxarıla bilməz. Bu o deməkdir ki, 2561024-dən çox olmayan müəyyən bir rəqəm bu şəkildə əldə edilə bilməz.
Ancaq gəlin Python-da bütün mümkün kilobayt mətnləri yaradan, onları icra üçün işə salan və bir nömrə çıxarsa, bu nömrəni əlçatan olanların lüğətinə əlavə edən bir proqram yazaq. Bütün 2561024 imkanı yoxladıqdan sonra, nə qədər vaxt aparmasından asılı olmayaraq, proqram lüğətdə çatışmayan ən kiçik rəqəmi axtarır və həmin rəqəmi çap edir. Aydın görünür ki, belə bir proqram bir kilobayt koda sığacaq və bir kilobayt proqram tərəfindən çıxarıla bilməyən rəqəmi çıxaracaq!
İndi tutmaq nədir? Bunu artıq qeydin qeyri-rəsmiliyinə aid etmək olmaz!
Proqramımızın işləməsi üçün astronomik həcmdə yaddaş tələb edəcəyi ilə çaşqınsınızsa - 2561024 elementdən ibarət lüğət (və ya bit massivi) - onsuz da eyni şeyi edə bilərsiniz: öz növbəsində 2561024 rəqəmin hər biri üçün , uyğun biri olmayana qədər bütün 2561024 mümkün proqramdan keçin. Belə bir axtarışın çox uzun müddət davam etməsinin əhəmiyyəti yoxdur: nömrədən və proqramdan (2561024)2 cütdən az yoxladıqdan sonra o, başa çatacaq və o çox əziz nömrəni tapacaq.
Yoxsa bitməyəcək? Həqiqətən, sınaqdan keçiriləcək bütün proqramlar arasında olacaq while True: pass (və onun funksional analoqları) - və məsələ belə bir proqramı sınaqdan keçirməkdən daha irəli getməyəcək!
Berrinin paradoksundan fərqli olaraq, qeydin qeyri-rəsmi olmasıdır, ikinci halda bizdə yaxşı gizlədilmiş islahat var. . Məsələ burasındadır ki, proqramdan onun məhsuldarlığını müəyyən müddət ərzində müəyyən etmək mümkün deyil. Xüsusilə, Kolmogorov mürəkkəbliyi : verilmiş nömrə üçün bu nömrəni çap edən ən qısa proqramın uzunluğunu tapmağa imkan verən heç bir alqoritm yoxdur; bu o deməkdir ki, Berri probleminin həlli yoxdur - verilmiş nömrə üçün ən qısa şifahi təyinatın uzunluğunu tapmaq.
Mənbə: www.habr.com