Iṣoro ti funmorawon data, ni ọna ti o rọrun julọ, le ni ibatan si awọn nọmba ati awọn akiyesi wọn. Awọn nọmba le jẹ itọkasi nipasẹ awọn nọmba (" mọkanla" fun nọmba 11), awọn ikosile mathematiki ("meji ninu ogun" fun 1048576), awọn ikosile okun ("mẹsan marun" fun 99999), awọn orukọ to dara ("nọmba ti ẹranko" fun 666, "Ọdun ti iku Turing" fun 1954), tabi awọn akojọpọ lainidii rẹ. Eyikeyi yiyan ni o dara nipasẹ eyiti interlocutor le pinnu kedere nọmba wo ni a n sọrọ nipa. O han ni, sọ fun interlocutor rẹ "ipin ti mẹjọ" daradara siwaju sii ju deede amiakosile "XNUMX". Ibeere ọgbọn kan dide nibi: kini ami akiyesi kukuru fun nọmba ti a fun?
Onímọ̀ ọgbọ́n orí Bertrand Russell tí a tẹ̀ jáde ní 1908 , eyi ti o fọwọkan lori ọrọ akiyesi nọmba lati apa idakeji: Kini nọmba ti o kere julọ ti ko nilo awọn lẹta ọgọrin?
Iru nọmba kan gbọdọ wa: lati ọgọrin awọn lẹta Russian ati awọn alafo o le ṣe awọn orukọ 3480 nikan, eyiti o tumọ si pe lilo awọn lẹta ọgọrin o ko le yan awọn nọmba 3480 ko ju 3480 lọ. Eyi tumọ si pe ko ṣee ṣe lati yan nọmba kan ko ju XNUMX lọ ni ọna yii.
Eyi tumọ si pe nọmba yii yoo ni ibamu si yiyan "nọmba ti o kere julọ fun eyiti awọn lẹta ọgọrin ko to", ti o ni awọn lẹta 78 nikan! Ni apa kan, nọmba yii gbọdọ wa; ni ida keji, ti nọmba yii ba wa, lẹhinna yiyan rẹ ko ni ibamu si rẹ. Paradox!
Ọna to rọọrun lati yọkuro paradox yii ni lati tọka si aibikita ti awọn akiyesi ọrọ-ọrọ. Bii, ti o ba jẹ pe ṣeto awọn asọye ni pato ni a gba laaye ninu ami akiyesi, lẹhinna "nọmba ti o kere julọ fun eyiti awọn lẹta ọgọrin ko to" kii yoo jẹ akọsilẹ ti o wulo, lakoko ti o wulo awọn ami akiyesi bi "ipin ti mẹjọ" yoo wa ni itẹwọgba.
Ṣe awọn ọna deede wa lati ṣe apejuwe lẹsẹsẹ (algoridimu) ti awọn iṣe lori awọn nọmba? Nibẹ ni o wa, ati ni ọpọlọpọ - wọn pe wọn ni awọn ede siseto. Dipo awọn akiyesi ọrọ, a yoo lo awọn eto (fun apẹẹrẹ, ni Python) ti o ṣafihan awọn nọmba ti o nilo. Fun apẹẹrẹ, fun mẹsan marun ni eto naa dara print("9"*5). A yoo tẹsiwaju lati nifẹ ninu eto ti o kuru ju fun nọmba ti a fun. Awọn ipari ti iru eto ni a npe ni awọn nọmba; o jẹ awọn tumq si iye to eyi ti a fi fun nọmba le wa ni fisinuirindigbindigbin.
Dipo paradox Berry, a le ronu iru kan bayi: Kini nọmba ti o kere julọ ti eto kilobyte ko to lati jade?
A yoo ronu ni ọna kanna bi iṣaaju: awọn ọrọ kilobyte 2561024 wa, eyiti o tumọ si pe ko si ju awọn nọmba 2561024 le ṣejade nipasẹ awọn eto kilobyte. Eyi tumọ si pe nọmba kan ti ko tobi ju 2561024 ko le ṣe jade ni ọna yii.
Ṣugbọn jẹ ki a kọ eto kan ni Python ti o ṣe gbogbo awọn ọrọ kilobyte ti o ṣeeṣe, ṣiṣe wọn fun ipaniyan, ati pe ti wọn ba jade nọmba kan, lẹhinna ṣafikun nọmba yii si iwe-itumọ ti awọn ti o le de ọdọ. Lẹhin ti ṣayẹwo gbogbo awọn aye 2561024, laibikita bi o ṣe pẹ to, eto naa n wa nọmba ti o kere julọ ti o padanu lati iwe-itumọ ati tẹ nọmba naa. O dabi ẹnipe o han gbangba pe iru eto kan yoo baamu si koodu kilobyte kan - yoo si jade nọmba pupọ ti ko le ṣejade nipasẹ eto kilobyte kan!
Kini apeja ni bayi? O le ko to gun wa ni Wọn si awọn informality ti awọn amiakosile!
Ti o ba ni idamu nipasẹ otitọ pe eto wa yoo nilo iye oye astronomical ti iranti lati ṣiṣẹ - iwe-itumọ (tabi orun bit) ti awọn eroja 2561024 - lẹhinna o le ṣe ohun kanna laisi rẹ: fun ọkọọkan awọn nọmba 2561024, ni titan. , lọ nipasẹ gbogbo awọn eto 2561024 ti o ṣeeṣe, titi ko si ọkan ti o yẹ. Ko ṣe pataki pe iru wiwa bẹẹ yoo ṣiṣe ni pipẹ pupọ: lẹhin ti ṣayẹwo kere ju (2561024) awọn orisii 2 lati nọmba ati eto naa, yoo pari ati rii nọmba ti o nifẹ pupọ.
Tabi ki yoo pari? Lootọ, laarin gbogbo awọn eto ti yoo gbiyanju, yoo wa while True: pass (ati awọn analogues iṣẹ rẹ) - ati pe ọrọ naa kii yoo lọ siwaju ju idanwo iru eto kan lọ!
Ko dabi paradox Berry, nibiti apeja naa wa ninu alaye ti akiyesi, ninu ọran keji a ni atunṣe ti o farapamọ daradara. . Otitọ ni pe ko ṣee ṣe lati pinnu abajade rẹ lati inu eto ni akoko ipari. Ni pato, Kolmogorov complexity : ko si algorithm ti yoo gba laaye, fun nọmba ti a fun, lati wa ipari ti eto ti o kuru ju ti o tẹ nọmba yii; eyiti o tumọ si pe ko si ojutu si iṣoro Berry - lati wa ipari ti yiyan ọrọ sisọ kukuru fun nọmba ti a fifun.
orisun: www.habr.com