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

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

परिभाषाएँ

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

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 की परिलैंग्वेजेज के समान हैं। चंद्रा, कोज़ेन और स्टॉकमेयरप्रमेयों को सिद्ध किया हैं,

• 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.के रूप में है

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

विशेष स्थिति

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

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

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

अग्रिम पठन

• 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.