Duomenų glaudinimo problema paprasčiausia forma gali būti susijusi su skaičiais ir jų žymėjimais. Skaičiai gali būti žymimi skaitmenimis ("vienuolika" skaičiui 11), matematinės išraiškos ("du iš dvidešimties" 1048576), eilučių išraiškos ("penki devyneri" už 99999), vardai ("žvėries numeris" už 666, „Turingo mirties metai“ už 1954 m.) arba savavališkus jų derinius. Tinka bet koks žymėjimas, pagal kurį pašnekovas gali aiškiai nustatyti, apie kokį skaičių mes kalbame. Žinoma, pasakykite savo pašnekovui „aštuonių faktorius“ efektyvesnis nei lygiavertis žymėjimas "keturiasdešimt tūkstančių trys šimtai dvidešimt". Čia iškyla logiškas klausimas: koks trumpiausias tam tikro skaičiaus žymėjimas?
Filosofas Bertrandas Russellas paskelbė 1908 m , kuris paliečia skaičių žymėjimo klausimą iš priešingos pusės: Koks yra mažiausias skaičius, kuriam nereikia aštuoniasdešimties raidžių?
Toks skaičius turi egzistuoti: iš aštuoniasdešimties rusiškų raidžių ir tarpų galite sudaryti tik 3480 pavadinimų, o tai reiškia, kad naudojant aštuoniasdešimt raidžių galite pažymėti ne daugiau kaip 3480 skaičių. Tai reiškia, kad tokiu būdu neįmanoma nurodyti tam tikro skaičiaus ne daugiau kaip 3480.
Tai reiškia, kad šis skaičius atitiks pavadinimą „Mažiausias skaičius, kuriam neužtenka aštuoniasdešimties raidžių“, kuriame yra tik 78 raidės! Viena vertus, šis skaičius turi egzistuoti; kita vertus, jei šis skaičius egzistuoja, tada jo pavadinimas jo neatitinka. Paradoksas!
Lengviausias būdas atmesti šį paradoksą yra nurodyti žodinių užrašų neformalumą. Pavyzdžiui, jei žymėjime būtų leidžiamas tik konkrečiai apibrėžtas posakių rinkinys, tada „Mažiausias skaičius, kuriam neužtenka aštuoniasdešimties raidžių“ nebūtų tinkamas žymėjimas, tuo tarpu praktiškai naudingi užrašai kaip „aštuonių faktorius“ liktų priimtina.
Ar yra formalių būdų apibūdinti veiksmų su skaičiais seką (algoritmą)? Yra, ir gausybė – jos vadinamos programavimo kalbomis. Vietoj žodinių užrašų naudosime programas (pavyzdžiui, Python), kurios rodo reikiamus skaičius. Pavyzdžiui, penkiems devyneriams programa tinka print("9"*5). Mes ir toliau domėsimės trumpiausia tam tikro numerio programa. Tokios programos ilgis vadinamas skaičiai; tai teorinė riba, iki kurios galima suspausti duotą skaičių.
Vietoj Berry paradokso dabar galime apsvarstyti panašų: Koks yra mažiausias skaičius, kuriam išvesti neužtenka kilobaito programos?
Argumentuosime taip pat, kaip ir anksčiau: yra 2561024 kilobaitų tekstų, vadinasi, kilobaitų programomis galima išvesti ne daugiau kaip 2561024 numerių. Tai reiškia, kad tokiu būdu negalima gauti tam tikro skaičiaus, ne didesnio nei 2561024.
Bet parašykime programą Python, kuri sugeneruoja visus įmanomus kilobaitų tekstus, paleidžia juos vykdyti, o jei išveda skaičių, tada įtraukia šį skaičių į pasiekiamų žodyną. Patikrinusi visas 2561024 XNUMX XNUMX galimybes, nesvarbu, kiek tai užtruktų, programa ieško mažiausio žodyne trūkstamo skaičiaus ir išspausdina tą skaičių. Atrodo akivaizdu, kad tokia programa tilps į kilobaitą kodo ir išves tą patį skaičių, kurio negali išvesti kilobaito programa!
Koks laimikis dabar? To nebegalima sieti su užrašo neformalumu!
Jei jus glumina tai, kad mūsų programai reikės astronominės atminties – 2561024 elementų žodyno (arba bitų masyvo), tuomet tą patį galite padaryti ir be jo: kiekvienam iš 2561024 skaičių savo ruožtu. , pereikite visas 2561024 galimas programas, kol neatsiras tinkamos. Nesvarbu, kad tokia paieška truks labai ilgai: patikrinus mažiau nei (2561024)2 poras iš skaičiaus ir programos, ji baigsis ir ras tą labai branginamą skaičių.
O gal nesibaigs? Iš tiesų, tarp visų programų, kurios bus išbandytos, bus while True: pass (ir jos funkciniai analogai) – ir reikalas neapsiribos tik tokios programos išbandymu!
Skirtingai nuo Berry paradokso, kai sugautas žymėjimo neformalumas, antruoju atveju turime gerai užmaskuotą formuluotę. . Faktas yra tas, kad neįmanoma nustatyti jos išvesties iš programos per ribotą laiką. Visų pirma, Kolmogorovo sudėtingumas : nėra algoritmo, kuris leistų konkrečiam skaičiui rasti trumpiausios programos, kuri spausdina šį skaičių, ilgį; o tai reiškia, kad nėra Berry problemos sprendimo – surasti trumpiausio žodinio pavadinimo ilgį tam tikram skaičiui.
Šaltinis: www.habr.com