ဒေတာချုံ့ခြင်းဆိုင်ရာ ဝိရောဓိများ

၎င်း၏ အရိုးရှင်းဆုံးပုံစံဖြင့် ဒေတာချုံ့ခြင်းပြဿနာသည် နံပါတ်များနှင့် ၎င်းတို့၏ မှတ်စုများနှင့် ဆက်စပ်နိုင်သည်။ နံပါတ်များကို ဂဏန်းများဖြင့် ကိုယ်စားပြုနိုင်သည် ("ဆယ့်တစ်" နံပါတ် ၁၁ အတွက်) သင်္ချာအသုံးအနှုန်းများ ("နှစ်ဆယ်မှာ နှစ်ယောက်" 1048576 အတွက်)၊ string expressions ("ငါးကိုး" 99999 အတွက်) သင့်လျော်သောအမည်များ ("သားရဲအရေအတွက်" ၆၆၆၊ "Turing ကွယ်လွန်သည့်နှစ်" 1954) သို့မဟုတ် ၎င်းတို့ကို မတရားပေါင်းစပ်မှု။ စကားဝိုင်းသည် ကျွန်ုပ်တို့ပြောနေသည့် နံပါတ်ကို ပြတ်ပြတ်သားသား ဆုံးဖြတ်နိုင်သောကြောင့် မည်သည့် သတ်မှတ်ချက်မဆို သင့်လျော်ပါသည်။ ရှင်းပါတယ်၊ သင့်ချစ်သူကို ပြောပြပါ။ "ရှစ်ရုံ" ညီမျှသော အမှတ်အသားထက် ပိုထိရောက်သည်။ "လေးသောင်းသုံးရာနှစ်ဆယ်". ဤနေရာတွင် ယုတ္တိကျသောမေးခွန်းတစ်ခု ပေါ်လာသည်- ပေးထားသောနံပါတ်အတွက် အတိုဆုံးအမှတ်အသားမှာ အဘယ်နည်း။

ဒဿနပညာရှင် Bertrand Russell သည် ၁၉၀၈ ခုနှစ်တွင် ထုတ်ဝေခဲ့သည်။ "ဘယ်ရီရဲ့ ဝိရောဓိ"ဆန့်ကျင်ဘက်ဘက်မှ ကိန်းဂဏန်းအမှတ်အသား ပြဿနာနှင့် ပတ်သက်သော၊ စာလုံး ရှစ်ဆယ် မလိုအပ်သော အသေးငယ်ဆုံးနံပါတ်ကား အဘယ်နည်း။
ထိုသို့သော ဂဏန်းများ ရှိရမည်- ရုရှားစာလုံး ရှစ်ဆယ်နှင့် နေရာလွတ်များမှ 3480 ဒီဇိုင်းများကိုသာ ဖန်တီးနိုင်သည်၊ ဆိုလိုသည်မှာ စာလုံးရှစ်ဆယ်ကို အသုံးပြု၍ နံပါတ် 3480 ထက်မပိုဘဲ သတ်မှတ်နိုင်သည်။ ဆိုလိုသည်မှာ ဤနည်းဖြင့် 3480 ထက်မပိုသော နံပါတ်တစ်ခုကို သတ်မှတ်ရန် မဖြစ်နိုင်ကြောင်း ဆိုလိုသည်။

ဆိုလိုသည်မှာ ဤနံပါတ်သည် သတ်မှတ်ခြင်းနှင့် ကိုက်ညီမည်ဖြစ်သည်။ "အက္ခရာရှစ်ဆယ်မပြည့်မီ အငယ်ဆုံးနံပါတ်"စာလုံး 78 လုံးသာရှိသည်။ တစ်ဖက်တွင်၊ ဤနံပါတ်ရှိရမည်။ အခြားတစ်ဖက်တွင်၊ ဤနံပါတ်ရှိပါက၊ ၎င်း၏သတ်မှတ်ချက်သည် ၎င်းနှင့်မကိုက်ညီပါ။ ဝိရောဓိ!

ဤဝိရောဓိကို ပယ်ရန် အလွယ်ဆုံးနည်းလမ်းမှာ နှုတ်ဖြင့် မှတ်ချက်များကို အလွတ်သဘော ရည်ညွှန်းခြင်း ဖြစ်သည်။ အကယ်၍ အဓိပ္ပါယ်ဖွင့်ဆိုချက်တွင် အတိအကျသတ်မှတ်ထားသော အသုံးအနှုန်းများကိုသာ ခွင့်ပြုပါက၊ "အက္ခရာရှစ်ဆယ်မပြည့်မီ အငယ်ဆုံးနံပါတ်" မှန်ကန်သော မှတ်စုများ မဟုတ်သော်လည်း လက်တွေ့တွင် အသုံးဝင်သော မှတ်စုများ ဖြစ်သည်။ "ရှစ်ရုံ" လက်ခံနိုင်ဖွယ်ရှိနေပါမည်။

ကိန်းဂဏာန်းများပေါ်တွင် လုပ်ဆောင်မှုများ၏ အစီအစဥ် (algorithm) ကို ဖော်ပြရန် တရားဝင်နည်းလမ်းများ ရှိပါသလား။ ပရိုဂရမ်းမင်းဘာသာစကားများဟု ခေါ်သည် ။ နှုတ်ဖြင့်အမှတ်အသားများအစား၊ လိုအပ်သောနံပါတ်များကိုပြသသည့်ပရိုဂရမ်များ (ဥပမာ Python တွင်) ကိုအသုံးပြုပါမည်။ ဥပမာအားဖြင့်၊ ကိုးကိုးငါးခုအတွက် အစီအစဉ်သည် သင့်လျော်သည်။ print("9"*5). ပေးထားသောနံပါတ်အတွက် အတိုဆုံးအစီအစဉ်ကို ကျွန်ုပ်တို့ ဆက်လက်စိတ်ဝင်စားပါမည်။ ထိုကဲ့သို့သော program ၏အရှည်ကိုခေါ်သည်။ Kolmogorov ရှုပ်ထွေးမှု နံပါတ်များ; ၎င်းသည် ပေးထားသော နံပါတ်တစ်ခုကို ချုံ့နိုင်သည့် သီအိုရီကန့်သတ်ချက်ဖြစ်သည်။

Berry ၏ ဝိရောဓိဖြစ်မည့်အစား၊ ယခု ကျွန်ုပ်တို့သည် အလားတူတစ်ခုကို စဉ်းစားနိုင်သည်- ကီလိုဘိုက်ပရိုဂရမ်တစ်ခုသည် ထုတ်ပေးရန် မလုံလောက်သော အသေးငယ်ဆုံးနံပါတ်ကား အဘယ်နည်း။

ကျွန်ုပ်တို့သည် ယခင်နည်းအတိုင်း ကျိုးကြောင်းဆင်ခြင်ပါမည်- 2561024 ကီလိုဘိုက် စာသားများ ရှိသည်၊ ဆိုလိုသည်မှာ 2561024 ထက်ပိုသော ဂဏန်းများကို ကီလိုဘိုက်ပရိုဂရမ်များဖြင့် ထုတ်ပေးနိုင်သည်။ ဆိုလိုသည်မှာ 2561024 ထက်မကြီးသော အချို့သောနံပါတ်ကို ဤနည်းဖြင့် ဆင်းသက်နိုင်မည်မဟုတ်ပေ။

ဒါပေမယ့် ဖြစ်နိုင်ချေရှိတဲ့ ကီလိုဘိုက်စာသားတွေအားလုံးကို ထုတ်ပေးတဲ့ Python မှာ ပရိုဂရမ်တစ်ခု ရေးလိုက်ရအောင်၊ အကောင်အထည်ဖော်ဖို့ လုပ်ဆောင်ပေးတယ်၊ ပြီးတော့ နံပါတ်တစ်ခုထုတ်ရင်၊ အဲဒီနံပါတ်ကို လက်လှမ်းမှီနိုင်သူတွေရဲ့ အဘိဓာန်မှာ ပေါင်းထည့်လိုက်ရအောင်။ ဖြစ်နိုင်ခြေ 2561024 အားလုံးကို စစ်ဆေးပြီးနောက် အချိန်မည်မျှပင်ကြာစေကာမူ ပရိုဂရမ်သည် အဘိဓာန်မှ ပျောက်ဆုံးနေသော အသေးငယ်ဆုံးနံပါတ်ကို ရှာဖွေကာ ထိုနံပါတ်ကို ရိုက်နှိပ်သည်။ ထိုသို့သော ပရိုဂရမ်သည် ကုဒ်၏ ကီလိုဘိုက်သို့ လိုက်လျောညီထွေဖြစ်ပုံရသည် - နှင့် ကီလိုဘိုက်ပရိုဂရမ်မှ ထုတ်ပေး၍မရသော အရေအတွက်ကို ထုတ်ပေးလိမ့်မည် ။

အခုဖမ်းတာ ဘာလဲ။ ၎င်းသည် သင်္ကေတ၏ အလွတ်သဘောကြောင့်ဟု သတ်မှတ်၍ မရတော့ပါ။

ကျွန်ုပ်တို့၏ ပရိုဂရမ်သည် အလုပ်လုပ်ရန် နက္ခတ်ဗေဒင်ဆိုင်ရာ မှတ်ဉာဏ်ပမာဏ လိုအပ်မည်ဟူသောအချက်ကြောင့် သင်ရှုပ်ထွေးနေပါက ဒြပ်စင် 2561024 ၏ အဘိဓာန် (သို့မဟုတ် ဘစ် ခင်းကျင်းခြင်း) - ထို့နောက် ၎င်းမပါဘဲ တူညီသောအရာကို သင်လုပ်ဆောင်နိုင်သည်- 2561024 နံပါတ်တစ်ခုစီအတွက်၊ သင့်လျော်သောတစ်ခုမျှမရှိမချင်း ဖြစ်နိုင်ချေ 2561024 ပရိုဂရမ်အားလုံးကို ဖြတ်သန်းပါ။ ထိုသို့သောရှာဖွေမှုသည် အလွန်ကြာရှည်မည်မှာ အရေးမကြီးပါ- နံပါတ်နှင့် ပရိုဂရမ်မှ အတွဲ (2561024) ထက်နည်းသော အတွဲ (2) တွဲကို စစ်ဆေးပြီးနောက်၊ ၎င်းသည် အဆုံးသတ်ပြီး အလွန်မြတ်နိုးဖွယ်နံပါတ်ကို တွေ့ရှိမည်ဖြစ်သည်။

ဒါမှမဟုတ် မပြီးဘူးလား။ အမှန်တကယ်တော့ ကြိုးစားရမယ့် ပရိုဂရမ်တွေ အားလုံးထဲမှာ ရှိပါလိမ့်မယ်။ while True: pass (၎င်း၏လုပ်ဆောင်နိုင်သော analogues များ) - နှင့်ထိုကဲ့သို့သောပရိုဂရမ်ကိုစမ်းသပ်ခြင်းထက်ထိုကိစ္စသည်ဆက်လက်ရှိမည်မဟုတ်ပါ။

Berry ၏ ဝိရောဓိ နှင့် မတူဘဲ၊ ဖမ်းမိမှုမှာ အလွတ်သဘောဖြင့် ဖော်ပြခြင်းဖြစ်သည်၊ ဒုတိယ ကိစ္စတွင် ကျွန်ုပ်တို့တွင် ကောင်းမွန်သော အသွင်ပြောင်း ပြုပြင်ပြောင်းလဲမှု ရှိသည်၊ "ပြဿနာရပ်များ". အမှန်မှာ ပရိုဂရမ်တစ်ခုမှ ၎င်း၏ output ကို သတ်မှတ်အချိန်အတွင်း ဆုံးဖြတ်ရန် မဖြစ်နိုင်ပေ။ အထူးသဖြင့် Kolmogorov ရှုပ်ထွေးမှု တွက်ချက်လို့မရသော: ပေးထားသော နံပါတ်တစ်ခုအတွက်၊ ဤနံပါတ်ကို ရိုက်နှိပ်သည့် အတိုဆုံး ပရိုဂရမ်၏ အရှည်ကို ရှာဖွေရန် ခွင့်ပြုမည့် algorithm မရှိပါ။ ဆိုလိုသည်မှာ Berry ၏ပြဿနာအတွက် အဖြေမရှိပါ - ပေးထားသောနံပါတ်အတွက် အတိုဆုံးနှုတ်ဖြင့်သတ်မှတ်ခြင်း၏အရှည်ကိုရှာရန်။

source: www.habr.com