गैर नियतात्मक ट्यूरिंग मशीन: 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}}
-सैद्धांतिक [[कंप्यूटर विज्ञान]] में, एक गैर-[[नियतात्मक ट्यूरिंग मशीन]] (एनटीऍम) संगणना का एक सैद्धांतिक प्रारूप है जिसके संचालन नियम कुछ स्थितियों में एक से अधिक संभावित क्रियाओं को निर्दिष्ट करते हैं। अर्थात्, एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक एनटीऍम की अगली स्थिति पूर्ण रूप से इसकी क्रिया और इसके द्वारा देखे जाने वाले वर्तमान प्रतीक द्वारा निर्धारित नहीं होती है।
+सैद्धांतिक [[कंप्यूटर विज्ञान]] में, एक '''गैर-[[नियतात्मक ट्यूरिंग मशीन]]''' (एनटीएम) संगणना का एक सैद्धांतिक प्रारूप है जिसके संचालन नियम कुछ स्थितियों में एक से अधिक संभावित क्रियाओं को निर्दिष्ट करते हैं। अर्थात्, एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक एनटीएम की अगली स्थिति पूर्ण रूप से इसकी क्रिया और इसके द्वारा देखे जाने वाले वर्तमान प्रतीक द्वारा निर्धारित नहीं होती है।
-कंप्यूटर की क्षमताओं और सीमाओं की जांच करने के लिए कभी-कभी विचार प्रयोगों में एनटीऍम का उपयोग किया जाता है। [[सैद्धांतिक कंप्यूटर विज्ञान]] में सबसे महत्वपूर्ण प्रारंभिक समस्याओं में से एक [[पी बनाम एनपी समस्या|पी के विपरीत एनपी समस्या]] है, जो (अन्य समतुल्य योगों के बीच) इस प्रश्न से संबंधित है कि नियतात्मक कंप्यूटर के साथ गैर-नियतात्मक संगणना का अनुकरण करना कितना कठिन है।
+कंप्यूटर की क्षमताओं और सीमाओं की जांच करने के लिए कभी-कभी विचार प्रयोगों में एनटीएम का उपयोग किया जाता है। [[सैद्धांतिक कंप्यूटर विज्ञान]] में सबसे महत्वपूर्ण प्रारंभिक समस्याओं में से एक [[पी बनाम एनपी समस्या|पी के विपरीत एनपी समस्या]] है, जो (अन्य समतुल्य योगों के बीच) इस प्रश्न से संबंधित है कि नियतात्मक कंप्यूटर के साथ गैर-नियतात्मक संगणना का अनुकरण करना कितना कठिन है।
 == पृष्ठभूमि ==
@@ Line 10: / Line 10: @@
 === नियतात्मक ट्यूरिंग मशीन ===
-नियतात्मक ट्यूरिंग मशीन (डीटीऍम) में, नियमों का समूह किसी भी स्थिति के लिए किए जाने वाले अधिकतम एक कार्य को निर्धारित करता है।
+नियतात्मक ट्यूरिंग मशीन (डीटीएम) में, नियमों का समूह किसी भी स्थिति के लिए किए जाने वाले अधिकतम एक कार्य को निर्धारित करता है।
 नियतात्मक ट्यूरिंग मशीन में एक संक्रमण फलन होता है, जो किसी दिए गए अवस्था और प्रतीक के लिए  शीर्ष टेप के अनुसार तीन चीजें निर्दिष्ट करता है:
@@ Line 16: / Line 16: @@
 *वह दिशा (बाएं, दाएं या कोई भी नहीं) जिसमें शीर्ष को हिलना चाहिए, और
 * परिमित नियंत्रण के बाद की स्थिति।
-उदाहरण के लिए, अवस्था 3 में टेप पर एक X,डीटीऍम को टेप पर Y लिखवा सकता है, शीर्ष को एक स्थिति दाईं तरफ ले जा सकता है, और अवस्था 5 पर परिवर्तित  कर सकता है।
+उदाहरण के लिए, अवस्था 3 में टेप पर एक X, डीटीएम को टेप पर Y लिखवा सकता है, शीर्ष को एक स्थिति दाईं तरफ ले जा सकता है, और अवस्था 5 पर परिवर्तित  कर सकता है।
 == अंतर्ज्ञान ==
