वैकल्पिक ट्यूरिंग मशीन: Difference between revisions

Revision as of 22:58, 8 August 2023

कम्प्यूटेशनल जटिलता सिद्धांत में, वैकल्पिक ट्यूरिंग मशीन (ATM) गैर नियतात्मक ट्यूरिंग मशीन (NTM) के रूप में होती है, जिसमें अभिकलन एक्सेप्ट करने का एक नियम है, जो जटिलता वर्ग एनपी और को-एनपी की परिभाषा में उपयोग किए गए नियमों को सामान्य बनाता है। एटीएम की अवधारणा अशोक के. चंद्रा और लैरी स्टॉकमेयर के द्वारा प्रस्तुत की गई थी^[1] और स्वतंत्र रूप से डेक्सटर कोज़ेन द्वारा^[2] 1976 और 1981 में एक संयुक्त जर्नल पब्लिकेशन के साथ प्रस्तुत की गई है।^[3]

परिभाषाएँ

इनफॉर्मल विवरण

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

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

फॉर्मल परिभाषा

फॉर्मल रूप से, एक (एक-टेप) वैकल्पिक ट्यूरिंग मशीन 5- टपल के रूप में होता है $M=(Q,\Gamma ,\delta ,q_{0},g)$ जहाँ

$Q$ स्टेट का परिमित सेट है
$\Gamma$ परिमित टेप वर्णमाला है
$\delta :Q\times \Gamma \rightarrow {\mathcal {P}}(Q\times \Gamma \times \{L,R\})$ इसे ट्रांज़िशन फ़ंक्शन कहा जाता है जबकि L सिर को बाईं ओर और R सिर को दाईं ओर शिफ्ट करता है,
$q_{0}\in Q$ प्रारंभिक अवस्था है
$g:Q\rightarrow \{\wedge ,\vee ,accept,reject\}$ प्रत्येक स्टेट का प्रकार निर्दिष्ट करता है

यदि M, $g(q)=accept$ के साथ $q\in Q$ स्थिति में है, तो उसे कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है और यदि $g(q)=reject$ है तो कॉन्फ़िगरेशन को अएक्सेप्ट करने वाला कहा जाता है। जबकि $g(q)=\wedge$ के साथ एक कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है कि यदि एक चरण में रीचबल सभी कॉन्फ़िगरेशन एक्सेप्ट रूप में होते है, तो इसे एक्सेप्ट किया जाता है और यदि एक चरण में रीचबल कुछ कॉन्फ़िगरेशन अएक्सेप्ट किया जाता है, तो इसे अएक्सेप्ट किया जाता है। जबकि $g(q)=\vee$ के साथ एक कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है जब एक चरण में रीचबल कुछ कॉन्फ़िगरेशन के रूप में उपस्थित होते है, जिसे एक्सेप्ट या अएक्सेप्ट करना होता है जब एक चरण में रीचबल सभी कॉन्फ़िगरेशन अएक्सेप्ट कर रहे होते हैं, तब यह अंतिम स्थिति को छोड़कर मौलिक NTM में सभी स्टेट का प्रकार होता है। इस प्रकार कहा जाता है कि M एक इनपुट स्ट्रिंग डब्ल्यू को एक्सेप्ट करता है यदि M का प्रारंभिक विन्यास M की स्थिति $q_{0}$ ,है हेड टेप के बाएं छोर पर है और टेप में w एक्सेप्ट कर रहा है और यदि प्रारंभिक कॉन्फ़िगरेशन अएक्सेप्ट कर रहा है तो अएक्सेप्ट के रूप में होता है।

ध्यान दें कि किसी कॉन्फ़िगरेशन के लिए एक्सेप्ट करना और अएक्सेप्ट करना दोनों असंभव है, चूंकि, नॉन- टर्मिनेटीग अभिकलन की संभावना के कारण कुछ कॉन्फ़िगरेशन न तो एक्सेप्ट कर सकते हैं और न ही अएक्सेप्ट कर सकते हैं।

संसाधन सीमा

उपरोक्त परिभाषा का उपयोग करते हुए यह तय करते समय कि एटीएम का कॉन्फ़िगरेशन एक्सेप्ट या अएक्सेप्ट रूप में होता है और इस प्रकार वर्तमान कॉन्फ़िगरेशन से रीचबल सभी कॉन्फ़िगरेशन की जांच करना अधिकांशतः आवश्यक नहीं होता है। इस प्रकार विशेष रूप से एक अस्तित्वगत कॉन्फ़िगरेशन को एक्सेप्ट करने के रूप में लेबल किया जाता है यदि कोई सक्सेसर कॉन्फ़िगरेशन एक्सेप्ट करने योग्य पाया जाता है, और एक यूनिवर्सल कॉन्फ़िगरेशन को अएक्सेप्ट करने के रूप में लेबल किया जाता है यदि कोई सक्सेसर कॉन्फ़िगरेशन अएक्सेप्ट करता हुआ पाया जाता है।

एटीएम समय $t(n)$ रहते फॉर्मल लैंग्वेज तय कर लेता है, यदि, लंबाई के किसी भी इनपुट पर $n$ , तक कॉन्फ़िगरेशन की जांच करता है तब $t(n)$ प्रारंभिक कॉन्फ़िगरेशन को एक्सेप्ट या अएक्सेप्ट के रूप में लेबल करने के लिए पर्याप्त होता है। एक एटीएम क्षेत्र में एक लैंग्वेज $s(n)$ तय करता है, यदि उन कॉन्फ़िगरेशनों की जांच की जा रही है जो टेप सेल को इससे परे संशोधित नहीं करते हैं और इस प्रकार $s(n)$ बायीं ओर से सेल पर्याप्त है.

एक ऐसी लैंग्वेज जो कुछ स्थिरांक $c>0$ के लिए समय $c\cdot t(n)$ में कुछ एटीएम द्वारा तय की जाती है, उसे ${\mathsf {ATIME}}(t(n))$ , क्लास कहा जाता है और क्षेत्र $c\cdot s(n)$ में तय की गई लैंग्वेज को ${\mathsf {ASPACE}}(s(n))$ .कहा जाता है।

उदाहरण

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

ऐसी मशीन समय पर परिमाणित बूलियन सूत्र $n^{2}$ और स्थान $n$ . के रूप में तय करती है

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

जटिलता क्लासेस और डिटरर्मिनिस्टिक ट्यूरिंग मशीनों से तुलना

निम्नलिखित जटिलता क्लासेस एटीएम के लिए परिभाषित करने के लिए उपयोगी होती है

${\mathsf {AP}}=\bigcup _{k>0}{\mathsf {ATIME}}(n^{k})$ क्या लैंग्वेज बहुपद समय में डिसाइडेबल हैं?
${\mathsf {APSPACE}}=\bigcup _{k>0}{\mathsf {ASPACE}}(n^{k})$ बहुपद स्थान में डिसाइडेबल लैंग्वेज हैं
${\mathsf {AEXPTIME}}=\bigcup _{k>0}{\mathsf {ATIME}}(2^{n^{k}})$ क्या लैंग्वेज घातीय समय में डिसाइडेबल हैं

ये एक डिटरर्मिनिस्टिक ट्यूरिंग मशीन के अतिरिक्त एटीएम द्वारा उपयोग किए जाने वाले संसाधनों पर विचार करते हुए P, PSPACE और EXPTIME की परिलैंग्वेजेज के समान हैं। चंद्रा, कोज़ेन और स्टॉकमेयर^[3]प्रमेयों को सिद्ध किया हैं,

ALOGSPACE = P
AP = PSPACE
APSPACE = EXPTIME
AEXPTIME = EXPSPACE

${\mathsf {ASPACE}}(f(n))=\bigcup _{c>0}{\mathsf {DTIME}}(2^{cf(n)})={\mathsf {DTIME}}(2^{O(f(n))})$
${\mathsf {ATIME}}(g(n))\subseteq {\mathsf {DSPACE}}(g(n))$
${\mathsf {NSPACE}}(g(n))\subseteq \bigcup _{c>0}{\mathsf {ATIME}}(c\times g(n)^{2}),$

जहाँ $f(n)\geq \log(n)$ और $g(n)\geq \log(n)$ .

इन संबंधों का अधिक सामान्य रूप से समानांतर अभिकलन थीसिस द्वारा व्यक्त किया जाता है।

बॉण्डेड ऑल्टनेशन

परिभाषा

k विकल्पों के साथ एक वैकल्पिक ट्यूरिंग मशीन एक वैकल्पिक ट्यूरिंग मशीन है, जो अस्तित्वगत से यूनिवर्सल स्थिति में या इसके विपरीत k-1 बार से अधिक स्विच नहीं करती है। यह एक वैकल्पिक ट्यूरिंग मशीन है जिसके स्टेट k सेट में विभाजित होते हैं और इस प्रकार सम-संख्या वाले सेट में स्टेट यूनिवर्सल होते हैं और विषम संख्या वाले सेट में स्टेट अस्तित्वगत इसके विपरीत होते हैं। मशीन में सेट i और सेट j <'i में एक स्टेट के बीच कोई ट्रांजिशन नहीं होता है।

${\mathsf {ATIME}}(C,j)=\Sigma _{j}{\mathsf {TIME}}(C)$ समय के अनुसार डिसाइडेबल लैंग्वेजेज की क्लास है $f\in C$ एक मशीन जो अस्तित्वगत अवस्था में शुरू होती है और अधिक से अधिक बदलती रहती है और इस प्रकार $j-1$ बार. इसे कहा जाता है और $j$ वें स्तर का ${\mathsf {TIME}}(C)$ हायरार्की है।

${\mathsf {coATIME}}(C,j)=\Pi _{j}{\mathsf {TIME}}(C)$ उसी तरह से परिभाषित किया जाता है, लेकिन शुरुआत एक यूनिवर्सल स्थिति से होती है और इसमें लैंग्वेजेज के पूरक ${\mathsf {ATIME}}(f,j)$ .के रूप में होती है

${\mathsf {ASPACE}}(C,j)=\Sigma _{j}{\mathsf {SPACE}}(C)$ क्षेत्र बॉण्डेड अभिकलन के लिए इसी प्रकार परिभाषित किया जाता है।

उदाहरण

सर्किट न्यूनीकरण समस्या पर विचार करते है, एक सर्किट A को बूलियन फ़ंक्शन f और एक संख्या n की की गणना करते हुए यह निर्धारित करता है कि क्या अधिकतम n गेट्स वाला एक सर्किट होता है, जो समान फ़ंक्शन f की गणना करता है। एक प्रत्यावर्ती ट्यूरिंग मशीन, एक ऑल्टनेशन के साथ एक अस्तित्वगत स्थिति में शुरू करके इस समस्या को बहुपद समय में हल कर सकती है और इस प्रकार अधिकतम n द्वारों के साथ एक सर्किट B का अनुमान लगाकर, फिर एक यूनिवर्सल स्थिति पर स्विच करके एक इनपुट का अनुमान लगाकर यह जांचना कि उस इनपुट पर B का आउटपुट उस इनपुट पर A के आउटपुट से मेल खाता है।

कोलेप्सींग कक्षाएं

ऐसा कहा जाता है कि हायरार्की स्तर तक कोलेप्स हो जाता है और इस प्रकार $j$ यदि प्रत्येक लैंग्वेज स्तर में है और $k\geq j$ हायरार्की का स्तर अपने स्तर पर $j$ .के रूप में है

इमरमैन-स्ज़ेलेपेसेनी प्रमेय के परिणाम के रूप में, लॉगरिदमिक क्षेत्र हायरार्की अपने पहले स्तर तक कोलेप्स हो जाता है।^[4] एक परिणाम के रूप में ${\mathsf {SPACE}}(f)$ जब हायरार्की अपने पहले स्तर तक कोलेप्स हो जाता है तो $f=\Omega (\log )$ स्थान कंस्ट्रक्टिबल के रूप में है

विशेष स्थिति

बहुपद समय में k विकल्पों के साथ एक वैकल्पिक ट्यूरिंग मशीन, जो क्रमशः अस्तित्वगत यूनिवर्सल स्थिति में शुरू होकर क्लास $\Sigma _{k}^{p}$ (क्रमश, $\Pi _{k}^{p}$ ) में सभी समस्याओं का समाधान कर सकती है।^[5]

इन क्लास को कभी-कभी क्रमशः $\Sigma _{k}{\rm {P}}$ और $\Pi _{k}{\rm {P}}$ द्वारा निरूपित किया जाता है। विवरण के लिए बहुपद हायरार्की लेख में देख सकते है।

समय हायरार्की का एक और विशेष स्थिति,लॉगरिदम हायरार्की के रूप में है।

संदर्भ

↑ Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "अदल-बदल". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 98–108. doi:10.1109/SFCS.1976.4.
↑ Kozen, D. (1976). "ट्यूरिंग मशीनों में समानता पर". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 89–97. doi:10.1109/SFCS.1976.20. hdl:1813/7056.
↑ ^3.0 ^3.1 Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "अदल-बदल" (PDF). Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. S2CID 238863413. Archived from the original (PDF) on April 12, 2016.
↑ Immerman, Neil (1988). "गैर-नियतात्मक स्थान पूरकता के तहत बंद है" (PDF). SIAM Journal on Computing. 17 (5): 935–938. CiteSeerX 10.1.1.54.5941. doi:10.1137/0217058.
↑ Kozen, Dexter (2006). संगणना का सिद्धांत. Springer-Verlag. p. 58. ISBN 9781846282973.

अग्रिम पठन

Michael Sipser (2006). Introduction to the Theory of Computation (2nd ed.). PWS Publishing. ISBN 978-0-534-95097-2. Section 10.3: Alternation, pp. 380–386.
Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 978-0-201-53082-7. Section 16.2: Alternation, pp. 399–401.
Bakhadyr Khoussainov; Anil Nerode (2012). Automata Theory and its Applications. Springer Science & Business Media. ISBN 978-1-4612-0171-7.

[chasto-1] Chandra, Ashok K.; Stockmeyer, Larry J. (1976). "अदल-बदल". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 98–108. doi:10.1109/SFCS.1976.4.

[kozen-2] Kozen, D. (1976). "ट्यूरिंग मशीनों में समानता पर". Proc. 17th IEEE Symp. on Foundations of Computer Science. Houston, Texas. pp. 89–97. doi:10.1109/SFCS.1976.20. hdl:1813/7056.

[alternation-3] 3.0 ^3.1 Chandra, Ashok K.; Kozen, Dexter C.; Stockmeyer, Larry J. (1981). "अदल-बदल" (PDF). Journal of the ACM. 28 (1): 114–133. doi:10.1145/322234.322243. S2CID 238863413. Archived from the original (PDF) on April 12, 2016.

[4] Immerman, Neil (1988). "गैर-नियतात्मक स्थान पूरकता के तहत बंद है" (PDF). SIAM Journal on Computing. 17 (5): 935–938. CiteSeerX 10.1.1.54.5941. doi:10.1137/0217058.

[5] Kozen, Dexter (2006). संगणना का सिद्धांत. Springer-Verlag. p. 58. ISBN 9781846282973.

[1]

[2]

[3]

[4]

[5]

