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

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

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

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

${\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