गैर नियतात्मक ट्यूरिंग मशीन

सैद्धांतिक कंप्यूटर विज्ञान में, एक गैर-नियतात्मक ट्यूरिंग मशीन (एनटीऍम) संगणना का एक सैद्धांतिक प्रारूप है जिसके संचालन नियम कुछ स्थितियों में एक से अधिक संभावित क्रियाओं को निर्दिष्ट करते हैं। अर्थात्, एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक एनटीऍम की अगली स्थिति पूर्ण रूप से इसकी क्रिया और इसके द्वारा देखे जाने वाले वर्तमान प्रतीक द्वारा निर्धारित नहीं होती है।

कंप्यूटर की क्षमताओं और सीमाओं की जांच करने के लिए कभी-कभी विचार प्रयोगों में एनटीऍम का उपयोग किया जाता है। सैद्धांतिक कंप्यूटर विज्ञान में सबसे महत्वपूर्ण प्रारंभिक समस्याओं में से एक पी के विपरीत एनपी समस्या है, जो (अन्य समतुल्य योगों के बीच) इस प्रश्न से संबंधित है कि नियतात्मक कंप्यूटर के साथ गैर-नियतात्मक संगणना का अनुकरण करना कितना कठिन है।

पृष्ठभूमि

संक्षेप में, एक ट्यूरिंग मशीन की कल्पना एक साधारण कंप्यूटर के रूप में की जाती है जो नियमों के एक समूह का सख्ती से पालन करते हुए अंतहीन टेप पर एक बार में प्रतीकों को पढ़ता और लिखता है। यह निर्धारित करता है कि उसे अपनी आंतरिक स्थिति के अनुसार आगे क्या कार्य करना चाहिए और वर्तमान में वह कौन सा प्रतीक प्रयोग करता हैं। ट्यूरिंग मशीन के नियमों में से एक उदाहरण इस प्रकार हो सकता है: यदि आप अवस्था 2 में हैं और आपको 'A' दिखाई देता है, तो इसे 'B' में परिवर्तित करे, बाएँ जाएँ, और अवस्था 3 में परिवर्तित कर दे।

नियतात्मक ट्यूरिंग मशीन

नियतात्मक ट्यूरिंग मशीन (डीटीऍम) में, नियमों का समूह किसी भी स्थिति के लिए किए जाने वाले अधिकतम एक कार्य को निर्धारित करता है।

नियतात्मक ट्यूरिंग मशीन में एक संक्रमण फलन होता है, जो किसी दिए गए अवस्था और प्रतीक के लिए शीर्ष टेप के अनुसार तीन चीजें निर्दिष्ट करता है:

• टेप पर लिखा जाने वाला प्रतीक (यह वर्तमान में उस स्थिति में प्रतीक के समान हो सकता है, या बिल्कुल भी नहीं लिखा जा सकता है, जिसके परिणामस्वरूप कोई व्यावहारिक परिवर्तन नहीं होता है),
• वह दिशा (बाएं, दाएं या कोई भी नहीं) जिसमें शीर्ष को हिलना चाहिए, और
• परिमित नियंत्रण के बाद की स्थिति।

उदाहरण के लिए, अवस्था 3 में टेप पर एक X,डीटीऍम को टेप पर Y लिखवा सकता है, शीर्ष को एक स्थिति दाईं तरफ ले जा सकता है, और अवस्था 5 पर परिवर्तित कर सकता है।

अंतर्ज्ञान

नियतात्मक और गैर-नियतात्मक संगणना की तुलना

एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक गैर-नियतात्मक ट्यूरिंग मशीन (एनटीऍम) में नियमों का समूह किसी भी स्थिति के लिए एक से अधिक क्रियाओं को करने के लिए निर्धारित कर सकता है। उदाहरण के लिए, अवस्था 3 में टेप पर X एनटीऍम को इसकी अनुमति दे सकता है:

• Y लिखें, दाएँ जाएँ और स्थिति 5 पर बदले

या

• एक X लिखें, बाएँ जाएँ, और अवस्था 3 में रहें।

कई नियमों का समाधान

एनटीऍम कैसे जानता है कि उसे इनमें से कौन सा कार्य करना चाहिए? इसे देखने के दो विधिया हैं। एक तो यह कहना है कि मशीन सबसे भाग्यशाली संभावित अनुमानक है; यह हमेशा एक संक्रमण चुनता है जो अंततः एक स्वीकार्य स्थिति की ओर ले जाता है, यदि ऐसा कोई संक्रमण होता है। दूसरा यह कल्पना करना है कि मशीन कई-नियमो के सिद्धांत को कई प्रतियों में बदल देती है, जिनमें से प्रत्येक संभावित संक्रमणों में से एक का अनुसरण करती है। जबकि एक डीटीऍम के पास एक एकल संगणना पथ होता है तथा एक एनटीऍम के पास एक संगणना वृक्ष होता है जिसका वह अनुसरण करता हैं। यदि वृक्ष की कम से कम एक शाखा स्वीकृत पक्ष के साथ रुकती है, तो एनटीऍम इनपुट को स्वीकार करता है।

परिभाषा

एक गैर नियतात्मक ट्यूरिंग मशीन को औपचारिक रूप से छः-ट्यूपल $M=(Q,\Sigma ,\iota ,\sqcup ,A,\delta )$ के रूप में परिभाषित किया जा सकता हैं, जहाँ

• $Q$ अवस्थाओं का एक परिमित समूह है
• $\Sigma$ प्रतीकों का एक सीमित समूह है (टेप वर्णमाला)
• $\iota \in Q$ प्रारम्भिक अवस्था है
• $\sqcup \in \Sigma$ रिक्त चिन्ह है
• $A\subseteq Q$ (अंतिम) अवस्थाओं को स्वीकार करने का समूह है
• $\delta \subseteq \left(Q\backslash A\times \Sigma \right)\times \left(Q\times \Sigma \times \{L,S,R\}\right)$ अवस्थाओं और प्रतीकों पर एक संबंध है जिसे संक्रमण संबंध कहा जाता है। $L$ बाईं तरफ गतिशील है, $S$ गतिशील नहीं है, और $R$ दाईं तरफ गतिशील है।

एक मानक (नियतात्मक) ट्यूरिंग मशीन के साथ अंतर यह है कि, नियतात्मक ट्यूरिंग मशीनों के लिए, संक्रमण संबंध केवल एक संबंध के अतिरिक्त एक कार्य है।

विन्यास और विन्यास पर उत्पाद संबंध, जो टेप की किसी भी संभावित सामग्री को देखते हुए ट्यूरिंग मशीन की संभावित क्रियाओं का वर्णन करता है, मानक ट्यूरिंग मशीनों के लिए है, इसके अतिरिक्त कि उत्पाद संबंध अब एकल मान नहीं है। (यदि मशीन नियतात्मक है, तो संभावित संगणनाएँ एकल, संभवतः अनंत, पथ के सभी उपसर्ग हैं।)

एनटीऍम के लिए इनपुट नियतात्मक ट्यूरिंग मशीन के समान ही प्रदान किया जाता है: मशीन को विन्यास में प्रारम्भ किया जाता हैं जिसमें शीर्ष टेप स्ट्रिंग के पहले अक्षर (यदि कोई हो) पर होता है, और अन्यथा टेप पूरी तरह से खाली होता है।

एक एनटीऍम एक इनपुट स्ट्रिंग स्वीकार करता है अगर और केवल तभी जब उस स्ट्रिंग से शुरू होने वाले संभावित विनिमय पथों में से कम से कम एक मशीन को स्वीकार्य स्थिति में रखता है। नियतात्मक मशीन पर एक एनटीऍम के कई शाखा पथों का अनुकरण करते समय, जैसे ही कोई शाखा एक स्वीकार्य स्थिति में पहुँचती है, हम संपूर्ण अनुरूपण को रोक सकते हैं।

वैकल्पिक परिभाषाएं

एक गणितीय निर्माण के रूप में मुख्य रूप से प्रमाणों में उपयोग किया जाता है, एनटीऍम की परिभाषा में कई प्रकार के छोटे बदलाव होते हैं, लेकिन ये विविधताएँ सभी समान भाषाओं को स्वीकार करती हैं।

संक्रमण सम्बन्ध के आउटपुट में शीर्ष परिवर्तन को बाये से (-1), स्थायी (0), और दाये से (+1) को ले जाने का प्रतिनिधित्व करने के लिए अक्षरों का उपयोग करने के जगह प्रायः संख्यात्मक रूप से सांकेतिक शब्दो में बदला जाता हैं; का संक्रमण फलन आउटपुट $\left(Q\times \Sigma \times \{-1,0,+1\}\right)$ देता हैं। स्थिर (0) आउटपुट को छोड़ देना साधारण बात हैं, और इसके अतिरिक्त किसी भी वांछित स्थिर संक्रमण के सकर्मक समापन को सम्मिलित करें।

कुछ लेखक एक स्पष्ट अस्वीकृत स्थिति जोड़ते हैं, जिसके कारण एनटीऍम बिना स्वीकार किए रुक जाता है। यह परिभाषा अभी भी विषमता को बनाये रखती है जिसे कोई भी गैर-नियतात्मक शाखा स्वीकार कर सकती है, लेकिन स्ट्रिंग को अस्वीकार करने के लिए प्रत्येक शाखा को अस्वीकार करना होगा।

डीटीऍम के साथ कम्प्यूटेशनल समकक्ष

कोई कम्प्यूटेशनल(अभिकलनीय) समस्या जिसे डीटीऍम द्वारा हल किया जा सकता है, और इसके विपरीत एनटीऍम द्वारा भी हल किया जा सकता है। जबकि, यह माना जाता है कि सामान्य तौर पर समय की जटिलता समान नहीं हो सकती है।

एनटीऍम के एक विशेष कथन के रूप में डीटीऍम

एनटीऍम में डीटीऍम को विशेष कथनो के रूप में सम्मलित किया गया है, इसलिए डीटीऍम द्वारा की जा सकने वाली प्रत्येक गणना समकक्ष एनटीऍम द्वारा भी की जा सकती है।

एनटीऍम का डीटीऍम अनुकरण

ऐसा लग सकता है कि एनटीऍम, डीटीऍम की तुलना में अधिक शक्तिशाली हैं, क्योंकि वे एक ही प्रारंभिक विन्यास से उत्पन्न होने वाली संभावित कम्प्यूटेशंस (अभिकलन) के वृक्ष को अनुमति दे सकते हैं, अगर वृक्ष में कोई एक शाखा इसे स्वीकार करती है तो स्ट्रिंग को स्वीकार कर सकती है। जबकि, एनटीऍम को डीटीऍम के साथ अनुकरण करना संभव है, और वास्तव में यह एक से अधिक प्रकारो से किया जा सकता है।

विन्यास अवस्थाओं की बहुलता

एक दृष्टिकोण एक डीटीऍम का उपयोग करना है, जिसमें विन्यास एनटीऍम के कई विन्यासो का प्रतिनिधित्व करता है, और डीटीऍम के संचालन में उनमें से प्रत्येक पर बारी-बारी से जाना होता है, प्रत्येक पहुंच पर एक ही चरण को निष्पादित करना, और जब भी संक्रमण संबंध कई निरंतरताओं को परिभाषित करता है, तो नए विन्यासो को निर्मित करता हैं। .

टेपों की बहुलता

एक और निर्माण 3-टेप डीटीऍम के साथ एनटीऍम का अनुकरण करता है, जिनमें से पहला टेप हमेशा मूल इनपुट स्ट्रिंग रखता है, दूसरे का उपयोग एनटीऍम की एक विशेष गणना को अनुकरण करने के लिए किया जाता है, और तीसरा एनटीऍम के गणना वृक्ष में पथ को सांकेतिक शब्दो में निर्मित करता हैं। 3-टेप डीटीऍम को सामान्य एकल-टेप डीटीऍम के साथ आसानी से अनुकरण किया जाता है।

समय जटिलता और पी बनाम एनपी

Main article: P versus NP problem

