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

सैद्धांतिक कंप्यूटर विज्ञान में, एक गैर-नियतात्मक ट्यूरिंग मशीन (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 का उपयोग करना है, जिसमें कॉन्फ़िगरेशन NTM के कई कॉन्फ़िगरेशन का प्रतिनिधित्व करता है, और DTM के संचालन में उनमें से प्रत्येक पर बारी-बारी से जाना होता है, प्रत्येक विज़िट पर एक ही चरण को निष्पादित करना, और जब भी संक्रमण संबंध कई निरंतरताओं को परिभाषित करता है, तो नए कॉन्फ़िगरेशन को जन्म देता है। .

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

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

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

Main article: P versus NP problem

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

परिबद्ध nondeterminism

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

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

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

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