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

Latest revision as of 09:41, 23 August 2023

कम्प्यूटेशनल कम्प्लेक्सिटी सिद्धांत में, वैकल्पिक ट्यूरिंग मशीन (एटीएम) गैर नियतात्मक ट्यूरिंग मशीन (एनटीएम) के रूप में होती है, जिसमें कम्प्यूटेशन एक्सेप्ट करने का एक नियम है, जो कम्प्लेक्सिटी क्लासेस एनपी और को-एनपी की परिभाषा में उपयोग किए गए नियमों को सामान्य बनाता है। एटीएम की अवधारणा अशोक के. चंद्रा और लैरी स्टॉकमेयर के द्वारा प्रस्तुत की गई थी^[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$ के साथ एक कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है जब एक चरण में रीचबल कुछ कॉन्फ़िगरेशन के रूप में उपस्थित होते है, जो एक्सेप्ट या रिजेक्ट कर रहा होता है जब एक चरण में रीचबल सभी कॉन्फ़िगरेशन रिजेक्ट कर रहे होते हैं, तब यह अंतिम स्टेट को छोड़कर मौलिक एनटीएम में सभी स्टेट का प्रकार होता है। इस प्रकार कहा जाता है कि 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 1: / Line 1: @@
 {{Short description|Abstract computation model}}
 {{turing}}
-{{more footnotes|date=May 2011}}
+[[कम्प्यूटेशनल जटिलता  सिद्धांत|कम्प्यूटेशनल कम्प्लेक्सिटी सिद्धांत]] में, '''वैकल्पिक ट्यूरिंग मशीन''' ('''एटीएम''') [[गैर-नियतात्मक ट्यूरिंग मशीन|गैर नियतात्मक ट्यूरिंग मशीन]] ('''एनटीएम''') के रूप में होती है, जिसमें कम्प्यूटेशन एक्सेप्ट करने का एक नियम है, जो [[जटिलता वर्ग|कम्प्लेक्सिटी क्लासेस]] [[एनपी (जटिलता)|एनपी]] और [[सह-एनपी|को-एनपी]] की परिभाषा में उपयोग किए गए नियमों को सामान्य बनाता है। एटीएम की अवधारणा अशोक के. चंद्रा और [[लैरी स्टॉकमेयर]] के द्वारा प्रस्तुत की गई थी<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 की परिभाषा कम्प्यूटेशन के यूनिवर्सल विधि का उपयोग करती है और केवल जब सभी विकल्प एक एक्सेप्टिंग स्टेट की ओर ले जाते हैं तो पूरी कम्प्यूटेशन एक्सेप्ट हो जाती है। वैकल्पिक ट्यूरिंग मशीन इन मोडों के बीच वैकल्पिक रूप में होती है और इस प्रकार अधिक परिशुद्ध होने के लिए ऐसी मशीन के लिए स्वीकृति की परिभाषा देती है।
-'वैकल्पिक ट्यूरिंग मशीन' एक गैर-नियतात्मक ट्यूरिंग मशीन है जिसके राज्यों को दो सेटों में विभाजित किया गया है: 'अस्तित्ववादी राज्य' और 'सार्वभौमिक राज्य'। एक अस्तित्वगत अवस्था स्वीकार करने वाली होती है यदि कोई परिवर्तन स्वीकार करने वाली अवस्था की ओर ले जाता है; एक सार्वभौमिक राज्य स्वीकार कर रहा है यदि प्रत्येक संक्रमण एक स्वीकार्य राज्य की ओर ले जाता है। (इस प्रकार बिना किसी परिवर्तन वाला एक सार्वभौमिक राज्य बिना किसी शर्त के स्वीकार करता है; बिना किसी संक्रमण वाला एक अस्तित्ववादी राज्य बिना किसी शर्त के अस्वीकार करता है)। यदि प्रारंभिक स्थिति स्वीकार कर रही है तो मशीन पूरी तरह से स्वीकार करती है।
+'वैकल्पिक ट्यूरिंग मशीन' एक गैर नियतात्मक ट्यूरिंग मशीन के रूप में होती है, जिसके स्टेट एक्सिस्टेंटिअल स्टेट 'और 'यूनिवर्सल स्टेट को दो सेटों में विभाजित किया जाता है और इस प्रकार यदि कोई परिवर्तन एक्सेप्ट करने वाली अवस्था की ओर ले जाता है और यूनिवर्सल स्टेट एक्सेप्ट करता है, इस प्रकार यदि प्रत्येक ट्रांजिशन एक एक्सेप्टिंग स्टेट की ओर ले जाता है। तो बिना किसी परिवर्तन वाला एक यूनिवर्सल स्टेट बिना किसी शर्त के एक्सेप्ट हो जाता है और यह बिना किसी ट्रांजिशन वाला एक एक्सिस्टेंटिअल स्टेट बिना किसी शर्त के एक्सेप्ट करता है। यदि प्रारंभिक स्टेट रिजेक्ट करता है, यदि प्रारंभिक स्टेट एक्सेप्ट कर रही है तो मशीन पूरे प्रकार से एक्सेप्ट करती है।
-=== औपचारिक परिभाषा ===
+=== फॉर्मल परिभाषा ===
-औपचारिक रूप से, एक (एक-टेप) वैकल्पिक ट्यूरिंग मशीन 5-[[ टपल ]] है <math>M=(Q,\Gamma,\delta,q_0,g)</math> कहाँ
+फॉर्मल रूप से, एक (एक-टेप) वैकल्पिक ट्यूरिंग मशीन 5-[[ टपल | टपल]] के रूप में होता है <math>M=(Q,\Gamma,\delta,q_0,g)</math> जहाँ
-* <math>Q</math> राज्यों का सीमित समूह है
+* <math>Q</math> स्टेट का परिमित सेट है
 * <math>\Gamma</math> परिमित टेप वर्णमाला है
-* <math>\delta:Q\times\Gamma\rightarrow\mathcal{P}(Q\times\Gamma\times\{L,R\})</math> इसे ट्रांज़िशन फ़ंक्शन कहा जाता है (L सिर को बाईं ओर और R सिर को दाईं ओर शिफ्ट करता है)
+* <math>\delta:Q\times\Gamma\rightarrow\mathcal{P}(Q\times\Gamma\times\{L,R\})</math> इसे ट्रांज़िशन फ़ंक्शन कहा जाता है जबकि L हेड को बाईं ओर और R हेड को दाईं ओर शिफ्ट करता है,
 * <math>q_0\in Q</math> प्रारंभिक अवस्था है
-* <math>g:Q\rightarrow\{\wedge,\vee,accept,reject\}</math> प्रत्येक राज्य का प्रकार निर्दिष्ट करता है
+* <math>g:Q\rightarrow\{\wedge,\vee,accept,reject\}</math> प्रत्येक स्टेट का प्रकार निर्दिष्ट करता है
-यदि M एक अवस्था में है <math>q\in Q</math> साथ <math>g(q)=accept</math> तब उस कॉन्फ़िगरेशन को स्वीकार करने वाला कहा जाता है, और यदि <math>g(q)=reject</math> कहा जाता है कि कॉन्फ़िगरेशन अस्वीकार हो रहा है. के साथ एक विन्यास <math>g(q)=\wedge</math> ऐसा कहा जाता है कि यदि एक चरण में पहुंच योग्य सभी कॉन्फ़िगरेशन स्वीकार हो रहे हैं, तो इसे स्वीकार किया जा रहा है, और यदि एक चरण में पहुंच योग्य कुछ कॉन्फ़िगरेशन अस्वीकार किया जा रहा है, तो इसे अस्वीकार किया जा रहा है। के साथ एक विन्यास <math>g(q)=\vee</math> इसे तब स्वीकार करना कहा जाता है जब एक चरण में पहुंचने योग्य कुछ कॉन्फ़िगरेशन मौजूद होता है, जिसे स्वीकार करना और अस्वीकार करना होता है जब एक चरण में पहुंच योग्य सभी कॉन्फ़िगरेशन अस्वीकार कर रहे होते हैं (यह अंतिम स्थिति को छोड़कर शास्त्रीय एनटीएम में सभी राज्यों का प्रकार है)। कहा जाता है कि एम एक इनपुट स्ट्रिंग डब्ल्यू को स्वीकार करता है यदि एम का प्रारंभिक विन्यास (एम की स्थिति है <math>q_0</math>, हेड टेप के बाएं छोर पर है, और टेप में w) स्वीकार करना है, और यदि प्रारंभिक कॉन्फ़िगरेशन अस्वीकार कर रहा है तो अस्वीकार करना है।
+यदि 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> के साथ एक कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है जब एक चरण में रीचबल कुछ कॉन्फ़िगरेशन के रूप में उपस्थित होते है, जो एक्सेप्ट या रिजेक्ट कर रहा होता है जब एक चरण में रीचबल सभी कॉन्फ़िगरेशन रिजेक्ट कर रहे होते हैं, तब यह अंतिम स्टेट को छोड़कर मौलिक एनटीएम में सभी स्टेट का प्रकार होता है। इस प्रकार कहा जाता है कि 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> बायीं ओर से सेल पर्याप्त है.
+एटीएम समय <math>t(n)</math> रहते [[औपचारिक भाषा|फॉर्मल]] लैंग्वेज तय कर लेता है, यदि, लंबाई के किसी भी इनपुट पर {{mvar|n}}, तक कॉन्फ़िगरेशन की जांच करता है तब <math>t(n)</math> प्रारंभिक कॉन्फ़िगरेशन को एक्सेप्ट या रिजेक्ट के रूप में लेबल करने के लिए पर्याप्त होता है। एक एटीएम क्षेत्र में एक लैंग्वेज <math>s(n)</math> तय करता है, यदि उन कॉन्फ़िगरेशनों की जांच की जा रही है जो टेप सेल को इससे परे संशोधित नहीं करते हैं और इस प्रकार <math>s(n)</math> बायीं ओर से सेल पर्याप्त है.
-एक ऐसी भाषा जो समय के साथ कुछ एटीएम द्वारा तय की जाती है <math>c\cdot t(n)</math> कुछ स्थिरांक के लिए <math>c>0</math> कहा जाता है कि वह कक्षा में है <math>\mathsf{ATIME}(t(n))</math>, और अंतरिक्ष में एक भाषा तय की गई <math>c\cdot s(n)</math> कहा जाता है कि वह कक्षा में है <math>\mathsf{ASPACE}(s(n))</math>.
+एक ऐसी लैंग्वेज जो कुछ स्थिरांक <math>c>0</math> के लिए समय <math>c\cdot t(n)</math> में कुछ एटीएम द्वारा तय की जाती है, उसे <math>\mathsf{ATIME}(t(n))</math>, क्लास कहा जाता है और क्षेत्र <math>c\cdot s(n)</math> में तय की गई लैंग्वेज को<math>\mathsf{ASPACE}(s(n))</math>.कहा जाता है।
 == उदाहरण ==
-शायद वैकल्पिक मशीनों को हल करने के लिए सबसे स्वाभाविक समस्या मात्रात्मक बूलियन सूत्र समस्या है, जो [[बूलियन संतुष्टि समस्या]] का एक सामान्यीकरण है जिसमें प्रत्येक चर को अस्तित्वगत या सार्वभौमिक मात्रात्मक द्वारा बाध्य किया जा सकता है। वैकल्पिक मशीन शाखाएँ अस्तित्वगत रूप से परिमाणित चर के सभी संभावित मूल्यों को आज़माने के लिए और सार्वभौमिक रूप से सार्वभौमिक रूप से परिमाणित चर के सभी संभावित मूल्यों को बाएँ से दाएँ क्रम में आज़माने के लिए, जिसमें वे बंधे हैं। सभी परिमाणित चरों के लिए एक मान तय करने के बाद, यदि परिणामी बूलियन सूत्र सत्य का मूल्यांकन करता है तो मशीन स्वीकार कर लेती है, और यदि गलत का मूल्यांकन करती है तो अस्वीकार कर देती है। इस प्रकार अस्तित्वगत रूप से परिमाणित चर पर मशीन स्वीकार कर रही है कि क्या चर के लिए एक मान प्रतिस्थापित किया जा सकता है जो शेष समस्या को संतोषजनक बनाता है, और एक सार्वभौमिक रूप से परिमाणित चर पर मशीन स्वीकार कर रही है कि क्या कोई मान प्रतिस्थापित किया जा सकता है और शेष समस्या संतोषजनक है।
+संभवतया वैकल्पिक मशीनों को हल करने के लिए सबसे स्वाभाविक समस्या मात्रात्मक बूलियन सूत्र समस्या है, जो [[बूलियन संतुष्टि समस्या]] का एक सामान्यीकरण है जिसमें प्रत्येक चर को एक्सिस्टेंटिअल या सार्वभौमिक मात्रात्मक द्वारा बाध्य किया जा सकता है। इस प्रकार वैकल्पिक मशीन ब्रांचेस एक्सिस्टेंटिअल रूप से परिमाणित चर के सभी संभावित मूल्यों को जांचने के लिए होते है और यूनिवर्सल रूप से परिमाणित चर के सभी संभावित मूल्यों को बाएँ से दाएँ क्रम में जांचने के लिए अपनाये जाते है, जिसमें वे बंधे होते है। सभी परिमाणित चरों के लिए एक मान तय करने के बाद यदि परिणामी बूलियन सूत्र ट्रुथ का मूल्यांकन करता है तो मशीन एक्सेप्ट कर लेती है और यदि गलत का मूल्यांकन करता है तो रिजेक्ट कर देती है। इस प्रकार एक्सिस्टेंटिअल रूप से परिमाणित चर पर मशीन एक्सेप्ट कर रही है कि क्या चर के लिए एक मान प्रतिस्थापित किया जा सकता है जो शेष समस्या को संतोषजनक बनाता है, और एक यूनिवर्सल रूप से परिमाणित चर पर मशीन एक्सेप्ट कर रही है कि क्या कोई मान प्रतिस्थापित किया जा सकता है और शेष समस्या का समाधान किया जा सकता है।
+ऐसी मशीन समय पर परिमाणित बूलियन सूत्र <math>n^2</math> और समष्टि <math>n</math>. के रूप में तय करती है
-ऐसी मशीन समय पर परिमाणित बूलियन सूत्र तय करती है <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> बहुपद समष्टि में डिसाइडेबल लैंग्वेज हैं
+* <math>\mathsf{AEXPTIME}=\bigcup_{k>0}\mathsf{ATIME}(2^{n^k})</math> क्या लैंग्वेज घातीय समय में डिसाइडेबल हैं
-निम्नलिखित  कॉम्प्लेक्सिटी वर्ग एटीएम के लिए परिभाषित करने के लिए उपयोगी हैं:
+ये एक डिटरर्मिनिस्टिक ट्यूरिंग मशीन के अतिरिक्त एटीएम द्वारा उपयोग किए जाने वाले संसाधनों पर विचार करते हुए [[P, PSPACE]] और [[EXPTIME]] की परिभाषाओं के समान हैं। चंद्रा, कोज़ेन और स्टॉकमेयर<ref name=alternation /> प्रमेयों को सिद्ध किया हैं,
-* <math>\mathsf{AP}=\bigcup_{k>0}\mathsf{ATIME}(n^k)</math> क्या भाषाएँ बहुपद समय में निर्णय लेने योग्य हैं?
-* <math>\mathsf{APSPACE}=\bigcup_{k>0}\mathsf{ASPACE}(n^k)</math> बहुपद स्थान में निर्णय लेने योग्य भाषाएँ हैं
+* ALOGSPACE = P
-* <math>\mathsf{AEXPTIME}=\bigcup_{k>0}\mathsf{ATIME}(2^{n^k})</math> क्या भाषाएँ घातीय समय में निर्णय लेने योग्य हैं
+* AP = PSPACE
+* APSPACE = EXPTIME
+* AEXPTIME = EXPSPACE
-ये एक नियतात्मक ट्यूरिंग मशीन के बजाय एटीएम द्वारा उपयोग किए जाने वाले संसाधनों पर विचार करते हुए, [[पी (जटिलता)]], पीएसपीएसीई और [[ एक्सटाइम ]] की परिभाषाओं के समान हैं। चंद्रा, कोज़ेन, और स्टॉकमेयर<ref name=alternation />प्रमेयों को सिद्ध किया
-* एलॉगस्पेस = पी
-* एपी = पीस्पेस
-* एपस्पेस = एक्सटाइम
-* एक्सपीटाइम = [[एक्सस्पेस]]
 * <math>\mathsf{ASPACE}(f(n))=\bigcup_{c>0}\mathsf{DTIME}(2^{cf(n)})=\mathsf{DTIME}(2^{O(f(n))})</math>
 * <math>\mathsf{ATIME}(g(n))\subseteq \mathsf{DSPACE}(g(n))</math>
 * <math>\mathsf{NSPACE}(g(n))\subseteq\bigcup_{c>0}\mathsf{ATIME}(c\times g(n)^2),</math>
-कब <math>f(n)\ge\log(n)</math> और <math>g(n)\ge\log(n)</math>.
+जहाँ <math>f(n)\ge\log(n)</math> और <math>g(n)\ge\log(n)</math>.
-इन संबंधों का अधिक सामान्य रूप [[समानांतर गणना थीसिस|समानांतर कम्प्यूटेशन थीसिस]] द्वारा व्यक्त किया गया है।
+इन संबंधों का अधिक सामान्य रूप से [[समानांतर गणना थीसिस|समानांतर कम्प्यूटेशन थीसिस]] द्वारा व्यक्त किया जाता है।
-== परिबद्ध प्रत्यावर्तन ==
+== बॉण्डेड ऑल्टनेशन ==
 ===परिभाषा===
-{{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{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> क्षेत्र बॉण्डेड कम्प्यूटेशन के लिए इसी प्रकार परिभाषित किया जाता है।
 === उदाहरण ===
-[[सर्किट न्यूनीकरण समस्या]] पर विचार करें: एक सर्किट ए को एक [[बूलियन फ़ंक्शन]] एफ और एक संख्या एन की कम्प्यूटेशन करते हुए, यह निर्धारित करें कि क्या अधिकतम एन गेट्स वाला एक सर्किट है जो समान फ़ंक्शन एफ की कम्प्यूटेशन करता है। एक प्रत्यावर्ती ट्यूरिंग मशीन, एक प्रत्यावर्तन के साथ, एक अस्तित्वगत स्थिति में शुरू करके, इस समस्या को बहुपद समय में हल कर सकती है (अधिकतम n द्वारों के साथ एक सर्किट बी का अनुमान लगाकर, फिर एक सार्वभौमिक स्थिति पर स्विच करके, एक इनपुट का अनुमान लगाकर, और यह जांच कर कि उस इनपुट पर बी का आउटपुट उस इनपुट पर ए के आउटपुट से मेल खाता है)।
+[[सर्किट न्यूनीकरण समस्या]] पर विचार करते है, एक सर्किट A को [[बूलियन फ़ंक्शन]] f और एक संख्या n की की गणना करते हुए यह निर्धारित करता है कि क्या अधिकतम n गेट्स वाला एक सर्किट होता है, जो समान फ़ंक्शन f की गणना करता है। एक प्रत्यावर्ती ट्यूरिंग मशीन, एक ऑल्टनेशन के साथ एक एक्सिस्टेंटिअल स्टेट में शुरू करके इस समस्या को बहुपद समय में हल कर सकती है और इस प्रकार अधिकतम n द्वारों के साथ एक सर्किट B का अनुमान लगाकर, फिर एक यूनिवर्सल स्टेट पर स्विच करके एक इनपुट का अनुमान लगाकर यह जांचना कि उस इनपुट पर B का आउटपुट उस इनपुट पर A के आउटपुट से मेल खाता है।
-=== ढहती हुई कक्षाएं ===
+=== कोलेप्सींग कक्षाएं ===
-ऐसा कहा जाता है कि पदानुक्रम स्तर तक ढह जाता है {{mvar|j}} यदि प्रत्येक भाषा स्तर में है <math>k\ge j</math> पदानुक्रम का स्तर अपने स्तर पर है {{mvar|j}}.
+ऐसा कहा जाता है कि हायरार्की स्तर तक कोलेप्स हो जाता है और इस प्रकार {{mvar|j}} यदि प्रत्येक लैंग्वेज स्तर में है और <math>k\ge j</math> हायरार्की का स्तर अपने स्तर पर {{mvar|j}}.के रूप में है
-इमरमैन-स्ज़ेलेपेसेनी प्रमेय के परिणाम के रूप में, लॉगरिदमिक अंतरिक्ष पदानुक्रम अपने पहले स्तर तक ढह जाता है।<ref>{{Cite journal|first1=Neil|last1=Immerman|url=http://www.cs.umass.edu/~immerman/pub/space.pdf|title=गैर-नियतात्मक स्थान पूरकता के तहत बंद है|journal=[[SIAM Journal on Computing]]|volume=17|issue=5|year=1988|pages=935–938|doi=10.1137/0217058|citeseerx=10.1.1.54.5941}}</ref> एक परिणाम के रूप में <math>\mathsf{SPACE}(f)</math> जब पदानुक्रम अपने पहले स्तर तक ढह जाता है <math>f=\Omega(\log)</math> स्थान निर्माण योग्य है{{Citation needed|date=August 2010}}.
+इमरमैन-स्ज़ेलेपेसेनी प्रमेय के परिणाम के रूप में, लॉगरिदमिक क्षेत्र हायरार्की अपने पहले स्तर तक कोलेप्स हो जाता है।<ref>{{Cite journal|first1=Neil|last1=Immerman|url=http://www.cs.umass.edu/~immerman/pub/space.pdf|title=गैर-नियतात्मक स्थान पूरकता के तहत बंद है|journal=[[SIAM Journal on Computing]]|volume=17|issue=5|year=1988|pages=935–938|doi=10.1137/0217058|citeseerx=10.1.1.54.5941}}</ref> एक परिणाम के रूप में <math>\mathsf{SPACE}(f)</math> जब हायरार्की अपने पहले स्तर तक कोलेप्स हो जाता है तो <math>f=\Omega(\log)</math> समष्टि कंस्ट्रक्टिबल के रूप में है
-===विशेष मामले===
+===विशेष स्टेट===
-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>, क्रमश।
-विवरण के लिए [[बहुपद पदानुक्रम]] लेख देखें।
-समय पदानुक्रम का एक और विशेष मामला [[एलएच (जटिलता)]] है।
+इन क्लास को कभी-कभी क्रमशः <math>\Sigma_k\rm{P}</math> और <math>\Pi_k\rm{P}</math> द्वारा निरूपित किया जाता है। विवरण के लिए [[बहुपद पदानुक्रम|बहुपद]] हायरार्की लेख में देख सकते है।
+समय हायरार्की का एक और विशेष स्टेट, [[एलएच (जटिलता)|लॉगरिदम हायरार्की]] के रूप में है।
 == संदर्भ ==
@@ Line 96: / Line 94: @@
 * {{cite book|author = Christos Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 978-0-201-53082-7| author-link = Christos Papadimitriou }} Section 16.2: Alternation, pp.&nbsp;399–401.
 * {{cite book|author1=Bakhadyr Khoussainov|author2=Anil Nerode|author-link2=Anil Nerode|title=Automata Theory and its Applications|url=https://books.google.com/books?id=wR_oBwAAQBAJ|year =  2012|publisher=Springer Science & Business Media|isbn=978-1-4612-0171-7}}
-{{DEFAULTSORT:Alternating Turing Machine}}[[Category: गणना के मॉडल]]
+{{DEFAULTSORT:Alternating Turing Machine}}
-[[Category: Machine Translated Page]]
+[[Category:Created On 25/07/2023|Alternating Turing Machine]]
-[[Category:Created On 25/07/2023]]
+[[Category:Lua-based templates|Alternating Turing Machine]]
+[[Category:Machine Translated Page|Alternating Turing Machine]]
+[[Category:Pages with script errors|Alternating Turing Machine]]
+[[Category:Short description with empty Wikidata description|Alternating Turing Machine]]
+[[Category:Templates Vigyan Ready|Alternating Turing Machine]]
+[[Category:Templates that add a tracking category|Alternating Turing Machine]]
+[[Category:Templates that generate short descriptions|Alternating Turing Machine]]
+[[Category:Templates using TemplateData|Alternating Turing Machine]]
+[[Category:गणना के मॉडल|Alternating Turing Machine]]

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 09:41, 23 August 2023

Contents

परिभाषाएँ

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

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

संसाधन सीमा

उदाहरण

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

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

परिभाषा

उदाहरण

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

विशेष स्टेट

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 09:41, 23 August 2023

परिभाषाएँ

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

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

संसाधन सीमा

उदाहरण

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

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

परिभाषा

उदाहरण

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

विशेष स्टेट

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories