တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်တစ်ခုသည် တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီအရ၊ algorithm ဖြင့် ထိရောက်စွာ တွက်ချက်နိုင်သည့် လုပ်ဆောင်ချက်ကို ရည်ညွှန်းသည်။ ၎င်းသည် ကွန်ပြူတာသိပ္ပံနယ်ပယ်တွင် အခြေခံသဘောတရားတစ်ခုဖြစ်ပြီး တွက်ချက်မှု၏ကန့်သတ်ချက်များကိုနားလည်ရန် အရေးကြီးသောအခန်းကဏ္ဍမှပါဝင်ပါသည်။
တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်ကို သတ်မှတ်ရန်၊ ကျွန်ုပ်တို့သည် တွက်ချက်မှုဆိုင်ရာ မော်ဒယ်များ၏ စွမ်းဆောင်ရည်နှင့် ကန့်သတ်ချက်များကို ကျိုးကြောင်းဆင်ခြင်နိုင်စေမည့် တရားဝင်မူဘောင်တစ်ခုကို တည်ထောင်ရန် လိုအပ်ပါသည်။ ထိုကဲ့သို့သော မူဘောင်တစ်ခုမှာ ၁၉၃၆ ခုနှစ်တွင် Alan Turing မှ မိတ်ဆက်ခဲ့သည့် Turing စက်ဖြစ်သည်။ Turing စက်သည် ဆဲလ်များ ပိုင်းခြားထားသော တိပ်ခွေ၊ ဖတ်စာရေးခေါင်းနှင့် ပြည်နယ်များ ပါဝင်သော စိတ္တဇသင်္ချာပုံစံတစ်ခုဖြစ်သည်။ စက်သည် လက်ရှိဆဲလ်ပေါ်ရှိ သင်္ကေတကို ဖတ်ရှုကာ၊ လက်ရှိအခြေအနေနှင့် သင်္ကေတကို အခြေခံ၍ အခြေအနေအသစ်သို့ ကူးပြောင်းကာ လက်ရှိဆဲလ်ရှိ သင်္ကေတကို မွမ်းမံခြင်းဖြင့် လုပ်ဆောင်သည်။ ၎င်းသည် read-write head ကို ဆဲလ်တစ်ခုအား ဘယ် သို့မဟုတ် ညာဘက်သို့ ရွှေ့နိုင်သည်။
Turing machines ၏အခြေအနေတွင်၊ computable function ကို Turing machine တစ်ခုရှိနေသည့် function တစ်ခုအနေဖြင့်၊ input တစ်ခုခုပေး၍ ရပ်တန့်ကာ ထို input အတွက် မှန်ကန်သော output ကိုထုတ်ပေးသည့် function တစ်ခုအဖြစ် သတ်မှတ်သည်။ တစ်နည်းဆိုရသော် ပေးထားသော ထည့်သွင်းမှုအတွက် ၎င်း၏တန်ဖိုးကို တွက်ချက်နိုင်သော algorithm တစ်ခုရှိလျှင် function တစ်ခုသည် တွက်ချက်နိုင်သည်။ ဤအယူအဆသည် သီးခြားပိုင်ဆိုင်မှုတစ်ခုအား ကျေနပ်မှုရှိမရှိ ဆုံးဖြတ်နိုင်စွမ်းကို ရည်ညွှန်းသည့် ဆုံးဖြတ်ချက်ချနိုင်မှုဆိုင်ရာ အယူအဆနှင့် အနီးကပ်ဆက်စပ်နေသည်။
အချိန် ရှုပ်ထွေးမှု သဘောတရားကို အသုံးပြု၍ တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်များ၏ အယူအဆကို ထပ်မံ၍ တရားဝင် ဖော်ထုတ်နိုင်သည်။ Time complexity သည် input အရွယ်အစား၏ လုပ်ဆောင်မှုအဖြစ် ပြဿနာတစ်ခုကို ဖြေရှင်းရန်အတွက် algorithm တစ်ခုမှ လိုအပ်သော အချိန်ပမာဏကို တိုင်းတာသည်။ input အရွယ်အစားရှိ အဆင့်များစွာတွင် လုပ်ဆောင်ချက်ကို တွက်ချက်နိုင်သော Turing machine တစ်ခုရှိလျှင် လုပ်ဆောင်ချက်တစ်ခုအား polynomial time တွင် တွက်ချက်နိုင်သည်ဟု ဆိုသည်။ Polynomial time computable functions များသည် ၎င်းတို့၏ လည်ပတ်ချိန်အား input အရွယ်အစားဖြင့် ပေါင်း၍ များပြားစွာ ကြီးထွားလာသောကြောင့် ပိုမိုကောင်းမွန်သည်ဟု ယူဆပါသည်။
တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်များ၏ သဘောတရားကို သရုပ်ဖော်ရန်၊ ပေးထားသော နံပါတ်သည် နံပါတ်တစ်ဖြစ်မဖြစ် ဆုံးဖြတ်သည့် လုပ်ဆောင်ချက်ကို သုံးသပ်ကြည့်ကြပါစို့။ ဤ function သည် input n ကိုယူကာ n သည် prime နှင့် false ဖြစ်ပါက true ပြန်ပေးသည်။ Primality Testing Function သည် ပေးထားသော မည်သည့်နံပါတ်၏ Primity ကိုမဆို ဆုံးဖြတ်နိုင်သော Sieve of Eratosthenes ကဲ့သို့သော algorithm တစ်ခုရှိသောကြောင့် တွက်ချက်နိုင်သည်။
ဆန့်ကျင်ဘက်အနေနှင့်၊ ပေးထားသည့် ပရိုဂရမ်တစ်ခုသည် သီးခြားထည့်သွင်းမှုတစ်ခုအပေါ် ရပ်တန့်ခြင်းရှိမရှိ ဆုံးဖြတ်ပေးသည့် လုပ်ဆောင်ချက်ကို ထည့်သွင်းစဉ်းစားပါ။ ရပ်တန့်ခြင်းပြဿနာဟုလူသိများသော ဤလုပ်ဆောင်ချက်သည် တွက်ချက်၍မရပါ။ ဒါကို Diagonalization လို့ခေါ်တဲ့ နည်းပညာကို အသုံးပြုပြီး ၁၉၃၆ ခုနှစ်မှာ Alan Turing က သက်သေပြခဲ့ပါတယ်။ Turing ၏ သက်သေပြချက် အရ ပရိုဂရမ်သည် ရပ်တန့်မည် သို့မဟုတ် ထာဝစဉ် လုပ်ဆောင်မည် ၊ မည်သည့် ပရိုဂရမ် နှင့် ထည့်သွင်းမှုအတွက်မဆို ဆုံးဖြတ်နိုင်သည့် algorithm မရှိနိုင်ကြောင်း ပြသခဲ့သည်။
ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ၏ အခြေအနေတွင် တွက်ချက်နိုင်သော လုပ်ဆောင်မှုတစ်ခုသည် အယ်လဂိုရီသမ်ဖြင့် ထိရောက်စွာ တွက်ချက်နိုင်သည့် လုပ်ဆောင်ချက်ကို ရည်ညွှန်းသည်။ ၎င်းသည် ကွန်ပြူတာသိပ္ပံ၏ အခြေခံသဘောတရားတစ်ခုဖြစ်ပြီး ဆုံးဖြတ်ချက်ချနိုင်မှုသဘောတရားနှင့် နီးကပ်စွာဆက်စပ်နေသည်။ တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်များ၏ သဘောတရားကို Turing စက်များနှင့် အချိန်ရှုပ်ထွေးမှုတို့ကို အသုံးပြု၍ တရားဝင်ပြုလုပ်ထားသည်။ လုပ်ဆောင်ချက်များစွာကို တွက်ချက်နိုင်သော်လည်း၊ တွက်ချက်၍မရနိုင်သော ရပ်တန့်ခြင်းပြဿနာကဲ့သို့သော လုပ်ဆောင်ချက်များလည်း ရှိပါသည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ တွက်ချက်မှုဆိုင်ရာလုပ်ဆောင်ချက်များကို:
- Turing Machines ၏ မတူညီသော ကွဲပြားမှုများသည် တွက်ချက်မှုစွမ်းရည်နှင့် ညီမျှစေရန် ဘာကိုဆိုလိုသနည်း။
- တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်နှင့် ၎င်းကို တွက်ချက်နိုင်သော Turing စက်တည်ရှိမှုကြား ဆက်နွယ်မှုကို ရှင်းပြပါ။
- တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်ကို တွက်ချက်သည့်အခါ Turing စက်၏ အဓိပ္ပါယ်မှာ အဘယ်နည်း။
- လုပ်ဆောင်ချက်တစ်ခုကို အမြဲလက်ခံရန် Turing စက်ကို ပြုပြင်မွမ်းမံနိုင်ပါသလား။ ဘာ့ကြောင့်လဲ၊ ဘာ့ကြောင့်လဲ ဆိုတာ ရှင်းပြပါ။
- Turing စက်သည် လုပ်ဆောင်ချက်တစ်ခုကို မည်သို့တွက်ချက်သနည်း၊ အဝင်နှင့် အထွက်တိပ်များ၏ အခန်းကဏ္ဍက အဘယ်နည်း။