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

कम्प्यूटेशनल जटिलता सिद्धांत में, वैकल्पिक ट्यूरिंग मशीन (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.