Масъалаи фишурдани додаҳо, дар шакли соддатаринаш, метавонад ба рақамҳо ва аломатҳои онҳо алоқаманд бошад. Рақамҳоро бо рақамҳо ифода кардан мумкин аст ("ёздаҳ" барои рақами 11), ифодаҳои математикӣ ("ду дар бистум" барои 1048576), ифодаҳои сатр ("панҷ нӯҳ" барои 99999), номҳои хос ("шумораи ҳайвони ваҳшӣ" барои 666, "соли марги Тюринг" барои соли 1954) ё комбинатсияи худсаронаи он. Ҳама гуна нишона мувофиқ аст, ки тавассути он ҳамсӯҳбат метавонад ба таври возеҳ муайян кунад, ки мо дар бораи кадом рақам гап мезанем. Аён аст, ки ба хамсухбататон гуед "фактори ҳашт" нисбат ба қайди муодил самараноктар аст "чил ҳазору сесаду бист". Дар ин ҷо саволи мантиқӣ ба миён меояд: кӯтоҳтарин аломати рақами додашуда кадом аст?
Файласуф Бертран Рассел дар соли 1908 нашр кардааст , ки ба масъалаи сабти рақамҳо аз тарафи муқобил дахл мекунад: Шумораи хурдтарине, ки ҳаштод ҳарфро талаб намекунад, кадом аст?
Чунин рақам бояд вуҷуд дошта бошад: аз ҳаштод ҳарф ва фосилаи русӣ шумо метавонед танҳо 3480 аломатро ташкил диҳед, яъне бо истифода аз ҳаштод ҳарф шумо метавонед на бештар аз 3480 рақамро таъин кунед. Ин маънои онро дорад, ки бо ин роҳ рақами муайянро на бештар аз 3480 таъин кардан ғайриимкон аст.
Ин маънои онро дорад, ки ин рақам ба таъинот мувофиқат мекунад "камтарин адад, ки барои он ҳаштод ҳарф кофӣ нест", ки хамагй 78 харф дорад! Аз як тараф, ин рақам бояд вуҷуд дошта бошад; аз тарафи дигар, агар ин рақам вуҷуд дошта бошад, пас таъини он ба он мувофиқат намекунад. Парадокс!
Роҳи осонтарини рад кардани ин парадокс ин истинод ба ғайрирасмии қайдҳои шифоҳӣ мебошад. Мисли, агар танҳо маҷмӯи мушаххаси ифодаҳо дар қайд иҷозат дода шуда бошад, пас "камтарин адад, ки барои он ҳаштод ҳарф кофӣ нест" аломати эътиборнок нахоҳад буд, дар ҳоле ки қайдҳои амалан муфид ба монанди "фактори ҳашт" қобили қабул боқӣ мемонад.
Оё роҳҳои расмии тавсифи пайдарпаии (алгоритм) амалҳо дар рақамҳо вуҷуд доранд? Ҳастанд ва фаровонӣ - онҳоро забонҳои барномасозӣ меноманд. Ба ҷои қайдҳои шифоҳӣ, мо барномаҳоеро истифода мебарем (масалан, дар Python), ки рақамҳои заруриро нишон медиҳанд. Масалан, барои панч нух программа мувофик аст print("9"*5). Мо минбаъд низ ба барномаи кӯтоҳтарин барои рақами додашуда таваҷҷӯҳ хоҳем кард. Дарозии чунин барнома номида мешавад рақамҳо; он маҳдудияти назариявӣ мебошад, ки ба он адад фишурда мешавад.
Ба ҷои парадокси Берри, мо метавонем як чизи шабеҳро баррасӣ кунем: Кадом адад хурдтарин аст, ки як барномаи килобайт барои баровардан кифоя нест?
Мо мисли пештара фикр мекунем: 2561024 матни килобайт мавҷуд аст, яъне аз рӯи барномаҳои килобайтӣ на бештар аз 2561024 рақам бароварда мешавад. Ин маънои онро дорад, ки шумораи муайяни на бештар аз 2561024 бо ин роҳ ба даст овардан мумкин нест.
Аммо биёед дар Python барномае бинависем, ки ҳамаи матнҳои имконпазири килобайтро тавлид кунад, онҳоро барои иҷро иҷро кунад ва агар онҳо рақаме бароваранд, пас ин рақамро ба луғати матнҳои дастрас илова мекунад. Пас аз санҷидани ҳамаи 2561024 имконот, новобаста аз он ки ин чӣ қадар вақт мегирад, барнома хурдтарин адади дар луғат нопадидшударо меҷӯяд ва ин рақамро чоп мекунад. Чунин ба назар мерасад, ки чунин барнома ба як килобайт рамз мувофиқат мекунад ва ҳамон рақамеро мебарорад, ки бо як барномаи килобайтӣ бароварда намешавад!
Ҳоло дар чист? Онро дигар ба ѓайрирасмии нота рабт додан мумкин нест!
Агар шумо аз он чизе, ки барои кор кардани барномаи мо миқдори астрономии хотира - луғат (ё массиви бит) аз 2561024 элементро талаб мекунад, ошуфта бошед, пас шумо метавонед бе он ҳамон корро иҷро кунед: барои ҳар як рақами 2561024, дар навбати худ. , аз тамоми 2561024 барномаҳои имконпазир гузаред, то он даме, ки ягон барномаи мувофиқ вуҷуд надорад. Муҳим нест, ки чунин ҷустуҷӯ муддати хеле тӯлонӣ давом мекунад: пас аз тафтиши камтар аз (2561024)2 ҷуфт аз рақам ва барнома, он ба охир мерасад ва он рақами хеле азизро меёбад.
Ё тамом намешавад? Дар ҳақиқат, дар байни ҳамаи барномаҳое, ки санҷида мешаванд, хоҳанд буд while True: pass (ва аналогҳои функсионалии он) - ва масъала аз озмоиши чунин барнома дигар нахоҳад рафт!
Баръакси парадокси Берри, ки дар он ҷо сайд дар ғайрирасмии қайд буд, дар ҳолати дуюм мо ислоҳоти хуб пинҳоншуда дорем. . Гап дар сари он аст, ки натицаи онро аз як программа дар як муддати муайян муайян кардан мумкин нест. Махсусан, мураккабии Колмогоров : ягон алгоритме вуҷуд надорад, ки барои рақами додашуда дарозии барномаи кӯтоҳтаринро, ки ин рақамро чоп мекунад, пайдо кунад; ки ин маънои онро дорад, ки ҳалли масъалаи Берри вуҷуд надорад - барои ёфтани дарозии кӯтоҳтарин нишонаи шифоҳӣ барои рақами додашуда.
Манбаъ: will.com