ကျွန်ုပ်တို့တွင် ဆုံးဖြတ်နိုင်သော ဘာသာစကားတစ်ခုကို ဖော်ပြသည့် TM နှစ်ခုရှိလျှင် ညီမျှခြင်းမေးခွန်းသည် အဆုံးအဖြတ်မရနိုင်သေးပါ။
ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီနယ်ပယ်တွင်၊ ဆုံးဖြတ်ချက်ချနိုင်မှုသဘောတရားသည် အခြေခံကျသော အခန်းကဏ္ဍမှ ပါဝင်ပါသည်။ ဘာသာစကားတစ်ခုသည် ဘာသာစကားနှင့်သက်ဆိုင်သည်ဖြစ်စေ မပါဝင်သည်ဖြစ်စေ ပေးထားသည့်ထည့်သွင်းမှုအတွက် ဆုံးဖြတ်နိုင်သည့် Turing machine (TM) ရှိမရှိ ဆုံးဖြတ်နိုင်သည်ဟု ဆိုသည်။ ဘာသာစကားနှင့် ၎င်း၏ဂုဏ်သတ္တိများကို အယ်လ်ဂိုရီသမ်နည်းဖြင့် ကျိုးကြောင်းဆင်ခြင်နိုင်စေသောကြောင့် ဘာသာစကားတစ်ခု၏ ဆုံးဖြတ်နိုင်စွမ်းသည် အရေးကြီးသောပိုင်ဆိုင်မှုတစ်ခုဖြစ်သည်။
Turing စက်များအတွက် ညီမျှခြင်းမေးခွန်းသည် ပေးထားသော TM နှစ်ခုသည် ဘာသာစကားတစ်ခုတည်းကို အသိအမှတ်ပြုခြင်းရှိမရှိ ဆုံးဖြတ်ခြင်းနှင့် သက်ဆိုင်ပါသည်။ တရားဝင်အားဖြင့် TMs M1 နှင့် M2 နှစ်ခုကို ပေးထားပြီး၊ ညီမျှခြင်းမေးခွန်းသည် L(M1) = L(M2) ရှိ၊
TM နှစ်ခု၏ ညီမျှမှုကို ဆုံးဖြတ်ခြင်း၏ ယေဘူယျပြဿနာမှာ အဆုံးအဖြတ်မရနိုင်ဟု သိထားသည်။ ဆိုလိုသည်မှာ မထင်သလို TM နှစ်ခုသည် တူညီသောဘာသာစကားကို အသိအမှတ်ပြုခြင်း ရှိ၊ မရှိ အမြဲဆုံးဖြတ်နိုင်သည့် အယ်လဂိုရီသမ်မရှိဟု ဆိုလိုသည်။ ဤရလဒ်ကို Alan Turing က သူ၏ ကွန်ပျူတာစွမ်းရည်ဆိုင်ရာ ဟောပြောမှုတွင် သက်သေပြခဲ့သည်။
သို့သော်၊ ဤရလဒ်သည် မတရား TMs များ၏ ယေဘုယျကိစ္စရပ်အတွက် ထိန်းထားရန် အရေးကြီးသည်။ TM နှစ်ခုလုံးက ဆုံးဖြတ်နိုင်သော ဘာသာစကားများကို ဖော်ပြသည့် သီးခြားကိစ္စတွင်၊ ညီမျှခြင်းမေးခွန်းသည် ဆုံးဖြတ်ရနိုင်မည်ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော် ဆုံးဖြတ်နိုင်သော ဘာသာစကားများသည် ဘာသာစကားတွင် အဖွဲ့ဝင်ခြင်းကို ဆုံးဖြတ်နိုင်သော TM တစ်ခုရှိသောကြောင့်ဖြစ်သည်။ ထို့ကြောင့်၊ TM နှစ်ခုသည် ဆုံးဖြတ်နိုင်သော ဘာသာစကားများကို ဖော်ပြပါက၊ ၎င်းတို့၏ ညီမျှမှုကို ဆုံးဖြတ်သည့် TM အသစ်တစ်ခုကို ကျွန်ုပ်တို့ တည်ဆောက်နိုင်ပါသည်။
ဒါကို ဥပမာအနေနဲ့ သုံးသပ်ကြည့်ရအောင်။ ကျွန်ုပ်တို့တွင် ဆုံးဖြတ်နိုင်သော ဘာသာစကားများကို ဖော်ပြသည့် TM M1 နှင့် M2 နှစ်ခုရှိသည်ဆိုပါစို့။ ၎င်းတို့၏ ညီမျှမှုကို အောက်ပါအတိုင်း ဆုံးဖြတ်သည့် TM M အသစ်ကို ကျွန်ုပ်တို့ တည်ဆောက်နိုင်သည်-
1. input x ကိုပေးထားပြီး x တွင် M1 ကို x နှင့် M2 တွင် တစ်ပြိုင်နက် ပုံဖော်ပါ။
2. M1 သည် x ကိုလက်ခံပြီး M2 သည် x ကိုလက်ခံပါက လက်ခံပါ။
3. M1 က x ကို ငြင်းပယ်ရင် M2 က x ကို ငြင်းပယ်ရင် လက်ခံပါ။
4. မဟုတ်ပါက ငြင်းပယ်ပါ။
တည်ဆောက်မှုအားဖြင့်၊ M1 နှင့် M2 နှစ်ခုလုံး x လက်ခံပါက သို့မဟုတ် M1 နှင့် M2 နှစ်ခုလုံး x ငြင်းပယ်ပါက TM M သည် input x ကို လက်ခံမည်ဖြစ်သည်။ ဆိုလိုသည်မှာ M သည် ပေးထားသည့် input x အတွက် M1 နှင့် M2 ၏ ညီမျှမှုကို ဆုံးဖြတ်သည်။
မတရား TM နှစ်ခု၏ ညီမျှမှုကို ဆုံးဖြတ်ခြင်း၏ ယေဘူယျပြဿနာမှာ အဆုံးအဖြတ်မရနိုင်သော်လည်း၊ TM များသည် အဆုံးအဖြတ်နိုင်သော ဘာသာစကားများကို ဖော်ပြပါက ညီမျှခြင်းမေးခွန်းသည် ဆုံးဖြတ်ရနိုင်မည်ဖြစ်သည်။ အဘယ်ကြောင့်ဆိုသော် ကျွန်ုပ်တို့အား ဆုံးဖြတ်နိုင်သော ဘာသာစကားများကို TM မှ ဆုံးဖြတ်နိုင်ပြီး ၎င်းတို့၏ ညီမျှမှုကို ဆုံးဖြတ်ပေးသည့် TM တစ်ခုကို တည်ဆောက်နိုင်ခြင်းကြောင့် ဖြစ်သည်။ ဆုံးဖြတ်နိုင်သော ဘာသာစကားများကို ဖော်ပြသည့် TMs အတွက် ညီမျှခြင်းမေးခွန်း၏ အဆုံးအဖြတ်နိုင်မှုသည် ဤဘာသာစကားများ၏ တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုအပေါ် အရေးကြီးသော ထိုးထွင်းသိမြင်မှုကို ပေးပါသည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ Turing စက်၏ညီမျှ:
- ပြဿနာ၏ အဆုံးအဖြတ်မခံနိုင်သော်လည်း၊ အကောင်အထည်ဖော်မှုနှစ်ခု သို့မဟုတ် အကောင်အထည်ဖော်မှုတစ်ခုနှင့် တရားဝင်သတ်မှတ်ချက်တစ်ခုကြား ညီမျှသောအထောက်အထားကို ရှာဖွေခြင်း၏တန်ဖိုးသည် အဘယ်နည်း။
- ၎င်းတို့သည် တူညီသောတာဝန်ကို လုပ်ဆောင်ခြင်း ရှိ၊ မရှိ ဆုံးဖြတ်ရန်နှင့် ၎င်းသည် ယေဘုယျအားဖြင့် အဆုံးအဖြတ်မရနိုင်သော ပြဿနာတစ်ခု ဖြစ်သည်ကို ဆုံးဖြတ်ရန် အယ်လဂိုရီသမ်နှစ်ခုကို နှိုင်းယှဉ်သည့် လုပ်ငန်းစဉ်ကို ဖော်ပြပါ။
- Turing စက်များအတွက် အချည်းနှီးပြဿနာကို Turing စက်များအတွက် ညီမျှမှုပြဿနာအဖြစ် မည်သို့လျှော့ချနိုင်မည်နည်း။
- Turing စက်များ၏ ညီမျှခြင်း၏ အဆုံးအဖြတ်မခံနိုင်မှုနှင့် ဆိုက်ဘာလုံခြုံရေးနယ်ပယ်တွင် ၎င်း၏သက်ရောက်မှုများကို ရှင်းပြပါ။
- တွက်ချက်မှုဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီ၏ နောက်ခံတွင် ဆုံးဖြတ်ချက်ချနိုင်မှုဆိုင်ရာ သဘောတရားမှာ အဘယ်နည်း။