सममित ट्यूरिंग मशीन: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 4: Line 4:
औपचारिक रूप से, हम फॉर्म  {{tmath|(p,ab,D,cd,q)}} के ट्रांजिशन के एक सेट के साथ ट्यूरिंग मशीनों के एक प्रकार को परिभाषित करते हैं, जहां p,q अवस्थाएं हैं और इस प्रकार ab,cd प्रतीकों के जोड़े हैं और D एक दिशा के रूप में है। यदि D को छोड़ दिया जाता है, तो मशीन के हेड को टेप सिंबल b के ऊपर स्टेट p में एक सिंबल a से पहले रखा जा सकता है और इस प्रकार  हेड को बायीं ओर ले जाकर  स्टेट को q में बदलकर और सिंबल a, b को c, d से बदलकर परिवर्तित किया जाता है। इस प्रकार विपरीत ट्रांजिशन अधिकांशतः {{tmath|(q,cd,-D,ab,p)}} के रूप में प्रयुक्त किया जाता है और  यदि D सही है तो ट्रांजिशन एनालॉग होता है। एक समय में दो प्रतीकों को देखने और दोनों को बदलने की क्षमता अनावश्यक है, लेकिन इससे यह परिभाषा आसान हो जाती है।
औपचारिक रूप से, हम फॉर्म  {{tmath|(p,ab,D,cd,q)}} के ट्रांजिशन के एक सेट के साथ ट्यूरिंग मशीनों के एक प्रकार को परिभाषित करते हैं, जहां p,q अवस्थाएं हैं और इस प्रकार ab,cd प्रतीकों के जोड़े हैं और D एक दिशा के रूप में है। यदि D को छोड़ दिया जाता है, तो मशीन के हेड को टेप सिंबल b के ऊपर स्टेट p में एक सिंबल a से पहले रखा जा सकता है और इस प्रकार  हेड को बायीं ओर ले जाकर  स्टेट को q में बदलकर और सिंबल a, b को c, d से बदलकर परिवर्तित किया जाता है। इस प्रकार विपरीत ट्रांजिशन अधिकांशतः {{tmath|(q,cd,-D,ab,p)}} के रूप में प्रयुक्त किया जाता है और  यदि D सही है तो ट्रांजिशन एनालॉग होता है। एक समय में दो प्रतीकों को देखने और दोनों को बदलने की क्षमता अनावश्यक है, लेकिन इससे यह परिभाषा आसान हो जाती है।


ऐसी मशीनों को पहली बार 1982 में हैरी आर. लुईस और [[क्रिस्टोस पापादिमित्रियोउ]] द्वारा परिभाषित किया गया था,<ref>Jesper Jansson. [http://www.df.lth.se/~jj/Publications/STCON2.ps Deterministic Space-Bounded Graph Connectivity Algorithms]. Manuscript. 1998.</ref><ref>Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. ''Theoretical Computer Science''. pp.161-187. 1982.</ref> जो एक ऐसे वर्ग की तलाश कर रहे थे जिसमें यू[[एसटीसीओएन]] को रखा जाए, समस्या यह पूछ रही थी कि क्या एक अप्रत्यक्ष ग्राफ़ में दो दिए गए शीर्षों s,t के बीच कोई पथ है। इस समय तक, इसे केवल [[एनएल (जटिलता)]] में रखा जा सकता था, इसके बावजूद कि गैर-नियतात्मक परिमित ऑटोमेटन की आवश्यकता नहीं थी (असममित संस्करण एसटीसीओएन एनएल के लिए पूर्ण माना जाता था)। सममित ट्यूरिंग मशीनें सीमित गैर-नियतात्मक शक्ति वाली एक प्रकार की ट्यूरिंग मशीन हैं, और इन्हें कम से कम नियतात्मक ट्यूरिंग मशीनों के समान शक्तिशाली दिखाया गया है, जो बीच में एक दिलचस्प मामला देता है।
ऐसी मशीनों को पहली बार 1982 में हैरी आर. लुईस और [[क्रिस्टोस पापादिमित्रियोउ]] द्वारा परिभाषित किया गया था,<ref>Jesper Jansson. [http://www.df.lth.se/~jj/Publications/STCON2.ps Deterministic Space-Bounded Graph Connectivity Algorithms]. Manuscript. 1998.</ref><ref>Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. ''Theoretical Computer Science''. pp.161-187. 1982.</ref> जो '''[[USTCON]]''' को रखने के लिए एक वर्ग की तलाश कर रहे थे, इस प्रकार समस्या यह पूछ रही थी कि क्या अप्रत्यक्ष ग्राफ़ में दो दिए गए शीर्षों s,t के बीच कोई पथ है। इस समय तक, इसे केवल [[एनएल (जटिलता)|NL (कॉम्प्लेक्सिटी)]] के रूप में रखा जा सकता था, इसके अतिरिक्त नॉन-डिटर्मनिस्टिक  परिमित ऑटोमेटन की आवश्यकता नहीं थी इस प्रकार एसमेट्रिक संस्करण '''STCON''' NL के लिए पूर्ण माना जाता है। सममित ट्यूरिंग मशीनें सीमित नॉन-डिटर्मनिस्टिक  शक्ति वाली एक प्रकार की ट्यूरिंग मशीन के रूप में होती है और इन्हें कम से कम डिटर्मनिस्टिक  ट्यूरिंग मशीनों के समान शक्तिशाली दिखाया जाता है, जो बीच में एक दिलचस्प स्थिति प्रदान करता है ।


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


== {{sans-serif|1=SL=L}} ==
== {{sans-serif|1=SL=L}} ==
Line 12: Line 12:
{{sans-serif|SSPACE}}(S(n)) अंतरिक्ष में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत भाषाओं का वर्ग है {{tmath|O(S(n))}} और {{sans-serif|[[SL (complexity)|SL]]}}={{sans-serif|SSPACE}}(लॉग(एन)).
{{sans-serif|SSPACE}}(S(n)) अंतरिक्ष में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत भाषाओं का वर्ग है {{tmath|O(S(n))}} और {{sans-serif|[[SL (complexity)|SL]]}}={{sans-serif|SSPACE}}(लॉग(एन)).


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


2004 में, [[ओमर रींगोल्ड]] ने लॉगरिदमिक स्पेस में चलने वाले यूएसटीसीओएन के लिए एक नियतात्मक एल्गोरिथ्म दिखाकर साबित किया कि SL=L,<ref>{{citation
2004 में, [[ओमर रींगोल्ड]] ने लॉगरिदमिक स्पेस में चलने वाले यूएसटीसीओएन के लिए एक डिटर्मनिस्टिक  एल्गोरिथ्म दिखाकर साबित किया कि SL=L,<ref>{{citation
  | last = Reingold | first = Omer | author-link = Omer Reingold
  | last = Reingold | first = Omer | author-link = Omer Reingold
  | doi = 10.1145/1391289.1391291
  | doi = 10.1145/1391289.1391291

Revision as of 21:50, 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

Main article: SL (complexity)

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

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

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

टिप्पणियाँ

  1. ↑ Jesper Jansson. Deterministic Space-Bounded Graph Connectivity Algorithms. Manuscript. 1998.
  2. ↑ Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. Theoretical Computer Science. pp.161-187. 1982.
  3. ↑ 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
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सममित_ट्यूरिंग_मशीन&oldid=243327’