@@ Line 2: / Line 2: @@
 {{turing}}
 {{more footnotes|date=May 2011}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में, '''वैकल्पिक ट्यूरिंग मशीन''' ('''ATM''') [[गैर-नियतात्मक ट्यूरिंग मशीन|गैर-डिटर्मनिस्टिक ट्यूरिंग मशीन]] ('''NTM''') के रूप में होती है, जिसमें कम्प्यूटेशन एक्सेप्ट करने का एक नियम है, जो [[जटिलता वर्ग|कॉम्प्लेक्सिटी]] [[क्लास]] [[एनपी (जटिलता)|एनपी]] और [[सह-एनपी|को-एनपी]] की परिभाषा में उपयोग किए गए नियमों को सामान्य बनाता है। एटीएम की अवधारणा अशोक के. चंद्रा और [[लैरी स्टॉकमेयर]] के द्वारा प्रस्तुत की गई थी<ref name=chasto>{{Cite conference|doi=10.1109/SFCS.1976.4|last1=Chandra|first1=Ashok K.|last2=Stockmeyer|first2=Larry J.|title=अदल-बदल|book-title=Proc. 17th IEEE Symp. on Foundations of Computer Science|location=Houston, Texas|year=1976|pages=98–108}}</ref> और स्वतंत्र रूप से [[डेक्सटर कोज़ेन]] द्वारा<ref name=kozen>{{cite conference|doi=10.1109/SFCS.1976.20|last=Kozen|first=D.|title=ट्यूरिंग मशीनों में समानता पर|book-title=Proc. 17th IEEE Symp. on Foundations of Computer Science|location=Houston, Texas|year=1976|pages=89–97|hdl=1813/7056|hdl-access=free}}</ref> 1976 और 1981 में एक संयुक्त जर्नल पब्लिकेशन के साथ प्रस्तुत की गई है।<ref name=alternation>{{Cite journal|doi=10.1145/322234.322243 |last1=Chandra |first1=Ashok K. |last2=Kozen |first2=Dexter C. |last3=Stockmeyer |first3=Larry J. |title=अदल-बदल|url=http://users.cis.fiu.edu/~giri/teach/5420/f01/papers/p114-chandra.pdf |journal=[[Journal of the ACM]] |volume=28 |issue=1 |pages=114–133 |year=1981 |s2cid=238863413 |url-status=dead |archive-url=https://web.archive.org/web/20160412232110/http://users.cis.fiu.edu/~giri/teach/5420/f01/papers/p114-chandra.pdf |archive-date=April 12, 2016 }}</ref>
+[[कम्प्यूटेशनल जटिलता  सिद्धांत]] में, '''वैकल्पिक ट्यूरिंग मशीन''' ('''ATM''') [[गैर-नियतात्मक ट्यूरिंग मशीन|गैर नियतात्मक  ट्यूरिंग मशीन]] ('''NTM''') के रूप में होती है, जिसमें अभिकलन एक्सेप्ट करने का एक नियम है, जो [[जटिलता वर्ग]] [[एनपी (जटिलता)|एनपी]] और [[सह-एनपी|को-एनपी]] की परिभाषा में उपयोग किए गए नियमों को सामान्य बनाता है। एटीएम की अवधारणा अशोक के. चंद्रा और [[लैरी स्टॉकमेयर]] के द्वारा प्रस्तुत की गई थी<ref name=chasto>{{Cite conference|doi=10.1109/SFCS.1976.4|last1=Chandra|first1=Ashok K.|last2=Stockmeyer|first2=Larry J.|title=अदल-बदल|book-title=Proc. 17th IEEE Symp. on Foundations of Computer Science|location=Houston, Texas|year=1976|pages=98–108}}</ref> और स्वतंत्र रूप से [[डेक्सटर कोज़ेन]] द्वारा<ref name=kozen>{{cite conference|doi=10.1109/SFCS.1976.20|last=Kozen|first=D.|title=ट्यूरिंग मशीनों में समानता पर|book-title=Proc. 17th IEEE Symp. on Foundations of Computer Science|location=Houston, Texas|year=1976|pages=89–97|hdl=1813/7056|hdl-access=free}}</ref> 1976 और 1981 में एक संयुक्त जर्नल पब्लिकेशन के साथ प्रस्तुत की गई है।<ref name=alternation>{{Cite journal|doi=10.1145/322234.322243 |last1=Chandra |first1=Ashok K. |last2=Kozen |first2=Dexter C. |last3=Stockmeyer |first3=Larry J. |title=अदल-बदल|url=http://users.cis.fiu.edu/~giri/teach/5420/f01/papers/p114-chandra.pdf |journal=[[Journal of the ACM]] |volume=28 |issue=1 |pages=114–133 |year=1981 |s2cid=238863413 |url-status=dead |archive-url=https://web.archive.org/web/20160412232110/http://users.cis.fiu.edu/~giri/teach/5420/f01/papers/p114-chandra.pdf |archive-date=April 12, 2016 }}</ref>
 == परिभाषाएँ ==
 === इनफॉर्मल विवरण ===
-NP की परिभाषा कम्प्यूटेशन के एक्सिस्टेंटीएल मोड का उपयोग करती है, यदि कोई विकल्प एक्सेप्टिंग स्थिति की ओर ले जाता है, तो पूरी कम्प्यूटेशन एक्सेप्ट हो जाती है और इस प्रकार सह-NP की परिभाषा कम्प्यूटेशन के यूनिवर्सल विधि का उपयोग करती है इस प्रकार केवल जब सभी विकल्प एक एक्सेप्टिंग स्थिति की ओर ले जाते हैं तो पूरी कम्प्यूटेशन एक्सेप्ट होती है। एक वैकल्पिक ट्यूरिंग मशीन अधिक सटीक होने के लिए ऐसी मशीन के लिए स्वीकृति की परिभाषा इन मोडों के बीच वैकल्पिक रूप में होती है।
+NP की परिभाषा अभिकलन के अस्तित्वगत मोड का उपयोग करती है, यदि कोई विकल्प एक्सेप्टिंग स्थिति की ओर ले जाता है, तो पूरी  अभिकलन एक्सेप्ट हो जाती है और इस प्रकार को-NP की परिभाषा  अभिकलन के यूनिवर्सल विधि का उपयोग करती है और केवल जब सभी विकल्प एक एक्सेप्टिंग स्थिति की ओर ले जाते हैं तो पूरी अभिकलन एक्सेप्ट हो जाती है। वैकल्पिक ट्यूरिंग मशीन इन मोडों के बीच वैकल्पिक रूप में होती है और इस प्रकार अधिक परिशुद्ध होने के लिए ऐसी मशीन के लिए स्वीकृति की परिभाषा देती है।
-'वैकल्पिक ट्यूरिंग मशीन' एक गैर-डिटरर्मिनिस्टिक ट्यूरिंग मशीन के रूप में होती है, जिसके स्टेट एक्सिस्टेंटीएल स्टेट 'और 'यूनिवर्सल स्टेट को दो सेटों में विभाजित किया जाता है और यह इस प्रकार एक एक्सिस्टेंटीएल अवस्था एक्सेप्ट करने वाली होती है यदि कोई परिवर्तन एक्सेप्ट करने वाली अवस्था की ओर ले जाता है और यूनिवर्सल स्टेट एक्सेप्ट करता है, यदि प्रत्येक ट्रांजिशन एक एक्सेप्टिंग स्टेट की ओर ले जाता है। इस प्रकार बिना किसी परिवर्तन वाला एक यूनिवर्सल स्टेट बिना किसी शर्त के एक्सेप्ट करता है और यह बिना किसी ट्रांजिशन वाला एक एक्सिस्टेंटीएल स्टेट बिना किसी शर्त के एक्सेप्ट करता है। यदि प्रारंभिक स्थिति एक्सेप्ट करती है तो मशीन पूरी तरह से एक्सेप्ट होती है।
+'वैकल्पिक ट्यूरिंग मशीन' एक गैर नियतात्मक  ट्यूरिंग मशीन के रूप में होती है, जिसके स्टेट अस्तित्वगत स्टेट 'और 'यूनिवर्सल स्टेट को दो सेटों में विभाजित किया जाता है और इस प्रकार यदि कोई परिवर्तन एक्सेप्ट करने वाली अवस्था की ओर ले जाता है और यूनिवर्सल स्टेट एक्सेप्ट करता है, इस प्रकार यदि प्रत्येक ट्रांजिशन एक एक्सेप्टिंग स्टेट की ओर ले जाता है। तो बिना किसी परिवर्तन वाला एक यूनिवर्सल स्टेट बिना किसी शर्त के एक्सेप्ट हो  जाता है और यह बिना किसी ट्रांजिशन वाला एक अस्तित्वगत स्टेट बिना किसी शर्त के एक्सेप्ट करता है। यदि प्रारंभिक स्थिति अस्वीकार  करता है, यदि प्रारंभिक स्थिति एक्सेप्ट कर रही है तो मशीन पूरी तरह से एक्सेप्ट करती है।
 === फॉर्मल परिभाषा ===
@@ Line 22: / Line 22: @@
 यदि M, <math>g(q)=accept</math> के साथ <math>q\in Q</math> स्थिति में है, तो उसे कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है और यदि <math>g(q)=reject</math> है तो कॉन्फ़िगरेशन को अएक्सेप्ट करने वाला कहा जाता है। जबकि <math>g(q)=\wedge</math> के साथ एक कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है कि यदि एक चरण में रीचबल सभी कॉन्फ़िगरेशन एक्सेप्ट रूप में होते है, तो इसे एक्सेप्ट किया जाता है और यदि एक चरण में रीचबल कुछ कॉन्फ़िगरेशन अएक्सेप्ट किया जाता है, तो इसे अएक्सेप्ट किया जाता है। जबकि <math>g(q)=\vee</math> के साथ एक कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है जब एक चरण में रीचबल कुछ कॉन्फ़िगरेशन के रूप में उपस्थित होते है, जिसे एक्सेप्ट या अएक्सेप्ट करना होता है जब एक चरण में रीचबल सभी कॉन्फ़िगरेशन अएक्सेप्ट कर रहे होते हैं, तब यह अंतिम स्थिति को छोड़कर मौलिक NTM में सभी स्टेट का प्रकार होता है। इस प्रकार कहा जाता है कि M एक इनपुट स्ट्रिंग डब्ल्यू को एक्सेप्ट करता है यदि M का प्रारंभिक विन्यास M की स्थिति <math>q_0</math>,है हेड टेप के बाएं छोर पर है और टेप में w एक्सेप्ट कर रहा है और यदि प्रारंभिक कॉन्फ़िगरेशन अएक्सेप्ट कर रहा है तो अएक्सेप्ट के रूप में होता है।
-ध्यान दें कि किसी कॉन्फ़िगरेशन के लिए एक्सेप्ट करना और अएक्सेप्ट करना दोनों असंभव है, चूंकि, नॉन- टर्मिनेटीग कम्प्यूटेशन की संभावना के कारण कुछ कॉन्फ़िगरेशन न तो एक्सेप्ट कर सकते हैं और न ही अएक्सेप्ट कर सकते हैं।
+ध्यान दें कि किसी कॉन्फ़िगरेशन के लिए एक्सेप्ट करना और अएक्सेप्ट करना दोनों असंभव है, चूंकि, नॉन- टर्मिनेटीग  अभिकलन की संभावना के कारण कुछ कॉन्फ़िगरेशन न तो एक्सेप्ट कर सकते हैं और न ही अएक्सेप्ट कर सकते हैं।
 === संसाधन सीमा ===
-उपरोक्त परिभाषा का उपयोग करते हुए यह तय करते समय कि एटीएम का कॉन्फ़िगरेशन एक्सेप्ट या अएक्सेप्ट रूप में होता है और इस प्रकार वर्तमान कॉन्फ़िगरेशन से रीचबल सभी कॉन्फ़िगरेशन की जांच करना अधिकांशतः आवश्यक नहीं होता है। इस प्रकार विशेष रूप से एक एक्सिस्टेंटीएल कॉन्फ़िगरेशन को एक्सेप्ट करने के रूप में लेबल किया जाता है यदि कोई सक्सेसर कॉन्फ़िगरेशन एक्सेप्ट करने योग्य पाया जाता है, और एक यूनिवर्सल कॉन्फ़िगरेशन को अएक्सेप्ट करने के रूप में लेबल किया जाता है यदि कोई सक्सेसर कॉन्फ़िगरेशन अएक्सेप्ट करता हुआ पाया जाता है।
+उपरोक्त परिभाषा का उपयोग करते हुए यह तय करते समय कि एटीएम का कॉन्फ़िगरेशन एक्सेप्ट या अएक्सेप्ट रूप में होता है और इस प्रकार वर्तमान कॉन्फ़िगरेशन से रीचबल सभी कॉन्फ़िगरेशन की जांच करना अधिकांशतः आवश्यक नहीं होता है। इस प्रकार विशेष रूप से एक अस्तित्वगत कॉन्फ़िगरेशन को एक्सेप्ट करने के रूप में लेबल किया जाता है यदि कोई सक्सेसर कॉन्फ़िगरेशन एक्सेप्ट करने योग्य पाया जाता है, और एक यूनिवर्सल कॉन्फ़िगरेशन को अएक्सेप्ट करने के रूप में लेबल किया जाता है यदि कोई सक्सेसर कॉन्फ़िगरेशन अएक्सेप्ट करता हुआ पाया जाता है।
 एटीएम समय <math>t(n)</math> रहते [[औपचारिक भाषा|फॉर्मल]] लैंग्वेज तय कर लेता है, यदि, लंबाई के किसी भी इनपुट पर {{mvar|n}}, तक कॉन्फ़िगरेशन की जांच करता है तब <math>t(n)</math> प्रारंभिक कॉन्फ़िगरेशन को एक्सेप्ट या अएक्सेप्ट के रूप में लेबल करने के लिए पर्याप्त होता है। एक एटीएम क्षेत्र में एक लैंग्वेज <math>s(n)</math> तय करता है, यदि उन कॉन्फ़िगरेशनों की जांच की जा रही है जो टेप सेल को इससे परे संशोधित नहीं करते हैं और इस प्रकार <math>s(n)</math> बायीं ओर से सेल पर्याप्त है.
@@ Line 34: / Line 34: @@
 == उदाहरण ==
-वैकल्पिक मशीनों के समाधान में शायद सर्वाधिक स्वाभाविक समस्या, क्वांटिकृत बूलियन सूत्र समस्या है, जो [[बूलियन संतुष्टि समस्या]] का एक सामान्यीकरण है जिसमें प्रत्येक चर को एक्सिस्टेंटीएल या यूनिवर्सल मात्रात्मक द्वारा बाध्य किया जा सकता है। इस प्रकार वैकल्पिक मशीन ब्रांचेस एक्सिस्टेंटीएल रूप से परिमाणित चर के सभी संभावित मूल्यों को आज़माने के लिए होते है और यूनिवर्सल रूप से परिमाणित चर के सभी संभावित मूल्यों को बाएँ से दाएँ क्रम में आज़माने के लिए अपनाये जाते है, जिसमें वे बंधे होते है। सभी परिमाणित चरों के लिए एक मान तय करने के बाद यदि परिणामी बूलियन सूत्र ट्रुथ का मूल्यांकन करता है तो मशीन एक्सेप्ट कर लेती है और यदि गलत का मूल्यांकन करता है तो अएक्सेप्ट कर देती है। इस प्रकार एक्सिस्टेंटीएल रूप से परिमाणित चर पर मशीन एक्सेप्ट कर रही है कि क्या चर के लिए एक मान प्रतिस्थापित किया जा सकता है जो शेष समस्या को संतोषजनक बनाता है, और एक यूनिवर्सल रूप से परिमाणित चर पर मशीन एक्सेप्ट कर रही है कि क्या कोई मान प्रतिस्थापित किया जा सकता है और शेष समस्या का समाधान किया जा सकता है।
+वैकल्पिक मशीनों के समाधान में शायद सर्वाधिक स्वाभाविक समस्या, क्वांटिकृत बूलियन सूत्र समस्या है, जो [[बूलियन संतुष्टि समस्या]] का एक सामान्यीकरण है जिसमें प्रत्येक चर को अस्तित्वगत या यूनिवर्सल मात्रात्मक द्वारा बाध्य किया जा सकता है। इस प्रकार वैकल्पिक मशीन ब्रांचेस अस्तित्वगत रूप से परिमाणित चर के सभी संभावित मूल्यों को आज़माने के लिए होते है और यूनिवर्सल रूप से परिमाणित चर के सभी संभावित मूल्यों को बाएँ से दाएँ क्रम में आज़माने के लिए अपनाये जाते है, जिसमें वे बंधे होते है। सभी परिमाणित चरों के लिए एक मान तय करने के बाद यदि परिणामी बूलियन सूत्र ट्रुथ का मूल्यांकन करता है तो मशीन एक्सेप्ट कर लेती है और यदि गलत का मूल्यांकन करता है तो अएक्सेप्ट कर देती है। इस प्रकार अस्तित्वगत रूप से परिमाणित चर पर मशीन एक्सेप्ट कर रही है कि क्या चर के लिए एक मान प्रतिस्थापित किया जा सकता है जो शेष समस्या को संतोषजनक बनाता है, और एक यूनिवर्सल रूप से परिमाणित चर पर मशीन एक्सेप्ट कर रही है कि क्या कोई मान प्रतिस्थापित किया जा सकता है और शेष समस्या का समाधान किया जा सकता है।
 ऐसी मशीन समय पर परिमाणित बूलियन सूत्र <math>n^2</math> और स्थान <math>n</math>. के रूप में तय करती है
-बूलियन संतुष्टि समस्या को विशेष स्थितियों के रूप में देखा जा सकता है जहां सभी चर एक्सिस्टेंटीएल रूप से परिमाणित होते हैं, जो सामान्य गैर-नियतिवाद को अनुमति देता है, जो इसे कुशलतापूर्वक हल करने के लिए केवल एक्सिस्टेंटीएल ब्रांच का उपयोग करता है।
+बूलियन संतुष्टि समस्या को विशेष स्थितियों के रूप में देखा जा सकता है जहां सभी चर अस्तित्वगत रूप से परिमाणित होते हैं, जो सामान्य नॉन -नियतिवाद को अनुमति देता है, जो इसे कुशलतापूर्वक हल करने के लिए केवल अस्तित्वगत ब्रांच का उपयोग करता है।
-==  [[जटिलता वर्ग|कॉम्प्लेक्सिटी क्लासेस]] और डिटरर्मिनिस्टिक ट्यूरिंग मशीनों से तुलना ==
+==  [[जटिलता वर्ग|जटिलता  क्लासेस]] और डिटरर्मिनिस्टिक ट्यूरिंग मशीनों से तुलना ==
-निम्नलिखित कॉम्प्लेक्सिटी क्लासेस एटीएम के लिए परिभाषित करने के लिए उपयोगी होती है
+निम्नलिखित जटिलता  क्लासेस एटीएम के लिए परिभाषित करने के लिए उपयोगी होती है
 * <math>\mathsf{AP}=\bigcup_{k>0}\mathsf{ATIME}(n^k)</math> क्या लैंग्वेज बहुपद समय में डिसाइडेबल हैं?
 * <math>\mathsf{APSPACE}=\bigcup_{k>0}\mathsf{ASPACE}(n^k)</math> बहुपद स्थान में डिसाइडेबल लैंग्वेज हैं
@@ Line 59: / Line 59: @@
 जहाँ <math>f(n)\ge\log(n)</math> और <math>g(n)\ge\log(n)</math>.
-इन संबंधों का अधिक सामान्य रूप से [[समानांतर गणना थीसिस|समानांतर कम्प्यूटेशन थीसिस]] द्वारा व्यक्त किया जाता है।
+इन संबंधों का अधिक सामान्य रूप से [[समानांतर गणना थीसिस|समानांतर  अभिकलन थीसिस]] द्वारा व्यक्त किया जाता है।
 == बॉण्डेड ऑल्टनेशन ==
@@ Line 65: / Line 65: @@
 ===परिभाषा===
 {{Unreferenced section|date=October 2013}}
-''k'' विकल्पों के साथ एक वैकल्पिक ट्यूरिंग मशीन एक वैकल्पिक ट्यूरिंग मशीन है, जो एक्सिस्टेंटीएल से यूनिवर्सल स्थिति में या इसके विपरीत ''k''-1 बार से अधिक स्विच नहीं करती है। यह एक वैकल्पिक ट्यूरिंग मशीन है जिसके स्टेट ''k'' सेट में विभाजित होते हैं और इस प्रकार सम-संख्या वाले सेट में स्टेट यूनिवर्सल होते हैं और विषम संख्या वाले सेट में स्टेट एक्सिस्टेंटीएल इसके विपरीत होते हैं। मशीन में सेट ''i'' और सेट ''j'' <'i'' में एक स्टेट के बीच कोई ट्रांजिशन नहीं होता है।''
+''k'' विकल्पों के साथ एक वैकल्पिक ट्यूरिंग मशीन एक वैकल्पिक ट्यूरिंग मशीन है, जो अस्तित्वगत से यूनिवर्सल स्थिति में या इसके विपरीत ''k''-1 बार से अधिक स्विच नहीं करती है। यह एक वैकल्पिक ट्यूरिंग मशीन है जिसके स्टेट ''k'' सेट में विभाजित होते हैं और इस प्रकार सम-संख्या वाले सेट में स्टेट यूनिवर्सल होते हैं और विषम संख्या वाले सेट में स्टेट अस्तित्वगत इसके विपरीत होते हैं। मशीन में सेट ''i'' और सेट ''j'' <'i'' में एक स्टेट के बीच कोई ट्रांजिशन नहीं होता है।''
-<math>\mathsf{ATIME}(C,j)=\Sigma_j \mathsf{TIME}(C)</math> समय के अनुसार डिसाइडेबल लैंग्वेजेज की क्लास है <math>f\in C</math> एक मशीन जो एक्सिस्टेंटीएल अवस्था में शुरू होती है और अधिक से अधिक बदलती रहती है और इस प्रकार <math>j-1</math> बार. इसे कहा जाता है और {{mvar|j}}वें स्तर का <math>\mathsf{TIME}(C)</math> हायरार्की ''है।''
+<math>\mathsf{ATIME}(C,j)=\Sigma_j \mathsf{TIME}(C)</math> समय के अनुसार डिसाइडेबल लैंग्वेजेज की क्लास है <math>f\in C</math> एक मशीन जो अस्तित्वगत अवस्था में शुरू होती है और अधिक से अधिक बदलती रहती है और इस प्रकार <math>j-1</math> बार. इसे कहा जाता है और {{mvar|j}}वें स्तर का <math>\mathsf{TIME}(C)</math> हायरार्की ''है।''
 <math>\mathsf{coATIME}(C,j)=\Pi_j \mathsf{TIME}(C)</math> उसी तरह से परिभाषित किया जाता है, लेकिन शुरुआत एक यूनिवर्सल स्थिति से होती है और इसमें लैंग्वेजेज के पूरक <math>\mathsf{ATIME}(f,j)</math>.के रूप में होती है
-<math>\mathsf{ASPACE}(C,j)=\Sigma_j \mathsf{SPACE}(C)</math> क्षेत्र बॉण्डेड कम्प्यूटेशन के लिए इसी प्रकार परिभाषित किया जाता है।
+<math>\mathsf{ASPACE}(C,j)=\Sigma_j \mathsf{SPACE}(C)</math> क्षेत्र बॉण्डेड  अभिकलन के लिए इसी प्रकार परिभाषित किया जाता है।
 === उदाहरण ===
-[[सर्किट न्यूनीकरण समस्या]] पर विचार करते है, एक सर्किट A को [[बूलियन फ़ंक्शन]] f और एक संख्या n की की गणना करते हुए यह निर्धारित करता है कि क्या अधिकतम n गेट्स वाला एक सर्किट होता है, जो समान फ़ंक्शन f की गणना करता है। एक प्रत्यावर्ती ट्यूरिंग मशीन, एक ऑल्टनेशन के साथ एक एक्सिस्टेंटीएल स्थिति में शुरू करके इस समस्या को बहुपद समय में हल कर सकती है और इस प्रकार अधिकतम n द्वारों के साथ एक सर्किट B का अनुमान लगाकर, फिर एक यूनिवर्सल स्थिति पर स्विच करके एक इनपुट का अनुमान लगाकर यह जांचना कि उस इनपुट पर B का आउटपुट उस इनपुट पर A के आउटपुट से मेल खाता है।
+[[सर्किट न्यूनीकरण समस्या]] पर विचार करते है, एक सर्किट A को [[बूलियन फ़ंक्शन]] f और एक संख्या n की की गणना करते हुए यह निर्धारित करता है कि क्या अधिकतम n गेट्स वाला एक सर्किट होता है, जो समान फ़ंक्शन f की गणना करता है। एक प्रत्यावर्ती ट्यूरिंग मशीन, एक ऑल्टनेशन के साथ एक अस्तित्वगत स्थिति में शुरू करके इस समस्या को बहुपद समय में हल कर सकती है और इस प्रकार अधिकतम n द्वारों के साथ एक सर्किट B का अनुमान लगाकर, फिर एक यूनिवर्सल स्थिति पर स्विच करके एक इनपुट का अनुमान लगाकर यह जांचना कि उस इनपुट पर B का आउटपुट उस इनपुट पर A के आउटपुट से मेल खाता है।
 === कोलेप्सींग कक्षाएं ===
@@ Line 82: / Line 82: @@
 ===विशेष स्थिति===
-बहुपद समय में k विकल्पों के साथ एक वैकल्पिक ट्यूरिंग मशीन, जो क्रमशः एक्सिस्टेंटीएल यूनिवर्सल स्थिति में शुरू होकर क्लास <math>\Sigma_k^p</math> (क्रमश, <math>\Pi_k^p</math>) में सभी समस्याओं का समाधान कर सकती है।<ref>{{cite book|last=Kozen|first=Dexter|author-link=Dexter Kozen|title=संगणना का सिद्धांत|url=https://archive.org/details/theorycomputatio00koze|url-access=limited|publisher=[[Springer-Verlag]]|year=2006|page=[https://archive.org/details/theorycomputatio00koze/page/n67 58]|isbn=9781846282973}}</ref>
+बहुपद समय में k विकल्पों के साथ एक वैकल्पिक ट्यूरिंग मशीन, जो क्रमशः अस्तित्वगत यूनिवर्सल स्थिति में शुरू होकर क्लास <math>\Sigma_k^p</math> (क्रमश, <math>\Pi_k^p</math>) में सभी समस्याओं का समाधान कर सकती है।<ref>{{cite book|last=Kozen|first=Dexter|author-link=Dexter Kozen|title=संगणना का सिद्धांत|url=https://archive.org/details/theorycomputatio00koze|url-access=limited|publisher=[[Springer-Verlag]]|year=2006|page=[https://archive.org/details/theorycomputatio00koze/page/n67 58]|isbn=9781846282973}}</ref>
 इन क्लास को कभी-कभी क्रमशः <math>\Sigma_k\rm{P}</math> और <math>\Pi_k\rm{P}</math> द्वारा निरूपित किया जाता है। विवरण के लिए [[बहुपद पदानुक्रम|बहुपद]] हायरार्की लेख में देख सकते है।

Anonymous

Search

वैकल्पिक ट्यूरिंग मशीन: Difference between revisions

Namespaces

More

Page actions

Revision as of 22:58, 8 August 2023

Contents

परिभाषाएँ

इनफॉर्मल विवरण

फॉर्मल परिभाषा

संसाधन सीमा

उदाहरण

जटिलता क्लासेस और डिटरर्मिनिस्टिक ट्यूरिंग मशीनों से तुलना

बॉण्डेड ऑल्टनेशन

परिभाषा

उदाहरण

कोलेप्सींग कक्षाएं

विशेष स्थिति

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

वैकल्पिक ट्यूरिंग मशीन: Difference between revisions

Revision as of 22:58, 8 August 2023

परिभाषाएँ

इनफॉर्मल विवरण

फॉर्मल परिभाषा

संसाधन सीमा

उदाहरण

जटिलता क्लासेस और डिटरर्मिनिस्टिक ट्यूरिंग मशीनों से तुलना

बॉण्डेड ऑल्टनेशन

परिभाषा

उदाहरण

कोलेप्सींग कक्षाएं

विशेष स्थिति

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories