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

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

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

पृष्ठभूमि

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

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

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

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

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

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

अंतर्ज्ञान

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

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

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

या

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

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

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

परिभाषा

एक गैर नियतात्मक ट्यूरिंग मशीन को औपचारिक रूप से सिक्स-ट्यूपल $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$ दाईं तरफ गतिशील है।

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

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

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

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

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

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

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

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

DTM के साथ कम्प्यूटेशनल समकक्ष

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

NTM के एक विशेष कथन के रूप में DTM

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

NTM का DTM अनुकरण

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

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

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

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

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

समय जटिलता और P बनाम NP

Main article: P versus NP problem

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

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

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

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

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

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

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

यह भी देखें

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

संदर्भ

सामान्य

• 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