Мәліметтерді қысу мәселесі қарапайым түрде сандарға және олардың белгілеріне қатысты болуы мүмкін. Сандарды сандармен белгілеуге болады («он бір» 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 (және оның функционалдық аналогтары) - және мәселе мұндай бағдарламаны тестілеуден ары қарай кетпейді!
Берридің парадоксынан айырмашылығы, бұл жерде нотаның бейресми болуы, екінші жағдайда бізде жақсы жасырылған реформуляция бар. . Өйткені, бағдарламадан оның нәтижесін шектеулі уақыт ішінде анықтау мүмкін емес. Атап айтқанда, Колмогоров күрделілігі : берілген сан үшін осы санды басып шығаратын ең қысқа бағдарламаның ұзындығын табуға мүмкіндік беретін алгоритм жоқ; бұл Берри мәселесінің шешімі жоқ дегенді білдіреді - берілген сан үшін ең қысқа ауызша белгілеудің ұзындығын табу.
Ақпарат көзі: www.habr.com