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 တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ:
- ကျေးဇူးပြု၍ FSM အသိအမှတ်ပြုသင်္ကေတ 1 ခုပါသည့် binary string ရှိသည့်အဖြေတွင် ဥပမာကို ဖော်ပြပါ။" ...ထည့်သွင်းထားသောစာကြောင်း "1011"၊ FSM သည် နောက်ဆုံးအခြေအနေသို့မရောက်ဘဲ ပထမသင်္ကေတသုံးခုကိုလုပ်ဆောင်ပြီးနောက် S0 တွင်ပိတ်သွားပါသည်။"
- အဆုံးအဖြတ်မဟုတ်သောဝါဒသည် အကူးအပြောင်းလုပ်ဆောင်မှုကို မည်သို့အကျိုးသက်ရောက်သနည်း။
- ပုံမှန်ဘာသာစကားများသည် Finite State Machines များနှင့် တူညီပါသလား။
- PSPACE အတန်းသည် EXPSPACE အတန်းနှင့် မညီမျှပါသလား။
- Church-Turing Thesis အရ Turing Machine က algorithmically computable problem သည် ပြဿနာဖြစ်ပါသလား။
- ပေါင်းစပ်ဖွဲ့စည်းမှုအောက်တွင် ပုံမှန်ဘာသာစကားများ၏ ပိတ်သိမ်းခြင်းဆိုင်ရာ ပိုင်ဆိုင်မှုကား အဘယ်နည်း။ စက်နှစ်စက်ဖြင့် အသိအမှတ်ပြုထားသော ဘာသာစကားပေါင်းစည်းမှုကို ကိုယ်စားပြုရန်အတွက် အကန့်အသတ်ပြည်နယ်စက်များကို မည်သို့ပေါင်းစပ်ထားသနည်း။
- မတရားသောပြဿနာတိုင်းကို ဘာသာစကားတစ်ခုအဖြစ် ဖော်ပြနိုင်ပါသလား။
- P ရှုပ်ထွေးမှု အတန်းသည် PSPACE အတန်း၏ အစုခွဲတစ်ခုလား။
- Multi-tape Turing စက်တိုင်းတွင် တူညီသော single-tape Turing စက်ရှိပါသလား။
- ကြိုတင်ခန့်မှန်းချက်များ၏ ရလဒ်များကား အဘယ်နည်း။