-[[Image:Difference_between_deterministic_and_Nondeterministic.svg|thumb|350px|right| नियतात्मक और गैर-नियतात्मक संगणना की तुलना]]एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक गैर-नियतात्मक ट्यूरिंग मशीन (एनटीऍम) में नियमों का समूह किसी भी स्थिति के लिए एक से अधिक क्रियाओं को करने के लिए निर्धारित कर सकता है। उदाहरण के लिए, अवस्था 3 में टेप पर X एनटीऍम को इसकी अनुमति दे सकता है:
+[[Image:Difference_between_deterministic_and_Nondeterministic.svg|thumb|350px|right| नियतात्मक और गैर-नियतात्मक संगणना की तुलना]]एक नियतात्मक ट्यूरिंग मशीन के विपरीत, एक गैर-नियतात्मक ट्यूरिंग मशीन (एनटीएम) में नियमों का समूह किसी भी स्थिति के लिए एक से अधिक क्रियाओं को करने के लिए निर्धारित कर सकता है। उदाहरण के लिए, अवस्था 3 में टेप पर X एनटीएम को इसकी अनुमति दे सकता है:
 * Y लिखें, दाएँ जाएँ और स्थिति 5 पर बदले
 या
@@ Line 25: / Line 25: @@
 ===कई नियमों का समाधान===
-एनटीऍम कैसे जानता है कि उसे इनमें से कौन सा कार्य करना चाहिए? इसे देखने के दो विधिया हैं। एक तो यह कहना है कि मशीन सबसे भाग्यशाली संभावित अनुमानक है; यह हमेशा एक संक्रमण चुनता है जो अंततः एक स्वीकार्य स्थिति की ओर ले जाता है, यदि ऐसा कोई संक्रमण होता है। दूसरा यह कल्पना करना है कि मशीन कई-नियमो के सिद्धांत को कई प्रतियों में बदल देती है, जिनमें से प्रत्येक संभावित संक्रमणों में से एक का अनुसरण करती है। जबकि एक डीटीऍम के पास एक एकल संगणना पथ होता है तथा एक एनटीऍम के पास एक संगणना वृक्ष होता है जिसका वह अनुसरण करता हैं। यदि वृक्ष की कम से कम एक शाखा स्वीकृत पक्ष के साथ रुकती है, तो एनटीऍम इनपुट को स्वीकार करता है।
+एनटीएम कैसे जानता है कि उसे इनमें से कौन सा कार्य करना चाहिए? इसे देखने के दो विधिया हैं। एक तो यह कहना है कि मशीन सबसे भाग्यशाली संभावित अनुमानक है; यह हमेशा एक संक्रमण चुनता है जो अंततः एक स्वीकार्य स्थिति की ओर ले जाता है, यदि ऐसा कोई संक्रमण होता है। दूसरा यह कल्पना करना है कि मशीन कई-नियमो के सिद्धांत को कई प्रतियों में बदल देती है, जिनमें से प्रत्येक संभावित संक्रमणों में से एक का अनुसरण करती है। जबकि एक डीटीएम के पास एक एकल संगणना पथ होता है तथा एक एनटीएम के पास एक संगणना वृक्ष होता है जिसका वह अनुसरण करता हैं। यदि वृक्ष की कम से कम एक शाखा स्वीकृत पक्ष के साथ रुकती है, तो एनटीएम इनपुट को स्वीकार करता है।
 == परिभाषा ==
@@ Line 40: / Line 40: @@
 विन्यास और विन्यास पर उत्पाद संबंध, जो टेप की किसी भी संभावित सामग्री को देखते हुए ट्यूरिंग मशीन की संभावित क्रियाओं का वर्णन करता है, मानक ट्यूरिंग मशीनों के लिए है, इसके अतिरिक्त कि उत्पाद संबंध अब एकल मान नहीं है। (यदि मशीन नियतात्मक है, तो संभावित संगणनाएँ एकल, संभवतः अनंत, पथ के सभी उपसर्ग हैं।)
-एनटीऍम के लिए इनपुट नियतात्मक ट्यूरिंग मशीन के समान ही प्रदान किया जाता है: मशीन को विन्यास में प्रारम्भ किया जाता हैं जिसमें शीर्ष टेप स्ट्रिंग के पहले अक्षर (यदि कोई हो) पर होता है, और अन्यथा टेप पूरी तरह से खाली होता है।
+एनटीएम के लिए इनपुट नियतात्मक ट्यूरिंग मशीन के समान ही प्रदान किया जाता है: मशीन को विन्यास में प्रारम्भ किया जाता हैं जिसमें शीर्ष टेप स्ट्रिंग के पहले अक्षर (यदि कोई हो) पर होता है, और अन्यथा टेप पूरी तरह से खाली होता है।
-एक एनटीऍम एक इनपुट स्ट्रिंग स्वीकार करता है अगर और केवल तभी जब उस स्ट्रिंग से शुरू होने वाले संभावित विनिमय पथों में से कम से कम एक मशीन को स्वीकार्य स्थिति में रखता है। नियतात्मक मशीन पर एक एनटीऍम के कई शाखा पथों का अनुकरण करते समय, जैसे ही कोई शाखा एक स्वीकार्य स्थिति में पहुँचती है, हम संपूर्ण अनुरूपण को रोक सकते हैं।
+एक एनटीएम एक इनपुट स्ट्रिंग स्वीकार करता है अगर और केवल तभी जब उस स्ट्रिंग से शुरू होने वाले संभावित विनिमय पथों में से कम से कम एक मशीन को स्वीकार्य स्थिति में रखता है। नियतात्मक मशीन पर एक एनटीएम के कई शाखा पथों का अनुकरण करते समय, जैसे ही कोई शाखा एक स्वीकार्य स्थिति में पहुँचती है, हम संपूर्ण अनुरूपण को रोक सकते हैं।
 === वैकल्पिक परिभाषाएं ===
-एक गणितीय निर्माण के रूप में मुख्य रूप से प्रमाणों में उपयोग किया जाता है, एनटीऍम की परिभाषा में कई प्रकार के छोटे बदलाव होते हैं, लेकिन ये विविधताएँ सभी समान भाषाओं को स्वीकार करती हैं।
+एक गणितीय निर्माण के रूप में मुख्य रूप से प्रमाणों में उपयोग किया जाता है, एनटीएम की परिभाषा में कई प्रकार के छोटे बदलाव होते हैं, लेकिन ये विविधताएँ सभी समान भाषाओं को स्वीकार करती हैं।
 संक्रमण सम्बन्ध के आउटपुट में शीर्ष परिवर्तन को बाये से (-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> जिसके कारण एनटीएम बिना स्वीकार किए रुक जाता है। यह परिभाषा अभी भी विषमता को बनाये रखती है जिसे कोई भी गैर-नियतात्मक शाखा स्वीकार कर सकती है, लेकिन स्ट्रिंग को अस्वीकार करने के लिए प्रत्येक शाखा को अस्वीकार करना होगा।
-== डीटीऍम के साथ कम्प्यूटेशनल समकक्ष ==
+== डीटीएम के साथ कम्प्यूटेशनल समकक्ष ==
-कोई कम्प्यूटेशनल(अभिकलनीय) समस्या जिसे डीटीऍम द्वारा हल किया जा सकता है, और इसके विपरीत एनटीऍम द्वारा भी हल किया जा सकता है। जबकि, यह माना जाता है कि सामान्य तौर पर समय की जटिलता समान नहीं हो सकती है।
+कोई कम्प्यूटेशनल(अभिकलनीय) समस्या जिसे डीटीएम द्वारा हल किया जा सकता है, और इसके विपरीत एनटीएम द्वारा भी हल किया जा सकता है। जबकि, यह माना जाता है कि सामान्य तौर पर समय की जटिलता समान नहीं हो सकती है।
-'''एनटीऍम के एक विशेष कथन के रूप में डीटीऍम'''
+'''एनटीएम के एक विशेष कथन के रूप में डीटीएम'''
-एनटीऍम में डीटीऍम को विशेष कथनो के रूप में सम्मलित किया गया है, इसलिए डीटीऍम द्वारा की जा सकने वाली प्रत्येक गणना समकक्ष एनटीऍम द्वारा भी की जा सकती है।
+एनटीएम में डीटीएम को विशेष कथनो के रूप में सम्मलित किया गया है, इसलिए डीटीएम द्वारा की जा सकने वाली प्रत्येक गणना समकक्ष एनटीएम द्वारा भी की जा सकती है।
-'''एनटीऍम का डीटीऍम अनुकरण'''
+'''एनटीएम का डीटीएम अनुकरण'''
-ऐसा लग सकता है कि एनटीऍम, डीटीऍम की तुलना में अधिक शक्तिशाली हैं, क्योंकि वे एक ही प्रारंभिक विन्यास से उत्पन्न होने वाली संभावित कम्प्यूटेशंस (अभिकलन) के वृक्ष को अनुमति दे सकते हैं, अगर वृक्ष में कोई एक शाखा इसे स्वीकार करती है तो स्ट्रिंग को स्वीकार कर सकती है। जबकि, एनटीऍम को डीटीऍम के साथ अनुकरण करना संभव है, और वास्तव में यह एक से अधिक प्रकारो से किया जा सकता है।
+ऐसा लग सकता है कि एनटीएम, डीटीएम की तुलना में अधिक शक्तिशाली हैं, क्योंकि वे एक ही प्रारंभिक विन्यास से उत्पन्न होने वाली संभावित कम्प्यूटेशंस (अभिकलन) के वृक्ष को अनुमति दे सकते हैं, अगर वृक्ष में कोई एक शाखा इसे स्वीकार करती है तो स्ट्रिंग को स्वीकार कर सकती है। जबकि, एनटीएम को डीटीएम के साथ अनुकरण करना संभव है, और वास्तव में यह एक से अधिक प्रकारो से किया जा सकता है।
 ==== विन्यास अवस्थाओं की बहुलता ====
-एक दृष्टिकोण एक डीटीऍम का उपयोग करना है, जिसमें विन्यास एनटीऍम के कई विन्यासो का प्रतिनिधित्व करता है, और डीटीऍम के संचालन में उनमें से प्रत्येक पर बारी-बारी से जाना होता है, प्रत्येक पहुंच पर एक ही चरण को निष्पादित करना, और जब भी संक्रमण संबंध कई निरंतरताओं को परिभाषित करता है, तो नए विन्यासो को निर्मित करता हैं। .
+एक दृष्टिकोण एक डीटीएम का उपयोग करना है, जिसमें विन्यास एनटीएम के कई विन्यासो का प्रतिनिधित्व करता है, और डीटीएम के संचालन में उनमें से प्रत्येक पर बारी-बारी से जाना होता है, प्रत्येक पहुंच पर एक ही चरण को निष्पादित करना, और जब भी संक्रमण संबंध कई निरंतरताओं को परिभाषित करता है, तो नए विन्यासो को निर्मित करता हैं। .
 ==== टेपों की बहुलता ====
-एक और निर्माण 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|पी बनाम एनपी समस्या}}
-दूसरे निर्माण में, निर्मित डीटीऍम प्रभावी रूप से एनटीऍम के कम्प्यूटेशन (अभिकलन) पहले ट्री की चौड़ाई की खोज करता हैं, तब लंबाई बढ़ाने के क्रम में एनटीऍम की सभी संभावित संगणनाओं का चक्कर लगाता हैं जब तक कि यह एक स्वीकार्य नहीं हो जाता। इसलिए, डीटीऍम की स्वीकार्य गणना की लंबाई सामान्य रूप से एनटीऍम की सबसे छोटी स्वीकार्य गणना की लंबाई में घातीय है। यह डीटीऍम द्वारा एनटीऍम के अनुरूपण की एक सामान्य संपत्ति माना जाता है। पी = एनपी समस्या कंप्यूटर विज्ञान में सबसे प्रसिद्ध अज्ञात प्रश्न, इस समस्या के एक कथन से संबंधित है: जो यह है की बहुपद समय में एनटीऍम द्वारा हल की जाने वाली प्रत्येक समस्या, अनिवार्य रूप से बहुपद समय में डीटीऍम द्वारा हल करने योग्य है या नहीं है।
+दूसरे निर्माण में, निर्मित डीटीएम प्रभावी रूप से एनटीएम के कम्प्यूटेशन (अभिकलन) पहले ट्री की चौड़ाई की खोज करता हैं, तब लंबाई बढ़ाने के क्रम में एनटीएम की सभी संभावित संगणनाओं का चक्कर लगाता हैं जब तक कि यह एक स्वीकार्य नहीं हो जाता। इसलिए, डीटीएम की स्वीकार्य गणना की लंबाई सामान्य रूप से एनटीएम की सबसे छोटी स्वीकार्य गणना की लंबाई में घातीय है। यह डीटीएम द्वारा एनटीएम के अनुरूपण की एक सामान्य संपत्ति माना जाता है। पी = एनपी समस्या कंप्यूटर विज्ञान में सबसे प्रसिद्ध अज्ञात प्रश्न, इस समस्या के एक कथन से संबंधित है: जो यह है की बहुपद समय में एनटीएम द्वारा हल की जाने वाली प्रत्येक समस्या, अनिवार्य रूप से बहुपद समय में डीटीएम द्वारा हल करने योग्य है या नहीं है।
 == गैर-नियतात्मक परिबद्ध ==
-एक एनटीऍम में गैर-नियतात्मक परिबद्ध का गुण होता है। यदि कोई एनटीऍम हमेशा किसी दिए गए इनपुट टेप T पर रुकता है तो यह सीमित संख्या के चरणों में रुकता है, और इसलिए केवल संभावित विन्यासो की सीमित संख्या हो सकती है।
+एक एनटीएम में गैर-नियतात्मक परिबद्ध का गुण होता है। यदि कोई एनटीएम हमेशा किसी दिए गए इनपुट टेप T पर रुकता है तो यह सीमित संख्या के चरणों में रुकता है, और इसलिए केवल संभावित विन्यासो की सीमित संख्या हो सकती है।
 == क्वांटम कंप्यूटर्स के साथ तुलना ==
-[[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>{{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 85: / 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 98: / 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:Vigyan Ready]]
+[[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