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

Revision as of 23:12, 6 August 2023

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

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

SL=L

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

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

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

[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

[1]

[2]

[3]

@@ Line 1: / Line 1: @@
-एक सममित [[ट्यूरिंग मशीन]] एक ट्यूरिंग मशीन है, जिसमें एक [[कॉन्फ़िगरेशन ग्राफ़]] होता है जो अप्रत्यक्ष रूप में होता है अर्थात कॉन्फ़िगरेशन i कॉन्फ़िगरेशन j के रूप में उत्पन्न करता है। यदि इस प्रकार यह केवल j, i  के रूप में उत्पन्न होता है।
+एक सममित [[ट्यूरिंग मशीन]] एक ट्यूरिंग मशीन है, जिसमें एक [[कॉन्फ़िगरेशन ग्राफ़]] होता है जो अप्रत्यक्ष रूप में होता है अर्थात कॉन्फ़िगरेशन i कॉन्फ़िगरेशन j के रूप में उत्पन्न करता है। यदि इस प्रकार यह केवल j, i के रूप में उत्पन्न होता है।
 == सममित ट्यूरिंग मशीनों की परिभाषा ==
-औपचारिक रूप से, हम फॉर्म  {{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> जो '''[[USTCON]]''' को रखने के लिए एक वर्ग की तलाश कर रहे थे, इस प्रकार समस्या यह पूछ रही थी कि क्या अप्रत्यक्ष ग्राफ़ में दो दिए गए शीर्षों s,t के बीच कोई पथ है। इस समय तक, इसे केवल [[एनएल (जटिलता)|NL (कॉम्प्लेक्सिटी)]] के रूप में रखा जा सकता था, इसके अतिरिक्त नॉन-डिटर्मनिस्टिक  परिमित ऑटोमेटन की आवश्यकता नहीं थी इस प्रकार एसमेट्रिक संस्करण '''STCON''' NL के लिए पूर्ण माना जाता है। सममित ट्यूरिंग मशीनें सीमित नॉन-डिटर्मनिस्टिक  शक्ति वाली एक प्रकार की ट्यूरिंग मशीन के रूप में होती है और इन्हें कम से कम डिटर्मनिस्टिक  ट्यूरिंग मशीनों के समान शक्तिशाली दिखाया जाता है, जो बीच में एक दिलचस्प स्थिति प्रदान करता है ।
+ऐसी मशीनों को पहली बार 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}} ==
 {{main|एसएल (कॉम्प्लेक्सिटी)}}
-{{sans-serif|SSPACE}}(S(n))  स्थान में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत लैंग्वेज  {{tmath|O(S(n))}} और {{sans-serif|[[SL (complexity)|SL]]}}={{sans-serif|SSPACE}}(log(''n'')). की क्लास  है
+{{sans-serif|SSPACE}}(S(n)) स्थान में चलने वाली सममित ट्यूरिंग मशीन द्वारा स्वीकृत लैंग्वेज {{tmath|O(S(n))}} और {{sans-serif|[[SL (complexity)|SL]]}}={{sans-serif|SSPACE}}(log(''n'')). की क्लास है
-एसएल को समान रूप से यूएसटीसीओएन के लिए कम करने योग्य समस्याओं के वर्ग [[लॉगस्पेस]] के रूप में परिभाषित किया जा सकता है। लुईस और पापादिमित्रीउ ने अपनी परिभाषा के अनुसार यूएसटीसीओएन के लिए एक नॉन-डिटर्मनिस्टिक  मशीन का निर्माण करके यह दिखाया है कि उनके गुण एक समतुल्य सममित ट्यूरिंग मशीन के निर्माण को संभव बनाने के लिए पर्याप्त हैं। फिर, उन्होंने देखा कि एसएल में कोई भी भाषा यूएसटीसीओएन के लिए लॉगस्पेस रिड्यूसिबल है क्योंकि सममित गणना के गुणों से हम देख सकते हैं
+SL को समान रूप से यूएसटीसीओएन (USTCON) के लिए रीडुसिबल समस्याओं की क्लास [[लॉगस्पेस]] के रूप में परिभाषित किया जा सकता है। लुईस और पापादिमित्रीउ ने अपनी परिभाषा के अनुसार यूएसटीसीओएन के लिए एक नॉन-डिटर्मनिस्टिक मशीन का निर्माण करके यह दिखाया है कि उनके गुण एक समतुल्य सममित ट्यूरिंग मशीन के निर्माण को संभव बनाने के लिए पर्याप्त हैं। इस प्रकार फिर उन्होंने देखा कि SL में कोई भी लैंग्वेज यूएसटीसीओएन के लिए लॉगस्पेस रिड्यूसिबल के रूप में होती है, क्योंकि सममित काम्प्यटेशन में हम विशेष कॉन्फ़िगरेशन को ग्राफ़ के अप्रत्यक्ष किनारों के रूप में देख सकते हैं।
-ग्राफ़ के अप्रत्यक्ष किनारों के रूप में विशेष विन्यास।
-में, [[ओमर रींगोल्ड]] ने लॉगरिदमिक स्पेस में चलने वाले यूएसटीसीओएन के लिए एक डिटर्मनिस्टिक  एल्गोरिथ्म दिखाकर साबित किया कि SL=L,<ref>{{citation
+में, [[ओमर रींगोल्ड]] ने लॉगरिदमिक स्पेस में चलने वाले यूएसटीसीओएन के लिए एक डिटर्मनिस्टिक SL=L एल्गोरिथ्म दिखाकर साबित किया है<ref>{{citation
   | last = Reingold | first = Omer | author-link = Omer Reingold
   | doi = 10.1145/1391289.1391291
@@ Line 25: / Line 24: @@
   | title = Undirected connectivity in log-space
   | volume = 55
-  | year = 2008| s2cid = 207168478 }}</ref> जिसके लिए उन्हें 2005 [[ग्रेस मरे हॉपर पुरस्कार]] और ([[एवी विग्डर्सन]] और [[ सलिल वधान ]] के साथ) 2009 गोडेल पुरस्कार मिला। प्रूफ [[विस्तारक ग्राफ]]़ को कुशलतापूर्वक बनाने के लिए ज़िग-ज़ैग उत्पाद का उपयोग करता है।
+  | year = 2008| s2cid = 207168478 }}</ref> जिसके लिए उन्हें 2005 [[ग्रेस मरे हॉपर पुरस्कार]] और [[एवी विग्डर्सन]] और [[ सलिल वधान |सलिल वधान]] के साथ 2009 का गोडेल पुरस्कार मिला था और इस प्रकार प्रूफ [[विस्तारक ग्राफ]] को कुशलतापूर्वक बनाने के लिए ज़िग-ज़ैग उत्पाद का उपयोग करता है।
 ==टिप्पणियाँ==

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 23:12, 6 August 2023

Contents

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

SL=L

टिप्पणियाँ

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 23:12, 6 August 2023

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

SL=L

टिप्पणियाँ

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories