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

Latest revision as of 17:39, 29 August 2023

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

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

पृष्ठभूमि

संक्षेप में, एक ट्यूरिंग मशीन की कल्पना एक साधारण कंप्यूटर के रूप में की जाती है जो नियमों के एक समूह का सख्ती से पालन करते हुए अंतहीन टेप पर एक बार में प्रतीकों को पढ़ता और लिखता है। यह निर्धारित करता है कि उसे अपनी आंतरिक स्थिति के अनुसार आगे क्या कार्य करना चाहिए और वर्तमान में वह कौन सा प्रतीक प्रयोग करता हैं। ट्यूरिंग मशीन के नियमों में से एक उदाहरण इस प्रकार हो सकता है: यदि आप अवस्था 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) आउटपुट को छोड़ देना साधारण बात हैं,^[1] और इसके अतिरिक्त किसी भी वांछित स्थिर संक्रमण के सकर्मक समापन को सम्मिलित करें।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

बीक्यूँपी (बीक्यूँपी) समस्याओं की श्रेणी का संदिग्ध आकार। ध्यान दें कि आंकड़ा बताता है

{\mathsf {P}}\neq {\mathsf {NP}}

और

{\mathsf {NP}}\neq {\mathsf {PSPACE}}

. अगर यह सच नहीं है तो आंकड़ा अलग दिखना चाहिए।

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

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

यह भी देखें

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

संदर्भ

↑ Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.
↑ Erickson, Jeff. "गैर नियतात्मक ट्यूरिंग मशीनें" (PDF). U. Illinois Urbana-Champaign. Retrieved 2019-04-07.
↑ Lewis, Harry R.; Papadimitriou, Christos (1981). "Section 4.6: Nondeterministic Turing machines". संगणना के सिद्धांत के तत्व (1st ed.). Englewood Cliffs, New Jersey: Prentice-Hall. pp. 204–211. ISBN 978-0132624787.
↑ The Orion Quantum Computer Anti-Hype FAQ, Scott Aaronson.
↑ Tušarová, Tereza (2004). "क्वांटम जटिलता वर्ग". arXiv:cs/0409051..

सामान्य

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.

बाहरी संबंध

[GJ-1] Garey, Michael R.; David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman. ISBN 0-7167-1045-5.

[jeffe-2] Erickson, Jeff. "गैर नियतात्मक ट्यूरिंग मशीनें" (PDF). U. Illinois Urbana-Champaign. Retrieved 2019-04-07.

[3] Lewis, Harry R.; Papadimitriou, Christos (1981). "Section 4.6: Nondeterministic Turing machines". संगणना के सिद्धांत के तत्व (1st ed.). Englewood Cliffs, New Jersey: Prentice-Hall. pp. 204–211. ISBN 978-0132624787.

[4] The Orion Quantum Computer Anti-Hype FAQ, Scott Aaronson.

[5] Tušarová, Tereza (2004). "क्वांटम जटिलता वर्ग". arXiv:cs/0409051..

[1]

[2]

[3]

[4]

[5]

@@ Line 2: / Line 2: @@
 {{Turing}}
-सैद्धांतिक [[कंप्यूटर विज्ञान]] में, एक गैर-[[नियतात्मक ट्यूरिंग मशीन]] (NTM) संगणना का एक सैद्धांतिक प्रारूप है जिसके संचालन नियम कुछ स्थितियों में एक से अधिक संभावित क्रियाओं को निर्दिष्ट करते हैं। अर्थात्, एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक NTM की अगली स्थिति पूर्ण रूप से इसकी क्रिया और इसके द्वारा देखे जाने वाले वर्तमान प्रतीक द्वारा निर्धारित नहीं होती है।
+सैद्धांतिक [[कंप्यूटर विज्ञान]] में, एक '''गैर-[[नियतात्मक ट्यूरिंग मशीन]]''' (एनटीएम) संगणना का एक सैद्धांतिक प्रारूप है जिसके संचालन नियम कुछ स्थितियों में एक से अधिक संभावित क्रियाओं को निर्दिष्ट करते हैं। अर्थात्, एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक एनटीएम की अगली स्थिति पूर्ण रूप से इसकी क्रिया और इसके द्वारा देखे जाने वाले वर्तमान प्रतीक द्वारा निर्धारित नहीं होती है।
-कंप्यूटर की क्षमताओं और सीमाओं की जांच करने के लिए कभी-कभी विचार प्रयोगों में NTM का उपयोग किया जाता है। [[सैद्धांतिक कंप्यूटर विज्ञान]] में सबसे महत्वपूर्ण प्रारंभिक समस्याओं में से एक [[पी बनाम एनपी समस्या|P के विपरीत NP समस्या]] है, जो (अन्य समतुल्य योगों के बीच) इस प्रश्न से संबंधित है कि नियतात्मक कंप्यूटर के साथ गैर-नियतात्मक संगणना का अनुकरण करना कितना कठिन है।
+कंप्यूटर की क्षमताओं और सीमाओं की जांच करने के लिए कभी-कभी विचार प्रयोगों में एनटीएम का उपयोग किया जाता है। [[सैद्धांतिक कंप्यूटर विज्ञान]] में सबसे महत्वपूर्ण प्रारंभिक समस्याओं में से एक [[पी बनाम एनपी समस्या|पी के विपरीत एनपी समस्या]] है, जो (अन्य समतुल्य योगों के बीच) इस प्रश्न से संबंधित है कि नियतात्मक कंप्यूटर के साथ गैर-नियतात्मक संगणना का अनुकरण करना कितना कठिन है।
 == पृष्ठभूमि ==
