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

एक सममित ट्यूरिंग मशीन एक ट्यूरिंग मशीन है, जिसमें एक कॉन्फ़िगरेशन ग्राफ़ होता है जो अप्रत्यक्ष रूप में होता है अर्थात कॉन्फ़िगरेशन 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: एसएल (कॉम्प्लेक्सिटी)

SSPACE(S(n)) स्थान में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत लैंग्वेज $O(S(n))$ और SL=SSPACE(log(n)). की क्लास है

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

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