S2S (गणित): Difference between revisions

'''गणित''' में, '''S2S''' दो उत्तराधिकारियों वाला मोनैडिक द्वितीय क्रम सिद्धांत होता है। यह ज्ञात सबसे अभिव्यंजक प्राकृतिक निर्णायक सिद्धांतों में से एक होता है, जिसमें S2S में कई निर्णायक सिद्धांतों की व्याख्या की जा सकती है। इसकी निर्णायकता 1969 में माइकल ओ. राबिन द्वारा सिद्ध की गई थी।<ref>{{Cite journal |title=अनंत पेड़ों पर दूसरे क्रम के सिद्धांतों और ऑटोमेटा की निर्णायकता|last=Rabin |first=Michael |journal=Transactions of the American Mathematical Society |volume=141 |date=1969 |url=https://www.ams.org/journals/tran/1969-141-00/S0002-9947-1969-0246760-1/S0002-9947-1969-0246760-1.pdf}}</ref>

* एक निश्चित k के लिए, स्ट्रिंग से k तक एक फलन (अर्थात् k के नीचे की प्राकृतिक संख्या) को एक समुच्चय द्वारा एनकोड किया जा सकता है। इसके अतिरिक्त, s,t ⇒ s01t{{prime}} जहां T{{prime}} t के प्रत्येक वर्ण को दोगुना कर देता है, और s ⇒ {s01t{{prime}}: t∈{0,1}^*} S2S निश्चित होता है। इसके विपरीत, संचार जटिलता युक्ति के अनुसार, S1S (नीचे) में समुच्चय की एक जोड़ी को एक समुच्चय द्वारा N ्कोड करने योग्य नहीं होता है।

S2S निर्णय लेने योग्य होते है, और S2S, S1S, WS2S, WS1S में से प्रत्येक में घातांक के रैखिक रूप से बढ़ते संग्रह के अनुरूप एक [[गैर-प्राथमिक समस्या|गैर-प्राथमिक]] निर्णय जटिलता होती है। निचली सीमा के लिए, Σ¹₁ WS1S सूत्रों पर विचार करना पर्याप्त होता है। अंकगणित (या अन्य) गणना का प्रस्ताव करने के लिए एक दूसरे क्रम के परिमाणक का उपयोग किया जा सकता है, जिसे पहले क्रम परिमाणक का उपयोग करके सत्यापित किया जा सकता है यदि हम परीक्षण कर सकते हैं कि कौन सी संख्याएं बराबर हैं। इसके लिए, यदि हम संख्याओं 1..m को उचित रूप से एनकोड करते हैं, तो हम बाइनरी प्रतिनिधित्व i1i2...im के साथ एक संख्या को i1 1 i2 2 ... im m के रूप में एनकोड कर सकते हैं, जिसके पहले एक संरक्षक होता है। संरक्षक के परीक्षण को विलय करने और चर नामों का पुन: उपयोग करने से, बिट्स की संख्या घातांक की संख्या में रैखिक होती है। इस प्रकार ऊपरी सीमा के लिए, निर्णय प्रक्रिया (नीचे) का उपयोग करके, के-फोल्ड परिमाणक विकल्प वाले सूत्रों को सूत्र की लंबाई (समान स्थिरांक के साथ) के के + ओ (1)-गुना घातांक के अनुरूप समय में तय किया जा सकता है।

प्रत्येक परिमित k के लिए, ट्री-चौड़ाई ≤k (और संबंधित ट्री अपघटन) के साथ गणनीय ग्राफ़ का मोनैडिक द्वितीय क्रम (MSओ) सिद्धांत S2S में व्याख्या योग्य होता है (कोर्सेल का प्रमेय देखें)। उदाहरण के लिए, ट्री कीMSO सिद्धांत (ग्राफ़ के रूप में) या [[श्रृंखला-समानांतर ग्राफ]] का निर्णय लेने योग्य होता है। यहां (अर्थात् सीमित हुए ट्री की चौड़ाई के लिए), हम शीर्षों (या किनारों) के एक समुच्चय के लिए परिमितता परिमाणक की व्याख्या भी कर सकते हैं, और एक निश्चित पूर्णांक के समुच्चय मॉड्यूलो में शीर्षों (या किनारों) की गिनती भी कर सकते हैं। इस प्रकार असंख्य ग्राफ़ की अनुमति देने से सिद्धांत नहीं बदलता है। इसके अतिरिक्त, तुलना के लिए, S1S सीमित हुए [[पथ-चौड़ाई]] के जुड़े ग्राफ़ की व्याख्या कर सकता है।

इसके विपरीत, असंबद्ध ट्री -चौड़ाई के ग्राफ़ के प्रत्येक समुच्चय के लिए, इसका अस्तित्व (अर्थात् Σ¹₁) यदि हम शीर्षों और किनारों दोनों पर विधेय की अनुमति देते हैं तो MSO सिद्धांत अनिर्णीत होता है। इस प्रकार, एक अर्थ में, S2S की निर्णायकता सर्वोत्तम संभव होती है। इस प्रकार असीमित ट्री-चौड़ाई वाले ग्राफ़ में बड़े ग्रिड माइनर होते हैं, जिनका उपयोग [[ट्यूरिंग मशीन]] का अनुकरण करने के लिए किया जा सकता है।

S2S में कमी करके, गणनीय आदेशों का MSO सिद्धांत निर्णायक होता है, जैसा कि उनके क्लेन-ब्रौवर आदेशों के साथ गणनीय ट्री का MSO सिद्धांत होता है। यघपि, MSO सिद्धांत (<math>\mathbb{R}</math>, <) अनिर्णीत होता है।<ref>{{Cite journal |first1=Yuri |last1=Gurevich |first2=Saharon |last2=Shelah | authorlink2=Saharon Shelah |title=अद्वैतवादी सिद्धांत और "अगली दुनिया"|journal=[[Israel Journal of Mathematics]] |date=1984 |volume=49 |issue=1–3 |pages=55–68 |doi=10.1007/BF02760646 | doi-access=free |s2cid=15807840 }}</ref><ref>{{Cite web |url=https://mathoverflow.net/questions/385530/what-is-the-turing-degree-of-the-monadic-theory-of-the-real-line |title=What is the Turing degree of the monadic theory of the real line? |publisher=MathOverflow |access-date=November 14, 2022}}</ref> इस प्रकार क्रमवाचक संख्या का MSO सिद्धांत <ω₂ निर्णय योग्य होता है; ω₂ के लिए निर्णायकता ZFC से स्वतंत्र होता है (Con(ZFC + [[कमजोर रूप से कॉम्पैक्ट कार्डिनल]] मानते हुए)) ।<ref>{{Cite journal |first1=Yuri |last1=Gurevich |first2=Menachem |last2=Magidor |first3=Saharon |last3=Shelah |date=1993 |title=The monadic theory of ω₂ |journal=The Journal of Symbolic Logic |volume=48 |issue=2 |pages=387–398 |doi=10.2307/2273556 |jstor=2273556 |s2cid=120260712 |url=https://shelah.logic.at/files/95215/141.pdf }}</ref> इसके अतिरिक्त, एक क्रमवाचक संख्या को क्रमवाचक संख्या पर मोनैडिक सेकेंड क्रम युक्ति का उपयोग करके परिभाषित किया जा सकता है यदि इसे क्रमवाचक संख्या जोड़ और गुणा द्वारा निश्चित नियमित क्रमवाचक संख्या से प्राप्त किया जा सकता है।<ref>{{Citation |chapter=Monadic definability of ordinals |first=Itay |last=Neeman|title=Computational Prospects of Infinity |series=Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore |chapter-url=https://www.math.ucla.edu/~ineeman/monadic-def.pdf |date=2008 |volume=15 |pages=193–205 |doi=10.1142/9789812796554_0010|isbn=978-981-279-654-7 }}</ref>

S1S के लिए, प्रत्येक सूत्र Δ¹₁ सूत्र, और Π⁰₂ अंकगणितीय सूत्रों के बूलियन संयोजन के बराबर होता है। इसके अतिरिक्त, प्रत्येक S1S सूत्र सूत्र के मापदंडों के संगत ω-ऑटोमेटन द्वारा स्वीकृति के बराबर होते है। इस प्रकार ऑटोमेटन एक नियतात्मक समता ऑटोमेटन हो सकता है: एक समता ऑटोमेटन में प्रत्येक स्थिति के लिए एक पूर्णांक प्राथमिकता होती है, और यदि अनंत रूप से देखी जाने वाली सर्वोच्च प्राथमिकता अधिकांशतः विषम (वैकल्पिक रूप से, सम) होती है, तो इसे स्वीकार करता है।

S2S के न्यूनतम प्रतिरूप में बाइनरी स्ट्रिंग्स पर सभी नियमित भाषाएँ सम्मलित होती हैं। इस प्रकार यह मानक प्रतिरूप का एक प्रारंभिक उप प्रतिरूप होता है, इसलिए यदि ट्री एक S2S पैरामीटर-मुक्त निश्चित समुच्चय गैर-रिक्त होता है, तो इसमें एक नियमित ट्री सम्मलित होता है। एक नियमित भाषा को एक नियमित {0,1}-लेबल पूर्ण अनंत बाइनरी ट्री (स्ट्रिंग्स पर विधेय के साथ पहचाना गया) के रूप में भी माना जा सकता है। एक लेबल वाला ट्री नियमित होता है यदि इसे प्रारंभिक शीर्ष के साथ शीर्ष-लेबल वाले परिमित निर्देशित ग्राफ को अनियंत्रित करके प्राप्त किया जा सकता है; प्रारंभिक शीर्ष से पहुंच योग्य ग्राफ़ में एक (निर्देशित) चक्र एक अनंत ट्री देता है। नियमित ट्री की इस व्याख्या और एन्कोडिंग के साथ, प्रत्येक सत्य S2S सूत्र प्राथमिक फलन अंकगणित में पहले से ही सिद्ध हो सकता है। इस प्रकार यह गैर-नियमित ट्री होता हैं जिन्हें निर्धारण के लिए गैर-विधेयात्मक समझ की आवश्यकता हो सकती है। गणना योग्य संबंध के साथ S1S (और संभवतः S2S) (मानक प्रथम क्रम भाग के साथ और बिना दोनों) के गैर-नियमित (अर्थात् गैर-नियमित भाषाओं वाले) प्रतिरूप होते हैं। यघपि , स्ट्रिंग के पुनरावर्ती समुच्चय का समुच्चय के ज्ञान और निर्धारण की विफलता के कारण S2S का प्रतिरूप नहीं बनाता है।

निर्णायकता का प्रमाण यह प्रदर्शित करता है कि प्रत्येक सूत्र एक गैर-नियतात्मक ट्री ऑटोमेटन द्वारा स्वीकृति के बराबर होता है ([[ वृक्ष स्वचालन | ट्री स्वचालन]] और अनंत-ट्री ऑटोमेटन देखें)। एक अनंत ट्री ऑटोमेटन जड़ से प्रारम्भ होता है और ट्री की ओर बढ़ता है, और यदि प्रत्येक ट्री उपखंड स्वीकार करती है। एक गैर-नियतात्मक ट्री ऑटोमेटन स्वीकार करता है कि क्या खिलाड़ी 1 के पास जीतने की रणनीति होती है, जहां खिलाड़ी 1 नए स्थितियों (p₀,p₁) की एक (वर्तमान स्थिति और इनपुट के लिए) जोड़ी का चयन करता  है, जबकि खिलाड़ी 2उपखंड का चयन करता  है, यदि 0 चयन किया जाता है तो p₀ में संक्रमण होता है और p1 अन्यथा में होता है। इस प्रकार सह-नॉन-नियतिवादी ऑटोमेटन के लिए, सभी विकल्प खिलाड़ी 2 द्वारा तय किए जाते हैं, जबकि नियतात्मक के लिए, (p0,p1) स्थिति और इनपुट द्वारा तय किया जाता है; और एक गेम ऑटोमेटन के लिए, दो खिलाड़ी उपखंड और स्थिति को सेट करने के लिए एक सीमित गेम खेलते हैं। किसी उपखंड पर स्वीकृति उपखंड पर अनंत बार देखी जाने वाली स्थितियों पर आधारित होती है; समता ऑटोमेटा यहाँ पर्याप्त रूप से सामान्य होता हैं।

सूत्रों को ऑटोमेटा में परिवर्तित करने के लिए, आधार विवाद आसान होता है, और गैर-नियतत्ववाद अस्तित्वगत परिमाणकों के अनुसार समापन देता है, इसलिए हमें मात्र पूरकता के अनुसार समापन की आवश्यकता है। इस प्रकार समता खेलों की स्थितिगत निर्धारण का उपयोग करते हुए (जहां हमें पूर्वव्यापी समझ की आवश्यकता होती है), खिलाड़ी 1 जीतने वाली रणनीति की अनुपस्थिति में एक खिलाड़ी 2 जीतने वाली रणनीति S देती है, एक सह-नॉनडेटर्मिनिस्टिक ट्री ऑटोमेटन इसकी सुदृढ़ता की पुष्टि करता है। फिर ऑटोमेटन को नियतिवादी बनाया जा सकता है (जहां हमें स्थितियों की संख्या में शीघ्रता से वृद्धि मिलती है), और इस प्रकार S का अस्तित्व एक गैर-नियतात्मक ऑटोमेटन द्वारा स्वीकृति से सामान्य होता है।

ऑटोमेटा निर्धारण: सह-नॉनडेटर्मिनिस्टिक ट्री ऑटोमेटा के निर्धारण के लिए, ω-ऑटोमेटा पर विचार करके,उपखंड की विकल्प को इनपुट के रूप में अनैतिक, ऑटोमेटन का निर्धारण करता है और नियतात्मक ट्री ऑटोमेटन के लिए इसका पर्याप्त रूप से उपयोग करता है। ध्यान दें कि यह गैर-नियतात्मक ट्री ऑटोमेटा के लिए काम नहीं करता है क्योंकि बाईं ओर जाने का निर्धारण (अर्थात् s→s0) दाहिनी उपखंड की सामग्री पर निर्भर हो सकता है; गैर-नियतिवाद के विपरीत, नियतिवादी ट्री ऑटोमेटा स्पष्ट रूप से गैर-रिक्त समुच्चयों को भी स्वीकार नहीं कर सकता है। इस प्रकार एक गैर-नियतात्मक ω-ऑटोमेटन M को निर्धारित करने के लिए (सह-नॉनडेटर्मिनिस्टिक के लिए, पूरक लें, यह ध्यान में रखते हुए कि नियतात्मक समता ऑटोमेटा पूरक के अनुसार बंद होता हैं), हम प्रत्येक नोड के साथ M के संभावित स्थितियों का एक समुच्चय संग्रहीत करने और नोड निर्माण के लिए एक सफरा ट्री का उपयोग कर सकते हैं। और उच्च प्राथमिकता वाले स्थितियों तक पहुंचने के आधार पर विलोपन कर सकते है। विवरण के लिए देखें।<ref>{{Cite conference |last=Piterman |first=Nir |title=नॉनडेटर्मिनिस्टिक बुची और स्ट्रीट ऑटोमेटा से लेकर नियतात्मक पैरिटी ऑटोमेटा तक|conference=21st Annual IEEE Symposium on Logic in Computer Science (LICS'06) |date=2006 |pages=255–264 |doi=10.1109/LICS.2006.28 |arxiv=0705.2205}}</ref> <ref>{{Cite conference |last1=Löding |first1=Christof |last2=Pirogov |first2=Anton |title=Determinization of Büchi Automata: Unifying the Approaches of Safra and Muller-Schupp |conference=ICALP 2019 |arxiv=1902.02139}}</ref>

ट्री का सिद्धांत: ट्री पर एमएओ युक्ति की निर्णायकता के लिए (अर्थात् ग्राफ़ जो ट्री हैं), यहां तक ​​​​कि पहले क्रम की वस्तुओं के लिए परिमितता और मॉड्यूलर गिनती परिमाणक के साथ, हम गणनीय ट्री को पूर्ण बाइनरी ट्री में स्थापित कर सकते हैं और S2S की निर्णायकता का उपयोग कर सकते हैं। उदाहरण के लिए, एक नोड s के लिए, हम उसके बच्चों को s1, s01, s001 इत्यादि द्वारा प्रदर्शित कर सकते हैं। इस प्रकार अनगिनत ट्री के लिए, हम शेलह-स्टुप प्रमेय (नीचे) का उपयोग कर सकते हैं। हम कार्डिनलि ω₁ वाले समुच्चय को प्रथम क्रम वस्तुओं के लिए एक विधेय भी जोड़ सकते हैं₁, और कार्डिनैलि ω₂ के लिए विधेय , और इसी तरह अनंत नियमित कार्डिनल्स के लिए भी जोड़ सकते हैं। सीमित हुए ट्री की चौड़ाई के ग्राफ़ को ट्री का उपयोग करके व्याख्या की जा सकती है, और किनारों पर विधेय के बिना यह सीमित हुए क्लिक चौड़ाई के ग्राफ़ पर भी स्थापित होता है।

अद्वैत सिद्धांतों के ट्री विस्तार: शेलह-स्टूप प्रमेय द्वारा,<ref>{{Cite journal |last=Shelah |first=Saharon |title=व्यवस्था का मोनैडिक सिद्धांत|journal=Annals of Mathematics |volume=102 |issue=3 |date=Nov 1975 |pages=379–419 |doi=10.2307/1971037 |jstor=1971037 |url=https://shelah.logic.at/files/213042/42.pdf}}</ref><ref>{{Cite web |url=https://www.mccme.ru/shen/muchnik-memorial/materials/publications/tree_str.pdf |title=The generalization of Shelah–Stup theorem |access-date=November 14, 2022}}</ref> यदि एक मोनैडिक संबंधपरक प्रतिरूप M निर्णायक होता है, तो उसका ट्री प्रतिरूप भी ऐसा ही निर्णायक होता है। उदाहरण के लिए, (औपचारिकरण का मॉड्यूलो विकल्प) S2S, {0,1} एक ट्री के प्रतिरूप होता है। ट्री प्रतिरूप में, पहले क्रम की वस्तुएं विस्तार द्वारा क्रमित M के तत्वों के परिमित अनुक्रम होता हैं, और एक M-संबंध P_i को ''P_i''<nowiki/>'(''vd''₁,...,''vd''_k) ⇔ ''P_i''(''d''₁,...,''d''_k) पर मैप किया जाता है) ''P_i''<nowiki/>' के साथ अन्यथा (''d_j''∈''M'', और v, M के तत्वों का एक (संभवतः रिक्त) अनुक्रम होता है)। प्रमाण S2S निर्णायकता प्रमाण के समान होता है। प्रत्येक चरण में, एक (नॉनडेटर्मिनिस्टिक) ऑटोमेटन को इनपुट के रूप में M वस्तुओं (संभवतः दूसरे क्रम) का एक टुपल मिलता है, और एक M फॉर्मूला निर्धारित करता है कि किस स्थिति संक्रमण की अनुमति है। खिलाड़ी 1 (जैसा कि ऊपर है) एक मैपिंग चाइल्ड⇒स्थिति का चयन करता  है जिसे सूत्र (वर्तमान स्थिति को देखते हुए) द्वारा अनुमति दी जाती है, और खिलाड़ी 2 जारी रखने के लिए चाइल्ड (नोड का) का चयन करता  है। एक गैर-नियतात्मक ऑटोमेटन द्वारा अस्वीकृति देखने के लिए, प्रत्येक (नोड, स्थिति) के लिए (चाइल्ड, स्थिति) जोड़े का एक समुच्चय का चयन करे, जैसे कि हर विकल्प के लिए, कम से कम एक जोड़े को हिट किया जाए, और इस तरह कि सभी परिणामी पथ अस्वीकृति के लिए आगे बढ़ती है।