Маалыматтарды кысуу маселеси эң жөнөкөй түрдө сандарга жана алардын белгилерине тиешелүү болушу мүмкүн. Сандарды цифралар менен белгилесе болот ("он бир" 11 саны үчүн), математикалык туюнтмалар ("Жыйырманчы эки" 1048576 үчүн), сап туюнтмалары ("беш тогуз" 99999 үчүн), энчилүү ысымдар ("жырткычтын саны" 666 үчүн "Тюрингдин өлгөн жылы" 1954-жылга), же алардын ыктыярдуу комбинациялары. Ар кандай белги ылайыктуу, анын жардамы менен маектешибиз кайсы номер жөнүндө сөз болуп жатканын так аныктай алат. Албетте, маектешиңизге айтыңыз "сегиздин факториалы" эквиваленттүү белгилерге караганда натыйжалуураак "кырк миң үч жүз жыйырма". Бул жерде логикалык суроо туулат: берилген сан үчүн эң кыска белги деген эмне?
Философ Бертран Рассел 1908-жылы жарык көргөн , карама-каршы тараптан сандарды белгилөө маселесин козгойт: Сексен тамганы талап кылбаган эң кичине сан кайсы?
Мындай сан болушу керек: сексен орус тамгасынан жана боштуктан сиз болгону 3480 белгини түзө аласыз, бул сексен тамганы колдонуу менен 3480ден ашык эмес санды белгилей аласыз дегенди билдирет. Бул 3480ден ашпаган белгилүү бир санды ушундай жол менен белгилөө мүмкүн эмес дегенди билдирет.
Бул бул сан белгилөө туура келет дегенди билдирет "сексен тамга жетишсиз болгон эң кичине сан", анда 78 гана тамга бар! Бир жагынан, бул сан болушу керек; экинчи жагынан, бул сан бар болсо, анда анын белгилениши ага туура келбейт. Парадокс!
Бул парадоксту жокко чыгаруунун эң оңой жолу - вербалдык белгилердин формалдуу эместигине шилтеме кылуу. Белгилөөдө атайын аныкталган туюнтмалардын топтомуна гана уруксат берилген болсо, анда "сексен тамга жетишсиз болгон эң кичине сан" жарактуу белги болбойт, ал эми иш жүзүндө пайдалуу белгилер сыяктуу "сегиздин факториалы" алгылыктуу бойдон кала берет.
Сандардагы аракеттердин ырааттуулугун (алгоритмин) сүрөттөөнүн формалдуу жолдору барбы? Бар, жана көп - алар программалоо тилдери деп аталат. Оозеки белгилердин ордуна биз керектүү сандарды көрсөткөн программаларды (мисалы, Python тилинде) колдонобуз. Мисалы, беш тогуз үчүн программа ылайыктуу print("9"*5). Берилген номер үчүн эң кыска программага кызыгууну улантабыз. Мындай программанын узактыгы деп аталат сандар; бул берилген санды кысылышы мүмкүн болгон теориялык чек.
Берринин парадоксунун ордуна, биз ушуга окшошту карап көрсөк болот: Килобайттык программа чыгарууга жетпей турган эң кичине сан кайсы?
Биз мурункудай эле ой жүгүртөбүз: 2561024 килобайт тексттер бар, бул килобайттык программалар менен 2561024 сандан ашык эмес санды чыгарууга болбойт дегенди билдирет. Бул 2561024дөн ашпаган белгилүү бир санды ушундай жол менен алуу мүмкүн эмес дегенди билдирет.
Бирок келгиле, Python тилинде бардык мүмкүн болгон килобайттык тексттерди түзгөн программаны жазып көрөлү, аларды аткаруу үчүн иштетет жана эгер алар бир санды чыгарса, анда бул санды жеткиликтүү болгондордун сөздүгүнө кошот. Бардык 2561024 XNUMX XNUMX мүмкүнчүлүктү текшергенден кийин, канча убакыт талап кылынбасын, программа сөздүктө жок эң кичине санды издеп, ошол санды басып чыгарат. Мындай программа бир килобайт кодго туура келери анык көрүнөт - жана килобайттык программа чыгара албаган санды чыгарат!
Эми эмне болду? Аны мындан ары ноталардын формалдуу эместигине байланыштырууга болбойт!
Эгерде сиз биздин программанын иштеши үчүн астрономиялык көлөмдөгү эстутумду талап кыла тургандыгы менен чаташтырсаңыз - 2561024 элементтерден турган сөздүк (же бит массиви) - анда сиз ансыз да ошол эле нерсени жасай аласыз: 2561024 сандын ар бири үчүн, өз кезегинде , 2561024 мүмкүн болгон бардык программаларды аралап өтүңүз, ылайыктуу программа жок болмоюнча. Мындай издөө өтө көпкө созула турганы маанилүү эмес: номерден жана программадан (2561024) 2 жуптан азын текшергенден кийин, ал бүтүп, ошол абдан кымбат санды табат.
Же бүтпөйбү? Чынында эле, сыналган бардык программалардын арасында болот while True: pass (жана анын функционалдык аналогдору) - жана маселе мындай программаны сыноодон ары кетпейт!
Берринин парадоксунан айырмаланып, ноталардын формалдуу эместигинде кармалып калган, экинчи учурда бизде жакшы жашырылган реформуляция бар. . Чындыгында, программадан анын натыйжасын чектүү убакытта аныктоо мүмкүн эмес. Атап айтканда, Kolmogorov татаалдыгы : берилген сан үчүн бул санды басып чыгарган эң кыска программанын узундугун табууга мүмкүндүк бере турган алгоритм жок; бул Берринин көйгөйүнө эч кандай чечим жок дегенди билдирет - берилген сан үчүн эң кыска оозеки белгинин узундугун табуу.
Source: www.habr.com