-संक्षेप में, एक ट्यूरिंग मशीन की कल्पना एक साधारण कंप्यूटर के रूप में की जाती है जो नियमों के एक सेट का सख्ती से पालन करते हुए अंतहीन टेप पर एक बार में प्रतीकों को पढ़ता और लिखता है। यह निर्धारित करता है कि उसे अपनी आंतरिक स्थिति के अनुसार आगे क्या कार्य करना चाहिए और वर्तमान में वह कौन सा प्रतीक देखता है। ट्यूरिंग मशीन के नियमों में से एक का एक उदाहरण इस प्रकार हो सकता है: यदि आप राज्य 2 में हैं और आपको 'ए' दिखाई देता है, तो इसे 'बी' में बदल दें, बाएँ जाएँ, और राज्य 3 में बदलें।
+संक्षेप में, एक ट्यूरिंग मशीन की कल्पना एक साधारण कंप्यूटर के रूप में की जाती है जो नियमों के एक समूह का सख्ती से पालन करते हुए अंतहीन टेप पर एक बार में प्रतीकों को पढ़ता और लिखता है। यह निर्धारित करता है कि उसे अपनी आंतरिक स्थिति के अनुसार आगे क्या कार्य करना चाहिए और वर्तमान में वह कौन सा प्रतीक प्रयोग करता हैं। ट्यूरिंग मशीन के नियमों में से एक उदाहरण इस प्रकार हो सकता है: यदि आप अवस्था 2 में हैं और आपको 'A' दिखाई देता है, तो इसे 'B' में परिवर्तित करे, बाएँ जाएँ, और अवस्था 3 में परिवर्तित कर दे।
 === नियतात्मक ट्यूरिंग मशीन ===
-नियतात्मक ट्यूरिंग मशीन (डीटीएम) में, नियमों का सेट किसी भी स्थिति के लिए किए जाने वाले अधिकतम एक कार्य को निर्धारित करता है।
+नियतात्मक ट्यूरिंग मशीन (डीटीएम) में, नियमों का समूह किसी भी स्थिति के लिए किए जाने वाले अधिकतम एक कार्य को निर्धारित करता है।
-नियतात्मक ट्यूरिंग मशीन में एक संक्रमण कार्य होता है, जो किसी दिए गए राज्य और प्रतीक के लिए टेप हेड के तहत तीन चीजें निर्दिष्ट करता है:
+नियतात्मक ट्यूरिंग मशीन में एक संक्रमण फलन होता है, जो किसी दिए गए अवस्था और प्रतीक के लिए  शीर्ष टेप के अनुसार तीन चीजें निर्दिष्ट करता है:
 *टेप पर लिखा जाने वाला प्रतीक (यह वर्तमान में उस स्थिति में प्रतीक के समान हो सकता है, या बिल्कुल भी नहीं लिखा जा सकता है, जिसके परिणामस्वरूप कोई व्यावहारिक परिवर्तन नहीं होता है),
-*वह दिशा (बाएं, दाएं या कोई भी नहीं) जिसमें सिर को हिलना चाहिए, और
+*वह दिशा (बाएं, दाएं या कोई भी नहीं) जिसमें शीर्ष को हिलना चाहिए, और
-* परिमित नियंत्रण की बाद की स्थिति।
+* परिमित नियंत्रण के बाद की स्थिति।
-उदाहरण के लिए, राज्य 3 में टेप पर एक X, DTM को टेप पर Y लिखवा सकता है, सिर को एक स्थिति दाईं ओर ले जा सकता है, और राज्य 5 पर स्विच कर सकता है।
+उदाहरण के लिए, अवस्था 3 में टेप पर एक X, डीटीएम को टेप पर Y लिखवा सकता है, शीर्ष को एक स्थिति दाईं तरफ ले जा सकता है, और अवस्था 5 पर परिवर्तित  कर सकता है।
 == अंतर्ज्ञान ==
