တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်နှင့် ၎င်းကို တွက်ချက်နိုင်သော Turing စက်တည်ရှိမှုကြား ဆက်နွယ်မှုကို ရှင်းပြပါ။
ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီနယ်ပယ်တွင်၊ တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်တစ်ခုနှင့် ၎င်းကိုတွက်ချက်နိုင်သော Turing စက်တည်ရှိမှုကြား ဆက်နွယ်မှုသည် အခြေခံအရေးကြီးပါသည်။ ဤဆက်နွယ်မှုကို နားလည်ရန်၊ ကျွန်ုပ်တို့သည် တွက်ချက်နိုင်သော လုပ်ဆောင်ချက် မည်သည်နှင့် ၎င်းသည် Turing စက်များနှင့် မည်သို့ဆက်စပ်ကြောင်းကို ဦးစွာ သတ်မှတ်ရပါမည်။
recursive function ဟုလည်းလူသိများသော computable function သည် algorithm ဖြင့်တွက်ချက်နိုင်သော သင်္ချာလုပ်ဆောင်ချက်တစ်ခုဖြစ်သည်။ ၎င်းသည် input တစ်ခုခုကိုပေး၍ မည်သည့် input ကိုမဆိုရပ်တန့်ကာ ထို input အတွက်မှန်ကန်သော output ကိုထုတ်ပေးမည့် Turing machine တစ်ခုရှိနေသည့် function တစ်ခုဖြစ်သည်။ တစ်နည်းဆိုရသော် တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်သည် Turing စက်ဖြင့် ထိထိရောက်ရောက် တွက်ချက်နိုင်သည့် တစ်ခုဖြစ်သည်။
Turing စက်များသည် 1936 ခုနှစ်တွင် Alan Turing မှ မိတ်ဆက်ခဲ့သော သီအိုရီဆိုင်ရာ ကွန်ပြူတာ စက်များဖြစ်သည်။ ၎င်းတို့တွင် ဆဲလ်များအဖြစ် အဆုံးမရှိ ပိုင်းခြားထားသော တိပ်ခွေတစ်ခု၊ တိပ်တစ်လျှောက် ရွေ့လျားနိုင်သော စာဖတ်/ရေးနိုင်သော ဦးခေါင်းနှင့် အုပ်ချုပ်သည့် ပြည်နယ်များ ပါဝင်သည်။ စက်၏အပြုအမူ။ စက်သည် တိပ်ပေါ်ရှိ သင်္ကေတများကို ဖတ်သည်၊ ၎င်း၏ လက်ရှိအခြေအနေနှင့် ၎င်းဖတ်သည့် သင်္ကေတကို အခြေခံ၍ အချို့သော လုပ်ဆောင်ချက်များကို လုပ်ဆောင်ပြီး အခြေအနေအသစ်သို့ ကူးပြောင်းသည်။ စက်ရပ်သွားသည်အထိ ဤလုပ်ငန်းစဉ်ကို ဆက်လက်လုပ်ဆောင်ပါသည်။
တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်နှင့် ၎င်းကို တွက်ချက်နိုင်သော Turing စက်တည်ရှိမှုကြား ဆက်နွယ်မှုသည် Turing-completeness သဘောတရားအပေါ် အခြေခံသည်။ Turing စက်သည် အခြားသော Turing စက်ကို အတုယူနိုင်လျှင် Turing-ပြီးပြည့်စုံသည်ဟု ဆိုပါသည်။ တစ်နည်းအားဖြင့် Turing-complete machine သည် အခြားသော Turing machine မှ တွက်ချက်နိုင်သော မည်သည့် function ကိုမဆို တွက်ချက်နိုင်သည်။
ဤအဓိပ္ပါယ်ဖြင့် လုပ်ဆောင်ချက်တစ်ခုသည် တွက်ချက်နိုင်လျှင် ၎င်းကို တွက်ချက်နိုင်သော Turing စက်ရှိနေပြီဟု ဆိုနိုင်ပါသည်။ အပြန်အလှန်အားဖြင့် Turing စက်သည် လုပ်ဆောင်ချက်တစ်ခုကို တွက်ချက်နိုင်လျှင် ထိုလုပ်ဆောင်ချက်သည် တွက်ချက်နိုင်သည်။ ဤဆက်ဆံရေးသည် Turing စက်များသည် အခြားသော Turing စက်များကို အတုယူနိုင်သော universal computing devices များဖြစ်သည်ဟူသောအချက်အပေါ် အခြေခံထားသည်။
ဤဆက်ဆံရေးကို သရုပ်ဖော်ရန် ဥပမာတစ်ခုကို သုံးသပ်ကြည့်ကြပါစို့။ ကျွန်ုပ်တို့တွင် ဂဏန်းနှစ်လုံးပေါင်းထည့်နိုင်သော တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်တစ်ခုရှိသည်ဆိုပါစို့။ သွင်းအားစုနှစ်ခုယူကာ တိပ်ပေါ်ရှိ ပထမနံပါတ်သို့ နံပါတ်သို့ ရွေ့လျားပြီး ရလဒ်ကို ထုတ်ပေးသည့် Turing စက်ကို ကျွန်ုပ်တို့ သတ်မှတ်နိုင်သည်။ ဤ Turing စက်သည် တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်နှင့် ၎င်းကို တွက်ချက်နိုင်သော Turing စက်၏ တည်ရှိမှုကြား ဆက်နွယ်မှုကို ပြသသည့် အပိုလုပ်ဆောင်ချက်ကို တွက်ချက်နိုင်သည်။
တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်နှင့် ၎င်းကို တွက်ချက်နိုင်သော Turing စက်တည်ရှိမှုကြား ဆက်နွယ်မှုသည် Turing-completeness သဘောတရားအပေါ် အခြေခံသည်။ တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်သည် Turing စက်ဖြင့် ထိရောက်စွာ တွက်ချက်နိုင်သော တစ်ခုဖြစ်ပြီး၊ ၎င်းသည် အခြား Turing စက်ကို အတုယူနိုင်လျှင် Turing စက်သည် Turing ပြည့်စုံပါသည်။ ထို့ကြောင့် function တစ်ခုသည် တွက်ချက်နိုင်လျှင် ၎င်းကို တွက်ချက်နိုင်သော Turing machine ရှိပြီး အပြန်အလှန်အားဖြင့် ၎င်းကို တွက်ချက်နိုင်သည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ တွက်ချက်မှုဆိုင်ရာလုပ်ဆောင်ချက်များကို:
- Turing Machines ၏ မတူညီသော ကွဲပြားမှုများသည် တွက်ချက်မှုစွမ်းရည်နှင့် ညီမျှစေရန် ဘာကိုဆိုလိုသနည်း။
- တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်ကို တွက်ချက်သည့်အခါ Turing စက်၏ အဓိပ္ပါယ်မှာ အဘယ်နည်း။
- လုပ်ဆောင်ချက်တစ်ခုကို အမြဲလက်ခံရန် Turing စက်ကို ပြုပြင်မွမ်းမံနိုင်ပါသလား။ ဘာ့ကြောင့်လဲ၊ ဘာ့ကြောင့်လဲ ဆိုတာ ရှင်းပြပါ။
- Turing စက်သည် လုပ်ဆောင်ချက်တစ်ခုကို မည်သို့တွက်ချက်သနည်း၊ အဝင်နှင့် အထွက်တိပ်များ၏ အခန်းကဏ္ဍက အဘယ်နည်း။
- ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီအရ ကွန်ပြူတာလုပ်ဆောင်နိုင်သော လုပ်ဆောင်မှုဆိုသည်မှာ အဘယ်နည်း၊ ၎င်းကို မည်သို့သတ်မှတ်သနည်း။