दूसरे निर्माण में, निर्मित डीटीऍम प्रभावी रूप से एनटीऍम के कम्प्यूटेशन (अभिकलन) पहले ट्री की चौड़ाई की खोज करता हैं, तब लंबाई बढ़ाने के क्रम में एनटीऍम की सभी संभावित संगणनाओं का चक्कर लगाता हैं जब तक कि यह एक स्वीकार्य नहीं हो जाता। इसलिए, डीटीऍम की स्वीकार्य गणना की लंबाई सामान्य रूप से एनटीऍम की सबसे छोटी स्वीकार्य गणना की लंबाई में घातीय है। यह डीटीऍम द्वारा एनटीऍम के अनुरूपण की एक सामान्य संपत्ति माना जाता है। पी = एनपी समस्या कंप्यूटर विज्ञान में सबसे प्रसिद्ध अज्ञात प्रश्न, इस समस्या के एक कथन से संबंधित है: जो यह है की बहुपद समय में एनटीऍम द्वारा हल की जाने वाली प्रत्येक समस्या, अनिवार्य रूप से बहुपद समय में डीटीऍम द्वारा हल करने योग्य है या नहीं है।

गैर-नियतात्मक परिबद्ध

एक एनटीऍम में गैर-नियतात्मक परिबद्ध का गुण होता है। यदि कोई एनटीऍम हमेशा किसी दिए गए इनपुट टेप T पर रुकता है तो यह सीमित संख्या के चरणों में रुकता है, और इसलिए केवल संभावित विन्यासो की सीमित संख्या हो सकती है।

क्वांटम कंप्यूटर्स के साथ तुलना

बीक्यूँपी (बीक्यूँपी) समस्याओं की श्रेणी का संदिग्ध आकार। ध्यान दें कि आंकड़ा बताता है ${\mathsf {P}}\neq {\mathsf {NP}}$ और ${\mathsf {NP}}\neq {\mathsf {PSPACE}}$. अगर यह सच नहीं है तो आंकड़ा अलग दिखना चाहिए।

क्योंकि क्वांटम कम्प्यूटर्स, क्वांटम बिट्स का उपयोग करते हैं, जो पारंपरिक बिट्स के अतिरिक्त अवस्थाओं के अध्यारोपण में हो सकते हैं, कभी-कभी यह गलत धारणा है कि क्वांटम कंप्यूटर एनटीऍम हैं। जबकि, यह विशेषज्ञों द्वारा माना जाता है (लेकिन सिद्ध नहीं हुआ है) कि क्वांटम कंप्यूटर की शक्ति, वास्तव में, एनटीऍम की तुलना में अतुलनीय है; अर्थात् समस्याएँ उपलब्ध होने की संभावना है कि एक एनटीऍम कुशलता से हल कर सकता है इसके विपरीत जिसे एक क्वांटम कंप्यूटर नहीं कर सकता है । विशेष रूप से, यह संभावना है कि एनपी-पूर्ण समस्याएं एनटीऍम द्वारा हल की जा सकती हैं लेकिन बहुपद समय में क्वांटम कंप्यूटर द्वारा नहीं की जा सकती हैं।

सहज रूप से बताया जाये तो, जबकि एक क्वांटम कंप्यूटर वास्तव में एक अध्यारोपण स्थिति में हो सकता है, जो एक ही समय में निष्पादित सभी संभावित कम्प्यूटेशनल (अभिकलनीय) शाखाओं के अनुरूप हो सकता है (एनटीऍम के समान), अंतिम माप क्वांटम कंप्यूटर को यादृच्छिक रूप से चयनित शाखा में खंडित कर देगा। यह शाखा सामान्य रूप से एनटीऍम के विपरीत चुने गए समाधान का प्रतिनिधित्व नहीं करती है, जिसे घातीय रूप से कई शाखाओं के बीच सही समाधान चुनने की अनुमति होती है।

यह भी देखें

• संभाव्य ट्यूरिंग मशीन

संदर्भ

सामान्य

• Martin, John C. (1997). "Section 9.6: Nondeterministic Turing machines". भाषाओं का परिचय और संगणना का सिद्धांत (2nd ed.). McGraw-Hill. pp. 277–281. ISBN 978-0073191461.
• Papadimitriou, Christos (1993). "Section 2.7: Nondeterministic machines". अभिकलनात्मक जटिलता (1st ed.). Addison-Wesley. pp. 45–50. ISBN 978-0201530827.

बाहरी संबंध

• C++ Simulator of a Nondeterministic Multitape Turing Machine (free software).
• C++ Simulator of a Nondeterministic Multitape Turing Machine download link from sourceforge.net