सममित ट्यूरिंग मशीन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 10: | Line 10: | ||
== {{sans-serif|1=SL=L}} == | == {{sans-serif|1=SL=L}} == | ||
{{main|एसएल (कॉम्प्लेक्सिटी)}} | {{main|एसएल (कॉम्प्लेक्सिटी)}} | ||
{{sans-serif|SSPACE}}(S(n)) | {{sans-serif|SSPACE}}(S(n)) स्थान में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत लैंग्वेज {{tmath|O(S(n))}} और {{sans-serif|[[SL (complexity)|SL]]}}={{sans-serif|SSPACE}}(log(''n'')). की क्लास है | ||
एसएल को समान रूप से यूएसटीसीओएन के लिए कम करने योग्य समस्याओं के वर्ग [[लॉगस्पेस]] के रूप में परिभाषित किया जा सकता है। लुईस और पापादिमित्रीउ ने अपनी परिभाषा के अनुसार यूएसटीसीओएन के लिए एक नॉन-डिटर्मनिस्टिक मशीन का निर्माण करके यह दिखाया है कि उनके गुण एक समतुल्य सममित ट्यूरिंग मशीन के निर्माण को संभव बनाने के लिए पर्याप्त हैं। फिर, उन्होंने देखा कि एसएल में कोई भी भाषा यूएसटीसीओएन के लिए लॉगस्पेस रिड्यूसिबल है क्योंकि सममित गणना के गुणों से हम देख सकते हैं | एसएल को समान रूप से यूएसटीसीओएन के लिए कम करने योग्य समस्याओं के वर्ग [[लॉगस्पेस]] के रूप में परिभाषित किया जा सकता है। लुईस और पापादिमित्रीउ ने अपनी परिभाषा के अनुसार यूएसटीसीओएन के लिए एक नॉन-डिटर्मनिस्टिक मशीन का निर्माण करके यह दिखाया है कि उनके गुण एक समतुल्य सममित ट्यूरिंग मशीन के निर्माण को संभव बनाने के लिए पर्याप्त हैं। फिर, उन्होंने देखा कि एसएल में कोई भी भाषा यूएसटीसीओएन के लिए लॉगस्पेस रिड्यूसिबल है क्योंकि सममित गणना के गुणों से हम देख सकते हैं | ||
Revision as of 22:31, 6 August 2023
एक सममित ट्यूरिंग मशीन एक ट्यूरिंग मशीन है, जिसमें एक कॉन्फ़िगरेशन ग्राफ़ होता है जो अप्रत्यक्ष रूप में होता है अर्थात कॉन्फ़िगरेशन i कॉन्फ़िगरेशन j के रूप में उत्पन्न करता है। यदि इस प्रकार यह केवल j, i के रूप में उत्पन्न होता है।
सममित ट्यूरिंग मशीनों की परिभाषा
औपचारिक रूप से, हम फॉर्म के ट्रांजिशन के एक सेट के साथ ट्यूरिंग मशीनों के एक प्रकार को परिभाषित करते हैं, जहां p,q अवस्थाएं हैं और इस प्रकार ab,cd प्रतीकों के जोड़े हैं और D एक दिशा के रूप में है। यदि D को छोड़ दिया जाता है, तो मशीन के हेड को टेप सिंबल b के ऊपर स्टेट p में एक सिंबल a से पहले रखा जा सकता है और इस प्रकार हेड को बायीं ओर ले जाकर स्टेट को q में बदलकर और सिंबल a, b को c, d से बदलकर परिवर्तित किया जाता है। इस प्रकार विपरीत ट्रांजिशन अधिकांशतः के रूप में प्रयुक्त किया जाता है और यदि D सही है तो ट्रांजिशन एनालॉग होता है। एक समय में दो प्रतीकों को देखने और दोनों को बदलने की क्षमता अनावश्यक है, लेकिन इससे यह परिभाषा आसान हो जाती है।
ऐसी मशीनों को पहली बार 1982 में हैरी आर. लुईस और क्रिस्टोस पापादिमित्रियोउ द्वारा परिभाषित किया गया था,[1][2] जो USTCON को रखने के लिए एक वर्ग की तलाश कर रहे थे, इस प्रकार समस्या यह पूछ रही थी कि क्या अप्रत्यक्ष ग्राफ़ में दो दिए गए शीर्षों s,t के बीच कोई पथ है। इस समय तक, इसे केवल NL (कॉम्प्लेक्सिटी) के रूप में रखा जा सकता था, इसके अतिरिक्त नॉन-डिटर्मनिस्टिक परिमित ऑटोमेटन की आवश्यकता नहीं थी इस प्रकार एसमेट्रिक संस्करण STCON NL के लिए पूर्ण माना जाता है। सममित ट्यूरिंग मशीनें सीमित नॉन-डिटर्मनिस्टिक शक्ति वाली एक प्रकार की ट्यूरिंग मशीन के रूप में होती है और इन्हें कम से कम डिटर्मनिस्टिक ट्यूरिंग मशीनों के समान शक्तिशाली दिखाया जाता है, जो बीच में एक दिलचस्प स्थिति प्रदान करता है ।
समय में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत भाषाओं की क्लास है, इसे आसानी से साबित किया जा सकता है कि , में किसी भी मशीन की गैर-नियतिवाद को प्रारंभिक चरण तक सीमित करके जहां प्रतीकों की एक स्ट्रिंग को गैर-नियतात्मक रूप से लिखा जाता है और उसके बाद डिटर्मनिस्टिक के रूप में गणना की जाती है।
SL=L
SSPACE(S(n)) स्थान में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत लैंग्वेज और SL=SSPACE(log(n)). की क्लास है
एसएल को समान रूप से यूएसटीसीओएन के लिए कम करने योग्य समस्याओं के वर्ग लॉगस्पेस के रूप में परिभाषित किया जा सकता है। लुईस और पापादिमित्रीउ ने अपनी परिभाषा के अनुसार यूएसटीसीओएन के लिए एक नॉन-डिटर्मनिस्टिक मशीन का निर्माण करके यह दिखाया है कि उनके गुण एक समतुल्य सममित ट्यूरिंग मशीन के निर्माण को संभव बनाने के लिए पर्याप्त हैं। फिर, उन्होंने देखा कि एसएल में कोई भी भाषा यूएसटीसीओएन के लिए लॉगस्पेस रिड्यूसिबल है क्योंकि सममित गणना के गुणों से हम देख सकते हैं ग्राफ़ के अप्रत्यक्ष किनारों के रूप में विशेष विन्यास।
2004 में, ओमर रींगोल्ड ने लॉगरिदमिक स्पेस में चलने वाले यूएसटीसीओएन के लिए एक डिटर्मनिस्टिक एल्गोरिथ्म दिखाकर साबित किया कि SL=L,[3] जिसके लिए उन्हें 2005 ग्रेस मरे हॉपर पुरस्कार और (एवी विग्डर्सन और सलिल वधान के साथ) 2009 गोडेल पुरस्कार मिला। प्रूफ विस्तारक ग्राफ़ को कुशलतापूर्वक बनाने के लिए ज़िग-ज़ैग उत्पाद का उपयोग करता है।
टिप्पणियाँ
- ↑ Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms. Manuscript. 1998.
- ↑ Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science. pp.161-187. 1982.
- ↑ Reingold, Omer (2008), "Undirected connectivity in log-space", Journal of the ACM, 55 (4): 1–24, doi:10.1145/1391289.1391291, MR 2445014, S2CID 207168478, ECCC TR04-094
संदर्भ
- 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
