Matsalar matse bayanai, a cikin mafi sauƙi, na iya danganta da lambobi da bayanin su. Ana iya nuna lambobi ta lambobi (" sha daya" don lamba 11), maganganun lissafi ("biyu a cikin ashirin" don 1048576), maganganun kirtani ("biyar tara" don 99999), sunaye masu dacewa ("yawan dabba" da 666, "shekarar mutuwar Turing" don 1954), ko haɗuwa ta sabani. Duk wani nadi ya dace da wanda mai shiga tsakani zai iya tantance adadin da muke magana akai. Babu shakka, gaya wa mai magana da ku "factorial na takwas" mafi inganci fiye da daidai bayanin "dubu arba'in da dari uku da ashirin". Tambaya mai ma'ana ta taso a nan: menene mafi guntu bayanin lamba ga lambar da aka bayar?
Masanin falsafa Bertrand Russell ya buga a 1908 , wanda ya tabo batun bayanin lamba ta bangaren kishiyar: Menene mafi ƙarancin lamba wanda baya buƙatar haruffa tamanin?
Dole ne irin wannan lambar ta kasance: daga haruffa tamanin na Rashanci da sarari za ku iya yin zane-zane 3480 kawai, wanda ke nufin cewa ta amfani da haruffa tamanin ba za ku iya zayyana lambobi sama da 3480 ba. Wannan yana nufin cewa ba zai yiwu a ƙididdige takamaiman lamba ba fiye da 3480 ta wannan hanyar.
Wannan yana nufin cewa wannan lambar zata dace da nadi "mafi ƙarancin lamba wanda haruffa tamanin basu isa ba", wanda ke da haruffa 78 kawai! A gefe guda, dole ne wannan lamba ta kasance; a daya bangaren, idan wannan lamba ta kasance, to nadinsa bai dace da shi ba. Paradox!
Hanya mafi sauƙi don watsi da wannan sabani shine koma zuwa ga rashin fahimtar bayanan kalmomi. Kamar, idan kawai an ba da izinin saitin maganganu na musamman a cikin bayanin, to "mafi ƙarancin lamba wanda haruffa tamanin basu isa ba" ba zai zama ingantacciyar sanarwa ba, yayin da a zahiri bayanan bayanai masu amfani kamar "factorial na takwas" zai kasance karbuwa.
Shin akwai hanyoyi na yau da kullun don bayyana jerin (algorithm) na ayyuka akan lambobi? Akwai, kuma a yalwace - ana kiran su programming languages. Maimakon maganganun magana, za mu yi amfani da shirye-shirye (misali, a Python) waɗanda ke nuna lambobin da ake buƙata. Misali, na tara tara shirin ya dace print("9"*5). Za mu ci gaba da sha'awar mafi guntu shirin don lambar da aka ba. Ana kiran tsawon irin wannan shirin lambobi; shi ne ƙayyadaddun ka'idar da za a iya matsa lamba da aka ba shi.
Maimakon ɓacin rai na Berry, yanzu zamu iya yin la'akari da irin wannan: Menene mafi ƙarancin lamba wanda shirin kilobyte bai isa ya fitar ba?
Za mu yi tunani kamar yadda ya gabata: akwai rubutun kilobyte 2561024, wanda ke nufin cewa ba za a iya fitar da lambobi sama da 2561024 ta shirye-shiryen kilobyte ba. Wannan yana nufin cewa ba za a iya samun takamaiman lamba da bai wuce 2561024 ba ta wannan hanyar.
Amma bari mu rubuta wani shiri a cikin Python wanda ke samar da duk rubutun kilobyte mai yuwuwa, gudanar da su don aiwatarwa, kuma idan sun fitar da lamba, to sai a ƙara wannan lamba a cikin ƙamus na masu iya isa. Bayan an bincika duk damar 2561024, komai tsawon lokacin da ya ɗauka, shirin yana neman mafi ƙarancin lambar da ya ɓace daga ƙamus kuma ya buga wannan lambar. Yana da alama cewa irin wannan shirin zai shiga cikin lambar kilobyte - kuma zai fitar da ainihin lambar da ba za a iya fitar da shi ta hanyar shirin kilobyte ba!
Menene kama yanzu? Ba za a iya dangana shi ga rashin sanin ƙa'idar ba!
Idan kun damu da gaskiyar cewa shirinmu zai buƙaci adadin ƙwaƙwalwar sararin samaniya don aiki - ƙamus (ko bit array) na abubuwan 2561024 - to, zaku iya yin abu iri ɗaya ba tare da shi ba: ga kowane lambobi 2561024, bi da bi. , Shiga cikin duk shirye-shiryen 2561024 da za a iya yi, har sai babu wanda ya dace. Ba kome ba cewa irin wannan binciken zai ɗauki lokaci mai tsawo: bayan duba ƙasa da (2561024) 2 nau'i-nau'i daga lambar da shirin, zai ƙare kuma ya sami lambar da ake so.
Ko ba zai kare ba? Lallai, a cikin dukkan shirye-shiryen da za a gwada, za a samu while True: pass (da kuma analogues na aikin sa) - kuma al'amarin ba zai wuce gwajin irin wannan shirin ba!
Ba kamar Paradox na Berry ba, inda kama ya kasance a cikin rashin daidaituwa na bayanin, a cikin akwati na biyu muna da sake fasalin da aka ɓoye. . Gaskiyar ita ce, ba shi yiwuwa a tantance fitar da shi daga shirin a cikin ƙayyadadden lokaci. Musamman, Kolmogorov hadaddun : babu wani algorithm wanda zai ba da damar, don lambar da aka ba, don gano tsawon mafi guntu shirin da ke buga wannan lambar; wanda ke nufin babu mafita ga matsalar Berry - don nemo tsayin mafi guntuwar magana da aka ba da lamba.
source: www.habr.com