Church-Turing Thesis ဆိုသည်မှာ အဘယ်နည်း၊ ၎င်းသည် တွက်ချက်နိုင်စွမ်းကို မည်သို့အဓိပ္ပာယ်ဖွင့်ဆိုသနည်း။
Church-Turing Thesis သည် ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီနယ်ပယ်တွင် အခြေခံသဘောတရားတစ်ခုဖြစ်ပြီး တွက်ချက်နိုင်စွမ်း၏ကန့်သတ်ချက်များကိုနားလည်ရန်အရေးကြီးသောအခန်းမှပါဝင်ပါသည်။ ၎င်းကို သင်္ချာပညာရှင် Alonzo Church နှင့် ယုတ္တိဗေဒပညာရှင်နှင့် ကွန်ပြူတာပညာရှင် Alan Turing တို့က 1930 ခုနှစ်များတွင် အလားတူ အယူအဆများကို လွတ်လပ်စွာ ပုံဖော်ပေးခဲ့သော အစွဲပြု၍ အမည်ပေးထားသည်။
၎င်း၏ အဓိကအချက်မှာ Church-Turing Thesis တွင် ထိထိရောက်ရောက် တွက်ချက်နိုင်သော မည်သည့်လုပ်ဆောင်ချက်ကို Turing စက်ဖြင့် တွက်ချက်နိုင်သည်ဟု ဖော်ပြထားသည်။ တစ်နည်းဆိုရသော် function တစ်ခုကို algorithm ဖြင့် တွက်ချက်နိုင်လျှင် Turing machine မှလည်း တွက်ချက်နိုင်သည်။ ဤစာတမ်းသည် Turing စက်များ၊ lambda calculus နှင့် recursive functions ကဲ့သို့သော မတူညီသော တွက်ချက်မှုပုံစံများတွင် တူညီသည်ဟု ဤစာတမ်းတွင် ဖော်ပြထားခြင်းဖြစ်သည်။
Turing စက်သည် ဆဲလ်များအဖြစ် ပိုင်းခြားထားသော အဆုံးမရှိ တိပ်တစ်ခု၊ တိပ်တစ်လျှောက် ရွေ့လျားနိုင်သော စာဖတ်ရေးဦးခေါင်းနှင့် စက်၏ အပြုအမူကို ဆုံးဖြတ်ပေးသည့် ထိန်းချုပ်ယူနစ်တို့ ပါဝင်သော ကွန်ပျူတာ၏ စိတ္တဇသင်္ချာပုံစံတစ်ခုဖြစ်သည်။ တိပ်သည် အစပိုင်းတွင် ဗလာဖြစ်ပြီး စက်၏ အပြုအမူကို ပြည်နယ်များနှင့် ကူးပြောင်းခြင်းဆိုင်ရာ စည်းမျဉ်းအစုံဖြင့် ဆုံးဖြတ်သည်။ စက်သည် လက်ရှိတိပ်ဆဲလ်ရှိ သင်္ကေတကို ဖတ်နိုင်သည်၊ သင်္ကေတအသစ်တစ်ခုရေးရန်၊ ခေါင်းကို ဘယ်ဘက် သို့မဟုတ် ညာဘက်သို့ ရွှေ့ကာ လက်ရှိအခြေအနေနှင့် သင်္ကေတဖတ်သည့်အပေါ်မူတည်၍ ၎င်း၏အခြေအနေကို ပြောင်းလဲနိုင်သည်။
Church-Turing Thesis မှ algorithm ဖြင့် တွက်ချက်နိုင်သော မည်သည့် function ကို Turing machine မှ တွက်ချက်နိုင်ကြောင်း အခိုင်အမာဆိုသည်။ ဆိုလိုသည်မှာ ပြဿနာတစ်ခုအား ဖြေရှင်းရန် အဆင့်ဆင့်လုပ်ထုံးလုပ်နည်းတစ်ခုရှိလျှင် တူညီသောအဆင့်များကို လုပ်ဆောင်နိုင်သည့် Turing စက်တစ်ခုရှိနေပြီဖြစ်သည်။ အပြန်အလှန်အားဖြင့် ပြဿနာတစ်ခုကို Turing စက်ဖြင့် မဖြေရှင်းနိုင်ပါက ၎င်းကို ဖြေရှင်းနိုင်သည့် algorithm မရှိပါ။
Church-Turing Thesis သည် တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီနယ်ပယ်အတွက် သိသာထင်ရှားသောသက်ရောက်မှုများရှိသည်။ ၎င်းသည် တွက်ချက်မှုဆိုင်ရာ ကန့်သတ်ချက်များကို နားလည်ရန်အတွက် သီအိုရီအခြေခံအုတ်မြစ်ကို ထောက်ပံ့ပေးပြီး ၎င်းတို့၏ တွက်ချက်မှုဆိုင်ရာ အခက်အခဲများအပေါ် အခြေခံ၍ ပြဿနာများကို အမျိုးအစားခွဲခြားရန် ကူညီပေးသည်။ ဥပမာအားဖြင့်၊ များပြားလှသောအချိန်များတွင် Turing စက်ဖြင့်ဖြေရှင်းနိုင်သောပြဿနာများကို class P (polynomial time) တွင် ခွဲခြားသတ်မှတ်ထားပြီး၊ exponential time လိုအပ်သည့်ပြဿနာများကို class EXP (exponential time) မှ အမျိုးအစားခွဲခြားထားသည်။
ထို့အပြင်၊ Church-Turing Thesis သည် ဆိုက်ဘာလုံခြုံရေးနယ်ပယ်တွင် လက်တွေ့ကျသောသက်ရောက်မှုများရှိသည်။ ၎င်းသည် တိုက်ခိုက်မှုများ၏ တွက်ချက်မှုဆိုင်ရာ ဖြစ်နိုင်ခြေကို အကဲဖြတ်ရန်အတွက် မူဘောင်တစ်ခုကို ပံ့ပိုးပေးခြင်းဖြင့် cryptographic algorithms နှင့် protocols များ၏ လုံခြုံရေးကို ပိုင်းခြားစိတ်ဖြာရာတွင် ကူညီပေးပါသည်။ ဥပမာအားဖြင့်၊ Turing machine မှ တိုက်ခိုက်မှုများကို လုံခြုံစေသည်ဟု cryptographic algorithm မှ သက်သေပြပါက၊ ၎င်းသည် လက်တွေ့ကျသော တိုက်ခိုက်မှုများကို ခံနိုင်ရည်ရှိရန် ယုံကြည်မှုကို ပေးပါသည်။
Church-Turing Thesis သည် မတူညီသော တွက်ချက်မှုပုံစံများတစ်လျှောက် တွက်ချက်နိုင်မှု၏ ညီမျှမှုကို အခိုင်အမာအတည်ပြုသည့် ကွန်ပြူတာရှုပ်ထွေးမှုသီအိုရီတွင် အခြေခံသဘောတရားတစ်ခုဖြစ်သည်။ ထိထိရောက်ရောက် တွက်ချက်နိုင်သော မည်သည့်လုပ်ဆောင်ချက်ကို Turing စက်ဖြင့် တွက်ချက်နိုင်ကြောင်း ၎င်းကဆိုသည်။ ဤစာတမ်းသည် တွက်ချက်ခြင်းဆိုင်ရာ ကန့်သတ်ချက်များကို နားလည်ခြင်းအတွက် လေးနက်သော သက်ရောက်မှုများရှိပြီး ဆိုက်ဘာလုံခြုံရေးနယ်ပယ်တွင် လက်တွေ့အသုံးချမှုများပါရှိသည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ EITC/IS/CCTF တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ:
- Kleene ကြယ်ပွင့် လုပ်ဆောင်ချက်က ပုံမှန်ဘာသာစကားတစ်ခုကို ဘာလုပ်သလဲ။
- ဆုံးဖြတ်နိုင်သော နှင့် ဆုံးဖြတ်မနိုင်သော FSM များ၏ ညီမျှမှုကို စာကြောင်းတစ်ကြောင်း သို့မဟုတ် နှစ်ကြောင်းဖြင့် ရှင်းပြပါ။
- ဘာသာစကားတစ်ခုမှာ စာကြောင်း ၂ ခုရှိပါတယ်။ တစ်ခုကို FSM က လက်ခံပြီး နောက်တစ်ခုကို လက်မခံပါဘူး။ ဒီဘာသာစကားကို FSM က မှတ်မိတယ်လို့ ပြောလို့ရမလား၊ မသိဘူးလား။
- ရိုးရှင်းတဲ့ sorting algorithm တစ်ခုကို FSM အဖြစ် သတ်မှတ်နိုင်ပါသလား။ ဟုတ်ကဲ့ဆိုရင် directed graph နဲ့ ဘယ်လိုကိုယ်စားပြုနိုင်မလဲ။
- ဗလာစာကြောင်းများနှင့် ဗလာဘာသာစကားများ ပြည့်နိုင်ပါသလား။
- virtual machines များကို FSMs အဖြစ် သတ်မှတ်နိုင်ပါသလား။
- တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ formalism နားလည်မှုအတွက် အခြေခံသင်္ချာအဓိပ္ပါယ်ဖွင့်ဆိုချက်များနှင့် နိဒါန်းအချို့က အဘယ်နည်း။
- cryptography နှင့် cybersecurity ၏ အခြေခံအုတ်မြစ်များကို နားလည်ရန်အတွက် တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီသည် အဘယ်ကြောင့် အရေးကြီးသနည်း။
- ATM ၏ အဆုံးအဖြတ်မခံနိုင်မှုကို သရုပ်ပြရာတွင် ပြန်ကောက်ချက် သီအိုရီ၏ အခန်းကဏ္ဍက အဘယ်နည်း။
- palindromes ကိုဖတ်နိုင်သော PDA ကိုထည့်သွင်းစဉ်းစားခြင်းဖြင့်၊ ထည့်သွင်းမှုသည် ပထမ၊ palindrome နှင့် ဒုတိယ၊ palindrome မဟုတ်သည့်အခါ stack ၏ဆင့်ကဲဖြစ်စဉ်ကို အသေးစိတ်ပြောပြနိုင်မလား။