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

कम्प्यूटेशनल कम्प्लेक्सिटी सिद्धांत में, वैकल्पिक ट्यूरिंग मशीन (एटीएम) गैर नियतात्मक ट्यूरिंग मशीन (एनटीएम) के रूप में होती है, जिसमें कम्प्यूटेशन एक्सेप्ट करने का एक नियम है, जो कम्प्लेक्सिटी क्लासेस एनपी और को-एनपी की परिभाषा में उपयोग किए गए नियमों को सामान्य बनाता है। एटीएम की अवधारणा अशोक के. चंद्रा और लैरी स्टॉकमेयर के द्वारा प्रस्तुत की गई थी और इंडेपेंडेंटली डेक्सटर कोज़ेन द्वारा 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$ के साथ एक कॉन्फ़िगरेशन को एक्सेप्ट करने वाला कहा जाता है जब एक चरण में रीचबल कुछ कॉन्फ़िगरेशन के रूप में उपस्थित होते है, जो एक्सेप्ट या रिजेक्ट कर रहा होता है जब एक चरण में रीचबल सभी कॉन्फ़िगरेशन रिजेक्ट कर रहे होते हैं, तब यह अंतिम स्टेट को छोड़कर मौलिक एनटीएम में सभी स्टेट का प्रकार होता है। इस प्रकार कहा जाता है कि 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.