Turing စက်များ၏ မတူညီသော ကွဲပြားမှုအားလုံးသည် တွက်ချက်နိုင်စွမ်းနှင့် ညီမျှခြင်းရှိ၊ ၎င်းကိုဖြေရှင်းရန်အတွက် Turing စက်များ၏သဘောသဘာဝနှင့် တွက်ချက်မှုညီမျှခြင်းသဘောတရားကို ထည့်သွင်းစဉ်းစားရန် အရေးကြီးပါသည်။
Turing စက်သည် 1936 ခုနှစ်တွင် Alan Turing မှမိတ်ဆက်ခဲ့သော စိတ္တဇသင်္ချာတွက်ချက်မှုပုံစံတစ်ခုဖြစ်သည်။ ၎င်းတွင် အဆုံးမရှိတိပ်တစ်ခု၊ တိပ်ပေါ်တွင် သင်္ကေတများကို ဖတ်ရှုနိုင်၊ ရေးနိုင်သော တိပ်ခေါင်းတစ်ခု၊ အကန့်အသတ်ရှိသော ပြည်နယ်များနှင့် အသွင်ကူးပြောင်းမှုဆိုင်ရာ လုပ်ဆောင်မှုတစ်ခု ပါဝင်ပါသည်။ လက်ရှိအခြေအနေနှင့် ဖတ်နေသည့်သင်္ကေတကို အခြေခံ၍ စက်၏လုပ်ဆောင်ချက်များကို ညွှန်ပြသည်။ "ဂန္ထဝင်" သို့မဟုတ် "တိပ်တစ်ခုတည်း" Turing စက်ဟု မကြာခဏရည်ညွှန်းလေ့ရှိသော စံ Turing စက်သည် တွက်ချက်မှုဆိုင်ရာ လုပ်ငန်းစဉ်များကို သတ်မှတ်ရန်အတွက် အခြေခံစံနမူနာအဖြစ် ဆောင်ရွက်ပါသည်။
Turing စက်များတွင် အမျိုးမျိုးသော ပုံစံအမျိုးမျိုးရှိပြီး တစ်ခုစီတွင် ကွဲပြားသောဖွဲ့စည်းပုံများ သို့မဟုတ် မြှင့်တင်မှုများရှိသည်။ ထင်ရှားသော ကွဲပြားမှုများတွင်-
1. Multi-tape Turing စက်များ: ဤစက်များတွင် တိပ်များစွာရှိပြီး သက်ဆိုင်ရာတိပ်ခေါင်းများရှိသည်။ တိပ်တစ်ခုစီသည် အမှီအခိုကင်းစွာ လုပ်ဆောင်နိုင်ပြီး အကူးအပြောင်းလုပ်ဆောင်ချက်သည် တိပ်အားလုံးမှဖတ်သော သင်္ကေတများပေါ်တွင် မူတည်နိုင်သည်။ ရှုပ်ထွေးမှုများ များပြားလာသော်လည်း တိပ်ပေါင်းများစွာ Turing စက်များသည် single-tape Turing စက်များနှင့် တူညီပါသည်။ ဆိုလိုသည်မှာ Multi-tape Turing စက်ဖြင့်လုပ်ဆောင်သော မည်သည့်တွက်ချက်မှုကိုမဆို တိပ်တစ်ချပ် Turing စက်ဖြင့် အတုယူနိုင်သည်၊ လိုအပ်သည့် အဆင့်အရေအတွက်တွင် ဖြစ်နိုင်ခြေရှိသော များပြားလှသော တိုးမြင့်လာသော်လည်း၊
2. သတ်မှတ်မထားသော Turing စက်များ (NTMs): ဤစက်များသည် ပေးထားသောပြည်နယ်နှင့် ထည့်သွင်းသင်္ကေတတစ်ခုအတွက် အသွင်ကူးပြောင်းမှုများစွာကို ပြုလုပ်နိုင်ပြီး၊ များစွာသော တွက်ချက်မှုလမ်းကြောင်းများသို့ ထိထိရောက်ရောက် ခွဲထုတ်နိုင်သည်။ NTM များသည် တွက်ချက်မှုလမ်းကြောင်းများစွာကို တစ်ပြိုင်နက်တည်း စူးစမ်းနိုင်သော်လည်း ၎င်းတို့သည် အဆုံးအဖြတ်ပေးသော Turing စက်များ (DTMs) နှင့်လည်း တူညီပါသည်။ NTM မှအသိအမှတ်ပြုထားသောမည်သည့်ဘာသာစကားကိုမဆို DTM မှအသိအမှတ်ပြုနိုင်သော်လည်း၊ သရုပ်ဖော်မှုသည်အဆိုးဆုံးအခြေအနေတွင် exponential time လိုအပ်နိုင်သည်။
3. Universal Turing စက်များ (UTM)UTM သည် အခြားသော Turing စက်ကို အတုယူနိုင်သော Turing စက်ဖြစ်သည်။ ၎င်းသည် အခြားသော Turing စက်၏ ဖော်ပြချက်နှင့် ထိုစက်အတွက် ထည့်သွင်းမှုစာကြောင်းအဖြစ် ထည့်သွင်းပေးသည်။ ထို့နောက် UTM သည် input string တွင် ဖော်ပြထားသော စက်၏ အပြုအမူကို တုပသည်။ UTMs များ၏တည်ရှိမှုသည် Turing စက်မော်ဒယ်၏ universality ကို မီးမောင်းထိုးပြပြီး အခြား Turing machine သည် မည်သည့်တွက်ချက်မှုကိုမဆို လုပ်ဆောင်နိုင်သည်ကို သက်သေပြသည်။
4. Semi-Infinite တိပ်များဖြင့် Turing စက်များ: ဤစက်များတွင် ဦးတည်ချက်တစ်ခုတည်းတွင် အဆုံးမရှိသောတိပ်များရှိသည်။ Semi-အဆုံးမရှိတိပ် Turing စက်ဖြင့်လုပ်ဆောင်သော တွက်ချက်မှုတိုင်းကို တိပ်ပါ၀င်သည့် ကုဒ်နံပါတ်ဖြင့် စံ Turing စက်ဖြင့် အတုယူနိုင်သောကြောင့် ၎င်းတို့သည် စံ Turing စက်များနှင့် တူညီပါသည်။
5. ခေါင်းများစွာပါသော Turing စက်များ: ဤစက်များတွင် တိပ်တစ်ခုတည်းပေါ်တွင် ဖတ်နိုင်ပြီး စာရေးနိုင်သော တိပ်ခေါင်းများစွာ ပါရှိသည်။ Multi-tape Turing စက်များကဲ့သို့ပင် Multi-head Turing စက်များသည် တိပ်တစ်ခွေ Turing စက်များနှင့် တွက်ချက်မှုအရ တူညီပြီး ထပ်ဆင့်အဆင့်များ လိုအပ်နိုင်ချေရှိသည်။
6. Alternating Turing Machines (ATM): ဤစက်များသည် နိုင်ငံများကို ဖြစ်တည်မှု သို့မဟုတ် စကြာဝဠာအဖြစ် သတ်မှတ်ခွင့်ပြုခြင်းဖြင့် NTM များကို ယေဘူယျအားဖြင့် ယေဘုယျဖော်ပြသည်။ ATM သည် မူလအခြေအနေမှ ဖြစ်တည်မှု နှင့် စကြာဝဠာဆိုင်ရာ အခြေအနေများကို ကျေနပ်စေသော လက်ခံသည့်အခြေအနေသို့ ရွေ့လျားမှုအစီအစဥ်တစ်ခုရှိလျှင် ငွေထုတ်စက်တစ်ခုအား လက်ခံသည်။ ATM များသည် ၎င်းတို့မှတ်မိသည့် ဘာသာစကားများတွင် DTMs များနှင့် ညီမျှသော်လည်း၊ များပြားလှသော အတန်းအစားများဖြစ်သည့် polynomial hierarchy ကဲ့သို့သော ရှုပ်ထွေးသောအတန်းများသည် ကွဲပြားသော်လည်း၊
7. Quantum Turing စက်များ (QTMs): ဤစက်များသည် ကွမ်တမ်မက္ကင်းနစ်၏ အခြေခံမူများကို ပေါင်းစပ်ထားပြီး၊ ပြည်နယ်များ၏ superposition နှင့် entanglement ကိုခွင့်ပြုသည်။ QTM များသည် ဂန္တဝင် Turing စက်များထက် ပိုမိုထိရောက်စွာ ဖြေရှင်းနိုင်သော်လည်း (ဥပမာ- Shor ၏ အယ်လဂိုရီသမ်ကို အသုံးပြု၍ ကိန်းပြည့်များကို ပေါင်းထည့်ခြင်း)၊ ၎င်းတို့သည် တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်များ၏ အတန်းအစားတွင် ပို၍ အစွမ်းထက်မည်မဟုတ်ပေ။ QTM မှတွက်ချက်နိုင်သော မည်သည့်လုပ်ဆောင်ချက်ကို ဂန္တဝင် Turing စက်ဖြင့်လည်း တွက်ချက်နိုင်သည်။
တွက်ချက်မှုစွမ်းရည်တွင် မတူညီသော Turing machine ကွဲပြားမှုများ၏ ညီမျှမှုကို Church-Turing Thesis တွင် အခြေခံထားသည်။ ကျိုးကြောင်းဆီလျော်သော တွက်ချက်မှုပုံစံဖြင့် ထိထိရောက်ရောက် တွက်ချက်နိုင်သည့် မည်သည့်လုပ်ဆောင်ချက်ကို Turing စက်ဖြင့်လည်း တွက်ချက်နိုင်သည်ဟု ဤစာတမ်းတွင် ဖော်ပြထားသည်။ အကျိုးဆက်အနေဖြင့် Turing စက်များ၏ အထက်ဖော်ပြပါ ပြောင်းလဲမှုအားလုံးသည် ၎င်းတို့၏ လုပ်ဆောင်ချက်များကို တွက်ချက်ခြင်းနှင့် ဘာသာစကားများကို မှတ်မိနိုင်စွမ်း သတ်မှတ်ချက်များနှင့် တူညီသော်လည်း ၎င်းတို့သည် ထိရောက်မှု သို့မဟုတ် ပုံသဏ္ဍာန်၏ ရှုပ်ထွေးမှု ကွာခြားနိုင်သော်လည်း၊
ဤညီမျှမှုကို သရုပ်ဖော်ရန်၊ တိပ်တစ်ခုတည်း Turing စက်ကို အသုံးပြု၍ multi-tape Turing စက်ကို ပုံဖော်ရန် တာဝန်ကို စဉ်းစားပါ။ ကျွန်ုပ်တို့တွင် (ဋ) တိပ်များပါသော တိပ်ပေါင်းများစွာ Turing စက်တစ်ခုရှိသည်ဆိုပါစို့။ (k) တိပ်ခွေအားလုံး၏ အကြောင်းအရာများကို တိပ်တစ်ခုတည်းတွင် ကုဒ်ဖြင့် တိပ်တစ်ခုတည်း Turing စက်ဖြင့် ဤစက်ကို တုပနိုင်သည်။ တိပ်တစ်ခုတည်းစက်၏တိပ်ကို မူရင်းတိပ်တစ်ခုစီကိုကိုယ်စားပြုသည့်တစ်ခုစီကို (k) ကဏ္ဍများအဖြစ် ပိုင်းခြားနိုင်သည်။ စက်၏အခြေအနေသည် (k) တိပ်တစ်ခုစီရှိ တိပ်ခေါင်းများ၏ တည်နေရာများနှင့်ပတ်သက်သည့် အချက်အလက်များကို ထည့်သွင်းနိုင်သည်။ တိပ်တစ်ခုတည်းစက်၏ အကူးအပြောင်းလုပ်ဆောင်ချက်ကို ကုဒ်နံပါတ်တိပ်ပါ၀င်သည့်အကြောင်းအရာများနှင့် ဦးခေါင်းအနေအထားများကို လိုက်လျောညီထွေမွမ်းမံပြင်ဆင်ခြင်းဖြင့် Multi-တိပ်စက်၏အပြုအမူကိုအတုယူရန် ဒီဇိုင်းထုတ်နိုင်သည်။ ဤ simulation သည် မူရင်း multi-tape စက်ထက် ခြေလှမ်းများစွာ လိုအပ်နိုင်သော်လည်း၊ တိပ်တစ်ခုတည်းစက်သည် တူညီသောတွက်ချက်မှုကို လုပ်ဆောင်နိုင်သည်ကို သက်သေပြသည်။
အလားတူပင်၊ အဆုံးအဖြတ်မရှိ Turing စက်ဖြင့် အဆုံးအဖြတ်မရှိ Turing စက်ကို အတုယူခြင်းသည် NTM ၏ ဖြစ်နိုင်ချေရှိသော တွက်ချက်မှုလမ်းကြောင်းအားလုံးကို စနစ်တကျ စူးစမ်းခြင်း ပါဝင်သည်။ လမ်းကြောင်းအားလုံးကို နောက်ဆုံးတွင် စစ်ဆေးကြောင်း သေချာစေရန် အနံ-ပထမရှာဖွေမှု သို့မဟုတ် အနက်-ပထမရှာဖွေခြင်းကဲ့သို့သော နည်းပညာများကို အသုံးပြု၍ ၎င်းကို အောင်မြင်နိုင်သည်။ Simulation သည် အဆပိုနှေးနိုင်သော်လည်း DTM သည် NTM ကဲ့သို့တူညီသောဘာသာစကားများကို အသိအမှတ်ပြုနိုင်သည်ကို အတည်ပြုပါသည်။
Turing စက်များ ၏ universality ကို universal Turing machines များ တည်ရှိမှု ဖြင့် ဥပမာပေးပါသည်။ UTM သည် ပစ်မှတ်စက်၏ဖော်ပြချက်နှင့် ၎င်း၏ထည့်သွင်းမှုကို ဘာသာပြန်ခြင်းဖြင့် အခြား Turing စက်ကို တုပနိုင်သည်။ ဤစွမ်းရည်သည် ကွန်ပြူတာစံနစ်တစ်ခုတည်းမှ အခြားသော မော်ဒယ်များအားလုံး၏ အမူအကျင့်များကို ဖုံးအုပ်ထားနိုင်သည်ဟူသော အခြေခံမူကို အလေးပေးကာ တွက်ချက်မှုဆိုင်ရာ ညီမျှခြင်းသဘောတရားကို အားဖြည့်ပေးပါသည်။
Turing စက်များ၏ မတူညီသော ကွဲပြားမှုများသည် ထိရောက်မှု၊ ပရိုဂရမ်ရေးဆွဲရာတွင် လွယ်ကူမှု သို့မဟုတ် သဘောတရားဆိုင်ရာ ရှင်းလင်းပြတ်သားမှုဆိုင်ရာ အားသာချက်များကို ပေးစွမ်းနိုင်သော်လည်း ၎င်းတို့အားလုံးသည် ကွန်ပျူတာစွမ်းရည်နှင့် ညီမျှသည်။ ဤညီမျှမှုသည် သီအိုရီကွန်ပြူတာသိပ္ပံ၏ အခြေခံအုတ်မြစ်ဖြစ်ပြီး၊ တွက်ချက်မှု၏ကန့်သတ်ချက်များနှင့် အဆုံးအဖြတ်နိုင်မှုသဘောသဘာဝကို နားလည်ရန်အတွက် ပေါင်းစည်းထားသောဘောင်တစ်ခုကို ပံ့ပိုးပေးပါသည်။
အခြား လတ်တလောမေးခွန်းများနှင့် အဖြေများ တွက်ချက်မှုဆိုင်ရာလုပ်ဆောင်ချက်များကို:
- တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်နှင့် ၎င်းကို တွက်ချက်နိုင်သော Turing စက်တည်ရှိမှုကြား ဆက်နွယ်မှုကို ရှင်းပြပါ။
- တွက်ချက်နိုင်သော လုပ်ဆောင်ချက်ကို တွက်ချက်သည့်အခါ Turing စက်၏ အဓိပ္ပါယ်မှာ အဘယ်နည်း။
- လုပ်ဆောင်ချက်တစ်ခုကို အမြဲလက်ခံရန် Turing စက်ကို ပြုပြင်မွမ်းမံနိုင်ပါသလား။ ဘာ့ကြောင့်လဲ၊ ဘာ့ကြောင့်လဲ ဆိုတာ ရှင်းပြပါ။
- Turing စက်သည် လုပ်ဆောင်ချက်တစ်ခုကို မည်သို့တွက်ချက်သနည်း၊ အဝင်နှင့် အထွက်တိပ်များ၏ အခန်းကဏ္ဍက အဘယ်နည်း။
- ကွန်ပြူတာဆိုင်ရာ ရှုပ်ထွေးမှုသီအိုရီအရ ကွန်ပြူတာလုပ်ဆောင်နိုင်သော လုပ်ဆောင်မှုဆိုသည်မှာ အဘယ်နည်း၊ ၎င်းကို မည်သို့သတ်မှတ်သနည်း။