တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီရှိ ကုထုံးသီအိုရီသည် အဘယ်နည်း၊ ပရိုဂရမ်အတွင်းရှိ ပရိုဂရမ်တစ်ခု၏ ဖော်ပြချက်တစ်ခုကို မည်သို့ရရှိနိုင်သနည်း။
တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီရှိ ပြန်ကောက်ချက်သီအိုရီသည် ကျွန်ုပ်တို့အား ပရိုဂရမ်အတွင်းရှိ ပရိုဂရမ်တစ်ခု၏ ဖော်ပြချက်တစ်ခုကို ရရှိစေမည့် အခြေခံသဘောတရားတစ်ခုဖြစ်သည်။ ဤသီအိုရီသည် တွက်ချက်မှုဆိုင်ရာ ကန့်သတ်ချက်များနှင့် အချို့သော တွက်ချက်မှုဆိုင်ရာ ပြဿနာများကို ဖြေရှင်းရာတွင် ရှုပ်ထွေးမှုကို နားလည်ရန် အရေးကြီးသော အခန်းကဏ္ဍမှ ပါဝင်ပါသည်။
recursion theorem ၏ အရေးပါမှုကို နားလည်ရန်၊ recursion သဘောတရားကို ဦးစွာနားလည်ရန် လိုအပ်ပါသည်။ Recursion သည် ၎င်း၏လုပ်ဆောင်မှုအတွင်း သူ့ဘာသာသူခေါ်ဆိုနိုင်သည့် လုပ်ဆောင်ချက် သို့မဟုတ် ပရိုဂရမ်တစ်ခု၏ စွမ်းရည်ကို ရည်ညွှန်းသည်။ ဤနည်းပညာကို သေးငယ်၍ စီမံခန့်ခွဲနိုင်သော ပြဿနာခွဲများအဖြစ် ခွဲထုတ်ခြင်းဖြင့် ရှုပ်ထွေးသော ပြဿနာများကို ဖြေရှင်းရန်အတွက် ပရိုဂရမ်ရေးရာတွင် တွင်ကျယ်စွာ အသုံးပြုပါသည်။
Stephen Cole Kleene မှ ပုံဖော်ထားသည့်အတိုင်း ပြန်ကုထုံးသီအိုရီသည် တွက်ချက်နိုင်သော မည်သည့်လုပ်ဆောင်ချက်ကိုမဆို သူ့အလိုလိုရည်ညွှန်းသည့် ပရိုဂရမ်တစ်ခုက ကိုယ်စားပြုနိုင်သည်ဟု ဖော်ပြထားသည်။ တစ်နည်းဆိုရသော် ၎င်းသည် ၎င်းတို့၏ကိုယ်ပိုင်အမူအကျင့်များကို ဖော်ပြနိုင်သည့် ကိုယ်ပိုင်ကိုးကားသည့် ပရိုဂရမ်များရှိကြောင်း အာမခံပါသည်။ ဤသီအိုရီသည် တွက်ချက်မှုတွင် မိမိကိုယ်မိမိ ကိုးကားသည့် universality ကို သရုပ်ပြသောကြောင့် ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီအတွက် အားကောင်းသောရလဒ်တစ်ခုဖြစ်သည်။
ပိုမိုခိုင်မာသော နားလည်မှုပေးနိုင်ရန် ဥပမာတစ်ခုကို သုံးသပ်ကြည့်ကြပါစို့။ ပေးထားသော နံပါတ်တစ်ခု၏ factorial ကို တွက်ချက်သည့် ပရိုဂရမ်တစ်ခုရှိသည်ဆိုပါစို့။ ဤပရိုဂရမ်၏ ထပ်ခါတလဲလဲ အကောင်အထည်ဖော်မှုတွင် ၎င်းသည် အခြေခံကိစ္စသို့မရောက်မချင်း ၎င်းကိုသေးငယ်သောထည့်သွင်းမှုဖြင့် သူ့ကိုယ်သူခေါ်ဆိုသည့် လုပ်ဆောင်ချက်ပါဝင်မည်ဖြစ်သည်။ recursion သီအိုရီက ကျွန်ုပ်တို့သည် ပရိုဂရမ်အတွင်း၌ ဤပရိုဂရမ်ကို ကိုယ်စားပြုနိုင်ပြီး Factorial လုပ်ဆောင်မှု၏ မိမိကိုယ်ကို ကိုးကားဖော်ပြချက်အတွက် ခွင့်ပြုပေးကြောင်း ကျွန်ုပ်တို့အား အာမခံပါသည်။
ပရိုဂရမ်အတွင်း ပရိုဂရမ်တစ်ခုအား ဖော်ပြနိုင်မှုသည် ဆိုက်ဘာလုံခြုံရေးနယ်ပယ်တွင် သိသာထင်ရှားသောသက်ရောက်မှုများရှိသည်။ ၎င်းသည် ပရိုဂရမ်သည် runtime ကာလအတွင်း ၎င်း၏ကိုယ်ပိုင်ကုဒ်ကို မွမ်းမံနိုင်သည့် ကိုယ်ပိုင်ပြုပြင်မွမ်းမံထားသော ပရိုဂရမ်များ ဖွံ့ဖြိုးတိုးတက်မှုကို လုပ်ဆောင်ပေးသည်။ ကိုယ်တိုင်ပုံတူမွမ်းမံဖန်တီးခြင်း သို့မဟုတ် ထောက်လှမ်းခြင်းတို့ကို ရှောင်ရှားရန် ဤစွမ်းရည်ကို အန္တရာယ်ရှိသော သရုပ်ဆောင်များက အသုံးချနိုင်သော်လည်း၊ ၎င်းသည် ခုခံကာကွယ်မှုများအတွက် အခွင့်အလမ်းများကိုလည်း ပေးပါသည်။ ဥပမာအားဖြင့်၊ ပေါ်ပေါက်လာသောခြိမ်းခြောက်မှုများကို အင်တိုက်အားတိုက်တုံ့ပြန်နိုင်သည့် လိုက်လျောညီထွေရှိသော လုံခြုံရေးယန္တရားများကို အကောင်အထည်ဖော်ရန်အတွက် ကိုယ်တိုင်ပြုပြင်မွမ်းမံထားသော ပရိုဂရမ်များကို အသုံးပြုနိုင်သည်။
ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီရှိ ပြန်ကောက်ခြင်းသီအိုရီသည် ကိုယ်တိုင်ကိုးကားသည့်ပရိုဂရမ်များတည်ရှိမှုကို အာမခံသည့် အခြေခံသဘောတရားတစ်ခုဖြစ်သည်။ ၎င်းသည် ကျွန်ုပ်တို့အား ဆိုက်ဘာလုံခြုံရေးတွင် အပလီကေးရှင်းအမျိုးမျိုးဖြင့် ကိုယ်တိုင်ပြုပြင်မွမ်းမံထားသော ပရိုဂရမ်များကို ဖွံ့ဖြိုးတိုးတက်စေမည့် ပရိုဂရမ်အတွင်းရှိ ပရိုဂရမ်တစ်ခု၏ ဖော်ပြချက်တစ်ခုကို ရယူနိုင်စေပါသည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ EITC/IS/CCTF တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ အခြေခံအချက်များ:
- အဆုံးအဖြတ်မရှိသော PDAs များကို ထည့်သွင်းစဉ်းစားခြင်းဖြင့် ပြည်နယ်များ၏ ထိပ်တန်းရာထူးကို အဓိပ္ပါယ်ဖွင့်ဆိုနိုင်သည်။ သို့သော်လည်း၊ သတ်မှတ်မသတ်မှတ်ထားသော PDA များသည် ပြည်နယ်များစွာတွင် တပြိုင်နက်တည်းမဖြစ်နိုင်သော stack တစ်ခုသာရှိသည်။ ဒါက ဘယ်လိုဖြစ်နိုင်မလဲ။
- ကွန်ရက်အသွားအလာကို ခွဲခြမ်းစိတ်ဖြာပြီး ဖြစ်နိုင်ချေရှိသော လုံခြုံရေးချိုးဖောက်မှုများကို ညွှန်ပြသည့် ပုံစံများကို ခွဲခြားသတ်မှတ်ရန် အသုံးပြုသည့် PDA ၏ ဥပမာကား အဘယ်နည်း။
- ဘာသာစကားတစ်ခုသည် အခြားဘာသာစကားတစ်ခုထက်ပို၍ အစွမ်းထက်သည်ဟု ဆိုလိုခြင်းဖြစ်သည်။
- Turing Machine မှ context-sensitive languages များကို မှတ်မိနိုင်ပါသလား။
- ဘာသာစကား U = 0^n1^n (n>=0) အဘယ်ကြောင့် ပုံမှန်မဟုတ်သနည်း။
- '1' သင်္ကေတများ ကိန်းဂဏန်းများနှင့်အတူ binary strings များကို အသိအမှတ်ပြုသည့် FSM ကို မည်ကဲ့သို့ အဓိပ္ပာယ်ဖွင့်ဆိုရန်နှင့် ထည့်သွင်းမှု string 1011 ကို လုပ်ဆောင်သည့်အခါ ၎င်းနှင့် မည်သို့ဖြစ်မည်ကို ပြသရန်။
- အဆုံးအဖြတ်မဟုတ်သောဝါဒသည် အကူးအပြောင်းလုပ်ဆောင်မှုကို မည်သို့အကျိုးသက်ရောက်သနည်း။
- ပုံမှန်ဘာသာစကားများသည် Finite State Machines များနှင့် တူညီပါသလား။
- PSPACE အတန်းသည် EXPSPACE အတန်းနှင့် မညီမျှပါသလား။
- Church-Turing Thesis အရ Turing Machine က algorithmically computable problem သည် ပြဿနာဖြစ်ပါသလား။