सममित ट्यूरिंग मशीन

एक सममित ट्यूरिंग मशीन एक ट्यूरिंग मशीन है जिसमें एक कॉन्फ़िगरेशन ग्राफ़ होता है जो अप्रत्यक्ष होता है (अर्थात, कॉन्फ़िगरेशन i कॉन्फ़िगरेशन j उत्पन्न करता है यदि और केवल यदि j उत्पन्न होता है) मैं)।

सममित ट्यूरिंग मशीनों की परिभाषा

औपचारिक रूप से, हम फॉर्म के बदलावों के एक सेट के साथ ट्यूरिंग मशीनों के एक प्रकार को परिभाषित करते हैं $(p,ab,D,cd,q)$, जहां p,q अवस्थाएं हैं, ab,cd प्रतीकों के जोड़े हैं और D एक दिशा है। यदि D को छोड़ दिया जाता है, तो मशीन के हेड को टेप सिंबल b के ऊपर राज्य p में एक सिंबल a से पहले रखा जा सकता है, हेड को बायीं ओर ले जाकर, राज्य को q में बदलकर और सिंबल a, b को c, d से बदलकर परिवर्तित किया जा सकता है। विपरीत संक्रमण $(q,cd,-D,ab,p)$ हमेशा लागू किया जा सकता है. यदि D सही है तो संक्रमण समरूप है। एक समय में दो प्रतीकों को देखने और दोनों को बदलने की क्षमता अनावश्यक है, लेकिन परिभाषा को आसान बनाती है।

ऐसी मशीनों को पहली बार 1982 में हैरी आर. लुईस और क्रिस्टोस पापादिमित्रियोउ द्वारा परिभाषित किया गया था, जो एक ऐसे वर्ग की तलाश कर रहे थे जिसमें यूएसटीसीओएन को रखा जाए, समस्या यह पूछ रही थी कि क्या एक अप्रत्यक्ष ग्राफ़ में दो दिए गए शीर्षों s,t के बीच कोई पथ है। इस समय तक, इसे केवल एनएल (जटिलता) में रखा जा सकता था, इसके बावजूद कि गैर-नियतात्मक परिमित ऑटोमेटन की आवश्यकता नहीं थी (असममित संस्करण एसटीसीओएन एनएल के लिए पूर्ण माना जाता था)। सममित ट्यूरिंग मशीनें सीमित गैर-नियतात्मक शक्ति वाली एक प्रकार की ट्यूरिंग मशीन हैं, और इन्हें कम से कम नियतात्मक ट्यूरिंग मशीनों के समान शक्तिशाली दिखाया गया है, जो बीच में एक दिलचस्प मामला देता है।

${\mathsf {STIME}}(T(n))$ समय में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत भाषाओं का वर्ग है $O(T(n))$. इसे आसानी से साबित किया जा सकता है ${\mathsf {STIME}}(T)={\mathsf {NTIME}}(T)$ किसी भी मशीन की गैर-नियतिवाद को सीमित करके ${\mathsf {NTIME}}(T)$ एक प्रारंभिक चरण में जहां प्रतीकों की एक श्रृंखला को गैर-नियतात्मक रूप से लिखा जाता है, उसके बाद नियतात्मक गणना की जाती है।

SL=L

Main article: SL (complexity)

SSPACE(S(n)) अंतरिक्ष में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत भाषाओं का वर्ग है $O(S(n))$ और SL=SSPACE(लॉग(एन)).

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

2004 में, ओमर रींगोल्ड ने लॉगरिदमिक स्पेस में चलने वाले यूएसटीसीओएन के लिए एक नियतात्मक एल्गोरिथ्म दिखाकर साबित किया कि SL=L, जिसके लिए उन्हें 2005 ग्रेस मरे हॉपर पुरस्कार और (एवी विग्डर्सन और सलिल वधान के साथ) 2009 गोडेल पुरस्कार मिला। प्रूफ विस्तारक ग्राफ़ को कुशलतापूर्वक बनाने के लिए ज़िग-ज़ैग उत्पाद का उपयोग करता है।

संदर्भ

• Lecture Notes :CS369E: Expanders in Computer Science By Cynthia Dwork & Prahladh Harsha
• Lecture Notes
• Sharon Bruckner Lecture Notes
• Deterministic Space Bounded Graph connectivity Algorithms Jesper Janson