-[[Image:Difference_between_deterministic_and_Nondeterministic.svg|thumb|350px|right| नियतात्मक और गैर-नियतात्मक संगणना की तुलना]]एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक गैर-नियतात्मक ट्यूरिंग मशीन (NTM) में नियमों का सेट किसी भी स्थिति के लिए एक से अधिक क्रियाओं को करने के लिए निर्धारित कर सकता है। उदाहरण के लिए, राज्य 3 में टेप पर X NTM को इसकी अनुमति दे सकता है:
+[[Image:Difference_between_deterministic_and_Nondeterministic.svg|thumb|350px|right| नियतात्मक और गैर-नियतात्मक संगणना की तुलना]]एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक गैर-नियतात्मक ट्यूरिंग मशीन (एनटीएम) में नियमों का समूह किसी भी स्थिति के लिए एक से अधिक क्रियाओं को करने के लिए निर्धारित कर सकता है। उदाहरण के लिए, अवस्था 3 में टेप पर X एनटीएम को इसकी अनुमति दे सकता है:
-* Y लिखें, दाएँ जाएँ और स्थिति 5 पर स्विच करें
+* Y लिखें, दाएँ जाएँ और स्थिति 5 पर बदले
 या
 * एक X लिखें, बाएँ जाएँ, और अवस्था 3 में रहें।
 ===कई नियमों का समाधान===
-NTM कैसे जानता है कि उसे इनमें से कौन सी कार्रवाई करनी चाहिए? इसे देखने के दो तरीके हैं। एक तो यह कहना है कि मशीन सबसे भाग्यशाली संभावित अनुमानक है; यह हमेशा एक संक्रमण चुनता है जो अंततः एक स्वीकार्य स्थिति की ओर ले जाता है, अगर ऐसा कोई संक्रमण होता है। दूसरा यह कल्पना करना है कि मशीन कई-दुनिया के सिद्धांत को कई प्रतियों में बदल देती है, जिनमें से प्रत्येक संभावित संक्रमणों में से एक का अनुसरण करती है। जबकि एक DTM के पास एक एकल संगणना पथ होता है, जिसका अनुसरण करता है, एक NTM के पास एक संगणना वृक्ष होता है। यदि पेड़ की कम से कम एक शाखा स्वीकृत शर्त के साथ रुकती है, तो NTM इनपुट को स्वीकार करता है।
+एनटीएम कैसे जानता है कि उसे इनमें से कौन सा कार्य करना चाहिए? इसे देखने के दो विधिया हैं। एक तो यह कहना है कि मशीन सबसे भाग्यशाली संभावित अनुमानक है; यह हमेशा एक संक्रमण चुनता है जो अंततः एक स्वीकार्य स्थिति की ओर ले जाता है, यदि ऐसा कोई संक्रमण होता है। दूसरा यह कल्पना करना है कि मशीन कई-नियमो के सिद्धांत को कई प्रतियों में बदल देती है, जिनमें से प्रत्येक संभावित संक्रमणों में से एक का अनुसरण करती है। जबकि एक डीटीएम के पास एक एकल संगणना पथ होता है तथा एक एनटीएम के पास एक संगणना वृक्ष होता है जिसका वह अनुसरण करता हैं। यदि वृक्ष की कम से कम एक शाखा स्वीकृत पक्ष के साथ रुकती है, तो एनटीएम इनपुट को स्वीकार करता है।
 == परिभाषा ==
-एक गैर नियतात्मक ट्यूरिंग मशीन को औपचारिक रूप से सिक्स-ट्यूपल के रूप में परिभाषित किया जा सकता है <math>M=(Q, \Sigma, \iota, \sqcup, A, \delta)</math>, कहाँ
+एक गैर नियतात्मक ट्यूरिंग मशीन को औपचारिक रूप से छः-ट्यूपल <math>M=(Q, \Sigma, \iota, \sqcup, A, \delta)</math> के रूप में परिभाषित किया जा सकता हैं, जहाँ
-*<math>Q</math> राज्यों का एक परिमित समूह है
+*<math>Q</math> अवस्थाओं का एक परिमित समूह है
-*<math>\Sigma</math> प्रतीकों का एक सीमित सेट है (टेप वर्णमाला)
+*<math>\Sigma</math> प्रतीकों का एक सीमित समूह है (टेप वर्णमाला)
 *<math>\iota \in Q</math> प्रारम्भिक अवस्था है
 *<math>\sqcup \in \Sigma</math> रिक्त चिन्ह है
-*<math>A \subseteq Q</math> (अंतिम) राज्यों को स्वीकार करने का सेट है
+*<math>A \subseteq Q</math> (अंतिम) अवस्थाओं को स्वीकार करने का समूह है
-*<math>\delta \subseteq \left(Q \backslash A \times \Sigma\right) \times \left( Q \times \Sigma \times \{L,S,R\} \right)</math> राज्यों और प्रतीकों पर एक संबंध है जिसे संक्रमण संबंध कहा जाता है। <math>L</math> बाईं ओर आंदोलन है, <math>S</math> कोई आंदोलन नहीं है, और <math>R</math> दाईं ओर आंदोलन है।
+*<math>\delta \subseteq \left(Q \backslash A \times \Sigma\right) \times \left( Q \times \Sigma \times \{L,S,R\} \right)</math> अवस्थाओं और प्रतीकों पर एक संबंध है जिसे संक्रमण संबंध कहा जाता है। <math>L</math> बाईं तरफ गतिशील है, <math>S</math> गतिशील नहीं है, और <math>R</math> दाईं तरफ गतिशील है।
-एक मानक (नियतात्मक) [[ट्यूरिंग मशीन]] के साथ अंतर यह है कि, नियतात्मक ट्यूरिंग मशीनों के लिए, संक्रमण संबंध केवल एक संबंध के बजाय एक कार्य है।
+एक मानक (नियतात्मक) [[ट्यूरिंग मशीन]] के साथ अंतर यह है कि, नियतात्मक ट्यूरिंग मशीनों के लिए, संक्रमण संबंध केवल एक संबंध के अतिरिक्त एक कार्य है।
-विन्यास और विन्यास पर पैदावार संबंध, जो टेप की किसी भी संभावित सामग्री को देखते हुए ट्यूरिंग मशीन की संभावित क्रियाओं का वर्णन करता है, मानक ट्यूरिंग मशीनों के लिए है, सिवाय इसके कि पैदावार संबंध अब एकल-मूल्यवान नहीं है। (यदि मशीन नियतात्मक है, तो संभावित संगणनाएँ एकल, संभवतः अनंत, पथ के सभी उपसर्ग हैं।)
+विन्यास और विन्यास पर उत्पाद संबंध, जो टेप की किसी भी संभावित सामग्री को देखते हुए ट्यूरिंग मशीन की संभावित क्रियाओं का वर्णन करता है, मानक ट्यूरिंग मशीनों के लिए है, इसके अतिरिक्त कि उत्पाद संबंध अब एकल मान नहीं है। (यदि मशीन नियतात्मक है, तो संभावित संगणनाएँ एकल, संभवतः अनंत, पथ के सभी उपसर्ग हैं।)
-एनटीएम के लिए इनपुट नियतात्मक ट्यूरिंग मशीन के समान ही प्रदान किया जाता है: मशीन को कॉन्फ़िगरेशन में शुरू किया जाता है जिसमें टेप हेड स्ट्रिंग के पहले अक्षर (यदि कोई हो) पर होता है, और टेप पूरी तरह से खाली होता है अन्यथा .
+एनटीएम के लिए इनपुट नियतात्मक ट्यूरिंग मशीन के समान ही प्रदान किया जाता है: मशीन को विन्यास में प्रारम्भ किया जाता हैं जिसमें शीर्ष टेप स्ट्रिंग के पहले अक्षर (यदि कोई हो) पर होता है, और अन्यथा टेप पूरी तरह से खाली होता है।
-एक एनटीएम एक इनपुट स्ट्रिंग स्वीकार करता है अगर और केवल तभी जब उस स्ट्रिंग से शुरू होने वाले संभावित कम्प्यूटेशनल पथों में से कम से कम एक मशीन को स्वीकार्य स्थिति में रखता है। नियतात्मक मशीन पर एक NTM के कई ब्रांचिंग पथों का अनुकरण करते समय, जैसे ही कोई शाखा एक स्वीकार्य स्थिति में पहुँचती है, हम संपूर्ण सिमुलेशन को रोक सकते हैं।
+एक एनटीएम एक इनपुट स्ट्रिंग स्वीकार करता है अगर और केवल तभी जब उस स्ट्रिंग से शुरू होने वाले संभावित विनिमय पथों में से कम से कम एक मशीन को स्वीकार्य स्थिति में रखता है। नियतात्मक मशीन पर एक एनटीएम के कई शाखा पथों का अनुकरण करते समय, जैसे ही कोई शाखा एक स्वीकार्य स्थिति में पहुँचती है, हम संपूर्ण अनुरूपण को रोक सकते हैं।
 === वैकल्पिक परिभाषाएं ===
-एक गणितीय निर्माण के रूप में मुख्य रूप से प्रमाणों में उपयोग किया जाता है, NTM की परिभाषा में कई प्रकार के छोटे बदलाव होते हैं, लेकिन ये विविधताएँ सभी समान भाषाओं को स्वीकार करती हैं।
+एक गणितीय निर्माण के रूप में मुख्य रूप से प्रमाणों में उपयोग किया जाता है, एनटीएम की परिभाषा में कई प्रकार के छोटे बदलाव होते हैं, लेकिन ये विविधताएँ सभी समान भाषाओं को स्वीकार करती हैं।
-ट्रांज़िशन रिलेशन के आउटपुट में हेड मूवमेंट को लेफ्ट (-1), स्टेशनरी (0), और राइट (+1) को ले जाने का प्रतिनिधित्व करने के लिए अक्षरों का उपयोग करने के बजाय अक्सर संख्यात्मक रूप से एन्कोड किया जाता है; का ट्रांजिशन फंक्शन आउटपुट दे रहा है <math>\left( Q \times \Sigma \times \{-1,0,+1\} \right)</math>. स्थिर (0) आउटपुट को छोड़ना आम बात है,<ref name="GJ">{{cite book|last=Garey|first=Michael R.|author2=David S. Johnson|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|publisher=W. H. Freeman|year=1979|isbn=0-7167-1045-5|url-access=registration|url=https://archive.org/details/computersintract0000gare}}</ref> और इसके बजाय किसी भी वांछित स्थिर संक्रमण के सकर्मक समापन को सम्मिलित करें।
+संक्रमण सम्बन्ध के आउटपुट में शीर्ष परिवर्तन को बाये से (-1), स्थायी (0), और दाये से (+1) को ले जाने का प्रतिनिधित्व करने के लिए अक्षरों का उपयोग करने के जगह प्रायः संख्यात्मक रूप से सांकेतिक शब्दो में बदला जाता हैं; का संक्रमण फलन आउटपुट <math>\left( Q \times \Sigma \times \{-1,0,+1\} \right)</math> देता हैं। स्थिर (0) आउटपुट को छोड़ देना साधारण बात हैं,<ref name="GJ">{{cite book|last=Garey|first=Michael R.|author2=David S. Johnson|title=Computers and Intractability: A Guide to the Theory of NP-Completeness|publisher=W. H. Freeman|year=1979|isbn=0-7167-1045-5|url-access=registration|url=https://archive.org/details/computersintract0000gare}}</ref> और इसके अतिरिक्त किसी भी वांछित स्थिर संक्रमण के सकर्मक समापन को सम्मिलित करें।
-कुछ लेखक एक स्पष्ट अस्वीकृत स्थिति जोड़ते हैं,<ref name="jeffe">{{cite web |url=http://jeffe.cs.illinois.edu/teaching/algorithms/models/09-nondeterminism.pdf|title=गैर नियतात्मक ट्यूरिंग मशीनें|last=Erickson|first=Jeff|publisher=U. Illinois Urbana-Champaign|access-date=2019-04-07}}</ref>
+कुछ लेखक एक स्पष्ट अस्वीकृत स्थिति जोड़ते हैं,<ref name="jeffe">{{cite web |url=http://jeffe.cs.illinois.edu/teaching/algorithms/models/09-nondeterminism.pdf|title=गैर नियतात्मक ट्यूरिंग मशीनें|last=Erickson|first=Jeff|publisher=U. Illinois Urbana-Champaign|access-date=2019-04-07}}</ref> जिसके कारण एनटीएम बिना स्वीकार किए रुक जाता है। यह परिभाषा अभी भी विषमता को बनाये रखती है जिसे कोई भी गैर-नियतात्मक शाखा स्वीकार कर सकती है, लेकिन स्ट्रिंग को अस्वीकार करने के लिए प्रत्येक शाखा को अस्वीकार करना होगा।
-जिसके कारण NTM बिना स्वीकार किए रुक जाता है। यह परिभाषा अभी भी विषमता को बरकरार रखती है जिसे कोई भी गैर-नियतात्मक शाखा स्वीकार कर सकती है, लेकिन स्ट्रिंग को अस्वीकार करने के लिए प्रत्येक शाखा को अस्वीकार करना होगा।
 == डीटीएम के साथ कम्प्यूटेशनल समकक्ष ==
-कोई कम्प्यूटेशनल समस्या जिसे डीटीएम द्वारा हल किया जा सकता है, एनटीएम द्वारा हल किया जा सकता है, और इसके विपरीत। हालांकि, यह माना जाता है कि सामान्य तौर पर समय की जटिलता समान नहीं हो सकती है।
+कोई कम्प्यूटेशनल(अभिकलनीय) समस्या जिसे डीटीएम द्वारा हल किया जा सकता है, और इसके विपरीत एनटीएम द्वारा भी हल किया जा सकता है। जबकि, यह माना जाता है कि सामान्य तौर पर समय की जटिलता समान नहीं हो सकती है।
-=== एनटीएम === के एक विशेष मामले के रूप में डीटीएम
+'''एनटीएम के एक विशेष कथन के रूप में डीटीएम'''
-एनटीएम में डीटीएम को विशेष मामलों के रूप में शामिल किया गया है, इसलिए डीटीएम द्वारा की जा सकने वाली प्रत्येक गणना समकक्ष एनटीएम द्वारा भी की जा सकती है।
-=== एनटीएम === का डीटीएम अनुकरण
+एनटीएम में डीटीएम को विशेष कथनो के रूप में सम्मलित किया गया है, इसलिए डीटीएम द्वारा की जा सकने वाली प्रत्येक गणना समकक्ष एनटीएम द्वारा भी की जा सकती है।
-ऐसा लग सकता है कि एनटीएम डीटीएम की तुलना में अधिक शक्तिशाली हैं, क्योंकि वे एक ही प्रारंभिक कॉन्फ़िगरेशन से उत्पन्न होने वाली संभावित कम्प्यूटेशंस के पेड़ को अनुमति दे सकते हैं, अगर पेड़ में कोई एक शाखा इसे स्वीकार करती है तो स्ट्रिंग को स्वीकार कर सकती है। हालांकि, एनटीएम को डीटीएम के साथ अनुकरण करना संभव है, और वास्तव में यह एक से अधिक तरीकों से किया जा सकता है।
-==== कॉन्फ़िगरेशन राज्यों की बहुलता ====
+'''एनटीएम का डीटीएम अनुकरण'''
-एक दृष्टिकोण एक DTM का उपयोग करना है, जिसमें कॉन्फ़िगरेशन NTM के कई कॉन्फ़िगरेशन का प्रतिनिधित्व करता है, और DTM के संचालन में उनमें से प्रत्येक पर बारी-बारी से जाना होता है, प्रत्येक विज़िट पर एक ही चरण को निष्पादित करना, और जब भी संक्रमण संबंध कई निरंतरताओं को परिभाषित करता है, तो नए कॉन्फ़िगरेशन को जन्म देता है। .
+ऐसा लग सकता है कि एनटीएम, डीटीएम की तुलना में अधिक शक्तिशाली हैं, क्योंकि वे एक ही प्रारंभिक विन्यास से उत्पन्न होने वाली संभावित कम्प्यूटेशंस (अभिकलन) के वृक्ष को अनुमति दे सकते हैं, अगर वृक्ष में कोई एक शाखा इसे स्वीकार करती है तो स्ट्रिंग को स्वीकार कर सकती है। जबकि, एनटीएम को डीटीएम के साथ अनुकरण करना संभव है, और वास्तव में यह एक से अधिक प्रकारो से किया जा सकता है।
+==== विन्यास अवस्थाओं की बहुलता ====
+एक दृष्टिकोण एक डीटीएम का उपयोग करना है, जिसमें विन्यास एनटीएम के कई विन्यासो का प्रतिनिधित्व करता है, और डीटीएम के संचालन में उनमें से प्रत्येक पर बारी-बारी से जाना होता है, प्रत्येक पहुंच पर एक ही चरण को निष्पादित करना, और जब भी संक्रमण संबंध कई निरंतरताओं को परिभाषित करता है, तो नए विन्यासो को निर्मित करता हैं। .
 ==== टेपों की बहुलता ====
-एक और निर्माण 3-टेप डीटीएम के साथ एनटीएम का अनुकरण करता है, जिनमें से पहला टेप हमेशा मूल इनपुट स्ट्रिंग रखता है, दूसरे का उपयोग एनटीएम की एक विशेष गणना को अनुकरण करने के लिए किया जाता है, और तीसरा एनटीएम के गणना पेड़ में पथ को एन्कोड करता है।<ref>{{cite book |last1=Lewis |first1=Harry R. |author1-link=Harry R. Lewis |last2=Papadimitriou |first2=Christos |author2-link=Christos Papadimitriou |year=1981 |chapter=Section 4.6: Nondeterministic Turing machines |title=संगणना के सिद्धांत के तत्व|publisher=Prentice-Hall |place=Englewood Cliffs, New Jersey |edition=1st |pages=204–211 |isbn=978-0132624787 |url-access=registration |url=https://archive.org/details/elementsoftheory0000lewi}}</ref> 3-टेप डीटीएम को सामान्य सिंगल-टेप डीटीएम के साथ आसानी से अनुकरण किया जाता है।
+एक और निर्माण 3-टेप डीटीएम के साथ एनटीएम का अनुकरण करता है, जिनमें से पहला टेप हमेशा मूल इनपुट स्ट्रिंग रखता है, दूसरे का उपयोग एनटीएम की एक विशेष गणना को अनुकरण करने के लिए किया जाता है, और तीसरा एनटीएम के गणना वृक्ष में पथ को सांकेतिक शब्दो में निर्मित करता हैं।<ref>{{cite book |last1=Lewis |first1=Harry R. |author1-link=Harry R. Lewis |last2=Papadimitriou |first2=Christos |author2-link=Christos Papadimitriou |year=1981 |chapter=Section 4.6: Nondeterministic Turing machines |title=संगणना के सिद्धांत के तत्व|publisher=Prentice-Hall |place=Englewood Cliffs, New Jersey |edition=1st |pages=204–211 |isbn=978-0132624787 |url-access=registration |url=https://archive.org/details/elementsoftheory0000lewi}}</ref> 3-टेप डीटीएम को सामान्य एकल-टेप डीटीएम के साथ आसानी से अनुकरण किया जाता है।
 ==== समय जटिलता और पी बनाम एनपी ====
-{{Main|P versus NP problem}}
+{{Main|पी बनाम एनपी समस्या}}
-दूसरे निर्माण में, निर्मित डीटीएम प्रभावी ढंग से एनटीएम के कम्प्यूटेशन ट्री की चौड़ाई-पहली खोज करता है, लंबाई बढ़ाने के क्रम में एनटीएम की सभी संभावित संगणनाओं का दौरा करता है जब तक कि यह एक स्वीकार्य नहीं हो जाता। इसलिए, डीटीएम की स्वीकार्य गणना की लंबाई सामान्य रूप से एनटीएम की सबसे छोटी स्वीकार्य गणना की लंबाई में घातीय है। यह डीटीएम द्वारा एनटीएम के सिमुलेशन की एक सामान्य संपत्ति माना जाता है। पी = एनपी समस्या, कंप्यूटर विज्ञान में सबसे प्रसिद्ध अनसुलझा प्रश्न, इस मुद्दे के एक मामले से संबंधित है: बहुपद समय में एनटीएम द्वारा हल की जाने वाली हर समस्या अनिवार्य रूप से बहुपद समय में डीटीएम द्वारा हल करने योग्य है या नहीं।
-== परिबद्ध nondeterminism ==
+दूसरे निर्माण में, निर्मित डीटीएम प्रभावी रूप से एनटीएम के कम्प्यूटेशन (अभिकलन) पहले ट्री की चौड़ाई की खोज करता हैं, तब लंबाई बढ़ाने के क्रम में एनटीएम की सभी संभावित संगणनाओं का चक्कर लगाता हैं जब तक कि यह एक स्वीकार्य नहीं हो जाता। इसलिए, डीटीएम की स्वीकार्य गणना की लंबाई सामान्य रूप से एनटीएम की सबसे छोटी स्वीकार्य गणना की लंबाई में घातीय है। यह डीटीएम द्वारा एनटीएम के अनुरूपण की एक सामान्य संपत्ति माना जाता है। पी = एनपी समस्या कंप्यूटर विज्ञान में सबसे प्रसिद्ध अज्ञात प्रश्न, इस समस्या के एक कथन से संबंधित है: जो यह है की बहुपद समय में एनटीएम द्वारा हल की जाने वाली प्रत्येक समस्या, अनिवार्य रूप से बहुपद समय में डीटीएम द्वारा हल करने योग्य है या नहीं है।
-एक NTM में परिबद्ध nondeterminism का गुण होता है। यही है, यदि कोई NTM हमेशा किसी दिए गए इनपुट टेप T पर रुकता है तो यह सीमित संख्या में चरणों में रुकता है, और इसलिए केवल संभावित कॉन्फ़िगरेशन की सीमित संख्या हो सकती है।
+== गैर-नियतात्मक परिबद्ध ==
+एक एनटीएम में गैर-नियतात्मक परिबद्ध का गुण होता है। यदि कोई एनटीएम हमेशा किसी दिए गए इनपुट टेप T पर रुकता है तो यह सीमित संख्या के चरणों में रुकता है, और इसलिए केवल संभावित विन्यासो की सीमित संख्या हो सकती है।
 == क्वांटम कंप्यूटर्स के साथ तुलना ==
-[[File:BQP complexity class diagram.svg|thumb|[[BQP]] (BQP) समस्याओं की श्रेणी का संदिग्ध आकार। ध्यान दें कि आंकड़ा बताता है <math>\mathsf P \neq \mathsf{NP}</math> और <math>\mathsf{NP} \neq \mathsf{PSPACE}</math>. अगर यह सच नहीं है तो आंकड़ा अलग दिखना चाहिए।]]क्योंकि [[ एक कंप्यूटर जितना ]] [[ कितना ]]्स का उपयोग करते हैं, जो पारंपरिक बिट्स के बजाय राज्यों के [[ क्वांटम सुपरइम्पोजिशन ]] में हो सकते हैं, कभी-कभी यह गलत धारणा है कि क्वांटम कंप्यूटर एनटीएम हैं।<ref>[http://www.scottaaronson.com/blog/?p=198 The Orion Quantum Computer Anti-Hype FAQ], [[Scott Aaronson]].</ref> हालाँकि, यह विशेषज्ञों द्वारा माना जाता है (लेकिन सिद्ध नहीं हुआ है) कि क्वांटम कंप्यूटर की शक्ति, वास्तव में, एनटीएम की तुलना में अतुलनीय है; अर्थात्, समस्याएँ मौजूद होने की संभावना है कि एक NTM कुशलता से हल कर सकता है जिसे एक क्वांटम कंप्यूटर नहीं कर सकता है और इसके विपरीत।<ref>{{cite arXiv|first=Tereza|last=Tušarová|title=क्वांटम जटिलता वर्ग|year=2004|eprint=cs/0409051}}.</ref>{{better source needed|date=September 2017}} विशेष रूप से, यह संभावना है कि एनपी-पूर्ण समस्याएं एनटीएम द्वारा हल की जा सकती हैं लेकिन बहुपद समय में क्वांटम कंप्यूटर द्वारा नहीं।
+[[File:BQP complexity class diagram.svg|thumb|[[BQP|बीक्यूँपी]] (बीक्यूँपी) समस्याओं की श्रेणी का संदिग्ध आकार। ध्यान दें कि आंकड़ा बताता है <math>\mathsf P \neq \mathsf{NP}</math> और <math>\mathsf{NP} \neq \mathsf{PSPACE}</math>. अगर यह सच नहीं है तो आंकड़ा अलग दिखना चाहिए।]]क्योंकि[[ कितना | क्वांटम कम्प्यूटर्स, क्वांटम बिट्स]] का उपयोग करते हैं, जो पारंपरिक बिट्स के अतिरिक्त अवस्थाओं के[[ क्वांटम सुपरइम्पोजिशन | अध्यारोपण]] में हो सकते हैं, कभी-कभी यह गलत धारणा है कि क्वांटम कंप्यूटर एनटीएम हैं।<ref>[http://www.scottaaronson.com/blog/?p=198 The Orion Quantum Computer Anti-Hype FAQ], [[Scott Aaronson]].</ref> जबकि, यह विशेषज्ञों द्वारा माना जाता है (लेकिन सिद्ध नहीं हुआ है) कि क्वांटम कंप्यूटर की शक्ति, वास्तव में, एनटीएम की तुलना में अतुलनीय है; अर्थात् समस्याएँ उपलब्ध होने की संभावना है कि एक एनटीएम कुशलता से हल कर सकता है इसके विपरीत जिसे एक क्वांटम कंप्यूटर नहीं कर सकता है ।<ref>{{cite arXiv|first=Tereza|last=Tušarová|title=क्वांटम जटिलता वर्ग|year=2004|eprint=cs/0409051}}.</ref> विशेष रूप से, यह संभावना है कि एनपी-पूर्ण समस्याएं एनटीएम द्वारा हल की जा सकती हैं लेकिन बहुपद समय में क्वांटम कंप्यूटर द्वारा नहीं की जा सकती हैं।
-सहज रूप से बोलते हुए, जबकि एक क्वांटम कंप्यूटर वास्तव में एक सुपरपोज़िशन स्थिति में हो सकता है, जो एक ही समय में निष्पादित सभी संभावित कम्प्यूटेशनल शाखाओं के अनुरूप हो सकता है (एनटीएम के समान), अंतिम माप क्वांटम कंप्यूटर को यादृच्छिक रूप से चयनित शाखा में ध्वस्त कर देगा। यह शाखा सामान्य रूप से एनटीएम के विपरीत मांगे गए समाधान का प्रतिनिधित्व नहीं करती है, जिसे घातीय रूप से कई शाखाओं के बीच सही समाधान चुनने की अनुमति है।
+सहज रूप से बताया जाये तो, जबकि एक क्वांटम कंप्यूटर वास्तव में एक अध्यारोपण स्थिति में हो सकता है, जो एक ही समय में निष्पादित सभी संभावित कम्प्यूटेशनल (अभिकलनीय) शाखाओं के अनुरूप हो सकता है (एनटीएम के समान), अंतिम माप क्वांटम कंप्यूटर को यादृच्छिक रूप से चयनित शाखा में खंडित कर देगा। यह शाखा सामान्य रूप से एनटीएम के विपरीत चुने गए समाधान का प्रतिनिधित्व नहीं करती है, जिसे घातीय रूप से कई शाखाओं के बीच सही समाधान चुनने की अनुमति  होती है।
 == यह भी देखें ==
@@ Line 84: / Line 86: @@
 ==संदर्भ==
 {{Reflist}}
 === सामान्य ===
-{{more citations needed|date=January 2019}}
 *{{cite book |last=Martin |first=John C. |year=1997 |chapter=Section 9.6: Nondeterministic Turing machines |title=भाषाओं का परिचय और संगणना का सिद्धांत|publisher=McGraw-Hill |edition=2nd |pages=277–281 |isbn=978-0073191461 |url-access=registration |url=https://archive.org/details/introductiontola0002mart}}
 *{{cite book |last=Papadimitriou |first=Christos |author-link=Christos Papadimitriou |year=1993 |chapter=Section 2.7: Nondeterministic machines |title=अभिकलनात्मक जटिलता|publisher=Addison-Wesley |edition=1st |pages=45–50 |isbn=978-0201530827}}
@@ Line 97: / Line 94: @@
 *[http://sourceforge.net/projects/turing-machine/ C++ Simulator of a Nondeterministic Multitape Turing Machine download link from sourceforge.net]
-{{Authority control}}
+{{DEFAULTSORT:NonDeterministic Turing Machine}}
-{{DEFAULTSORT:NonDeterministic Turing Machine}}[[Category: ट्यूरिंग मशीन]]
-[[Category: Machine Translated Page]]
+[[Category:Articles with hatnote templates targeting a nonexistent page|NonDeterministic Turing Machine]]
-[[Category:Created On 07/05/2023]]
+[[Category:Created On 07/05/2023|NonDeterministic Turing Machine]]
+[[Category:Lua-based templates|NonDeterministic Turing Machine]]
+[[Category:Machine Translated Page|NonDeterministic Turing Machine]]
+[[Category:Pages with script errors|NonDeterministic Turing Machine]]
+[[Category:Short description with empty Wikidata description|NonDeterministic Turing Machine]]
+[[Category:Templates Vigyan Ready|NonDeterministic Turing Machine]]
+[[Category:Templates that add a tracking category|NonDeterministic Turing Machine]]
+[[Category:Templates that generate short descriptions|NonDeterministic Turing Machine]]
+[[Category:Templates using TemplateData|NonDeterministic Turing Machine]]
+[[Category:ट्यूरिंग मशीन|NonDeterministic Turing Machine]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 17:39, 29 August 2023

Contents

पृष्ठभूमि

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

अंतर्ज्ञान

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

परिभाषा

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

सामान्य

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 17:39, 29 August 2023

पृष्ठभूमि

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

अंतर्ज्ञान

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

परिभाषा

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

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

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

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

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

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

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

यह भी देखें

संदर्भ

सामान्य

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories