संगणनीय विश्लेषण

गणित और कंप्यूटर विज्ञान में, संगणनीय विश्लेषण संगणनीयता सिद्धांत के परिप्रेक्ष्य से गणितीय विश्लेषण का अध्ययन है। यह वास्तविक विश्लेषण और कार्यात्मक विश्लेषण के उन हिस्सों से संबंधित है जिन्हें कम्प्यूटेबिलिटी सिद्धांत तरीके से किया जा सकता है। क्षेत्र रचनात्मक विश्लेषण और संख्यात्मक विश्लेषण से निकटता से संबंधित है।

एक उल्लेखनीय परिणाम यह है कि अभिन्न (रीमैन इंटीग्रल के अर्थ में) संगणनीय है। इसे आश्चर्यजनक माना जा सकता है क्योंकि एक अभिन्न (ढीले शब्दों में) एक अनंत राशि है। जबकि इस परिणाम को इस तथ्य से समझाया जा सकता है कि प्रत्येक संगणनीय कार्य from $\mathbb {[} 0,1]$ को $\mathbb {R}$ समान रूप से निरंतर है, उल्लेखनीय बात यह है कि निरंतरता के मापांक की गणना हमेशा स्पष्ट रूप से दिए बिना की जा सकती है। इसी प्रकार एक आश्चर्यजनक तथ्य यह है कि जटिल फलनों की अवकल कलन भी संगणनीय है, जबकि यही परिणाम वास्तविक फलनों के लिए असत्य है।

उपरोक्त प्रेरक परिणामों का बिशप बचाओ के रचनात्मक विश्लेषण में कोई समकक्ष नहीं है। इसके बजाय, यह L. E. J. Brouwer द्वारा विकसित रचनात्मक विश्लेषण का मजबूत रूप है जो रचनात्मक तर्क में एक समकक्ष प्रदान करता है।

बुनियादी निर्माण

संगणनीय विश्लेषण करने के लिए एक लोकप्रिय मॉडल ट्यूरिंग मशीन है। टेप विन्यास और गणितीय संरचनाओं की व्याख्या इस प्रकार वर्णित है।

टाइप 2 ट्यूरिंग मशीन

टाइप 2 ट्यूरिंग मशीन तीन टेप वाली ट्यूरिंग मशीन है: एक इनपुट टेप, जो केवल पढ़ने के लिए है; एक कामकाजी टेप, जिसे लिखा और पढ़ा जा सकता है; और, विशेष रूप से, एक आउटपुट टेप, जो केवल परिशिष्ट है।

वास्तविक संख्या

इस संदर्भ में, वास्तविक संख्याओं को प्रतीकों के मनमानी अनंत अनुक्रमों के रूप में दर्शाया जाता है। उदाहरण के लिए ये अनुक्रम वास्तविक संख्या के अंकों का प्रतिनिधित्व कर सकते हैं। ऐसे अनुक्रमों की गणना करने की आवश्यकता नहीं है। दूसरी ओर, इन अनुक्रमों पर कार्य करने वाले कार्यक्रमों को उचित अर्थों में संगणनीय होने की आवश्यकता होती है।

संगणनीय कार्य

संगणनीय कार्यों को टाइप 2 ट्यूरिंग मशीन पर प्रोग्राम के रूप में दर्शाया जाता है। एक कार्यक्रम को कुल माना जाता है (आंशिक कार्य के विपरीत कुल कार्य के अर्थ में) यदि इनपुट की परवाह किए बिना आउटपुट टेप पर किसी भी संख्या में प्रतीकों को लिखने में सीमित समय लगता है। प्रोग्राम हमेशा के लिए चलते हैं, आउटपुट के तेजी से अधिक अंक उत्पन्न करते हैं।

नाम

अनंत सेटों से जुड़ी संगणनीयता के परिणाम में अक्सर नाम शामिल होते हैं, जो उन सेटों के बीच के नक्शे होते हैं और उनके सबसेट के पुनरावर्ती प्रतिनिधित्व होते हैं।

चर्चा

टाइप 1 बनाम टाइप 2 कम्प्यूटेबिलिटी का मुद्दा

टाइप 1 संगणनीयता संगणनीय विश्लेषण का भोली रूप है जिसमें एक मशीन को इनपुट को मनमाना वास्तविक संख्याओं के बजाय संगणनीय संख्याओं तक सीमित करता है।

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

वास्तविकता

इस घटना में कि कोई ट्यूरिंग मशीनों का उपयोग करने से नाखुश है (आधार पर कि वे निम्न स्तर और कुछ मनमानी हैं), स्टीफन कोल क्लेन-वेस्ले टोपोज़ नामक एक वास्तविकता टोपोज़ है जिसमें रचनात्मक विश्लेषण के लिए गणना योग्य विश्लेषण को कम कर सकते हैं। इस रचनात्मक विश्लेषण में वह सब कुछ शामिल है जो ब्रौवर स्कूल में मान्य है, न कि केवल बिशप स्कूल।

मूल परिणाम

प्रत्येक संगणनीय वास्तविक फलन सतत फलन होता है (वेहरौच 2000, पृ. 6)।

वास्तविक संख्याओं पर अंकगणितीय संक्रियाएँ संगणनीय हैं।

जबकि समानता (गणित) संबंध निर्णायकता (तर्क) नहीं है, असमान वास्तविक संख्याओं पर अधिक से अधिक विधेय निर्णायक है।

समान मानदंड ऑपरेटर भी गणना योग्य है। इसका तात्पर्य रीमैन एकीकरण की संगणनीयता से है।

रीमैन इंटीग्रल एक कम्प्यूटेशनल ऑपरेटर है: दूसरे शब्दों में, एक एल्गोरिथ्म है जो संख्यात्मक रूप से किसी भी गणना योग्य समारोह के इंटीग्रल का मूल्यांकन करेगा।

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

वास्तविक संख्याओं का एक उपसमुच्चय होता है जिसे संगणनीय संख्याएँ कहा जाता है, जो उपरोक्त परिणामों के अनुसार एक वास्तविक बंद क्षेत्र है।

सामान्य टोपोलॉजी और कम्प्यूटेबिलिटी सिद्धांत के बीच समानता

संगणनीय विश्लेषण के मूल परिणामों में से एक यह है कि प्रत्येक संगणनीय कार्य से $\mathbb {R}$ को $\mathbb {R}$ निरंतर कार्य है (वेहरौच 2000, पृष्ठ 6)। इसे और आगे ले जाने पर, यह पता चलता है कि टोपोलॉजी में बुनियादी धारणाओं और कम्प्यूटेबिलिटी में बुनियादी धारणाओं के बीच एक सादृश्य है:

• संगणनीय कार्य निरंतर कार्यों के अनुरूप होते हैं।
• अर्द्धनिर्णायक सेट खुले सेट के अनुरूप होते हैं।
• को-सेमीडेसिबल सेट बंद सेट के अनुरूप होते हैं।
• टोपोलॉजिकल सघनता का एक कम्प्यूटेशनल एनालॉग है। अर्थात्, एक उपसमुच्चय $S$ का $\mathbb {R}$ यदि यह एक अर्ध-निर्णय प्रक्रिया है तो संगणनीय रूप से कॉम्पैक्ट है$\forall _{S}$वह, एक अर्धसूत्रीविभाज्य विधेय दिया गया $P$ इनपुट के रूप में, अर्ध-तय करता है कि क्या सेट में प्रत्येक बिंदु $S$ विधेय को संतुष्ट करता है $P$.
• कम्प्यूटेशनल कॉम्पैक्टनेस की उपरोक्त धारणा हेइन-बोरेल प्रमेय के एक एनालॉग को संतुष्ट करती है। विशेष रूप से, इकाई अंतराल $[0,1]$ गणनात्मक रूप से कॉम्पैक्ट है।
• टोपोलॉजी में असतत रिक्त स्थान कम्प्यूटेबिलिटी में सेट के अनुरूप होते हैं जहां तत्वों के बीच समानता अर्ध-निर्णायक होती है।
• टोपोलॉजी में हॉसडॉर्फ स्पेस कम्प्यूटेबिलिटी में सेट के अनुरूप हैं जहां तत्वों के बीच असमानता अर्ध-निर्णायक है।

सादृश्य से पता चलता है कि सामान्य टोपोलॉजी और कम्प्यूटेबिलिटी एक दूसरे की लगभग दर्पण छवियां हैं। समानता को इस तथ्य का उपयोग करके समझाया जा सकता है कि कम्प्यूटेबिलिटी सिद्धांत और सामान्य टोपोलॉजी दोनों को रचनात्मक तर्क का उपयोग करके किया जा सकता है।

यह भी देखें

• स्पेकर अनुक्रम

संदर्भ

• Oliver Aberth (1980), Computable analysis, McGraw-Hill, ISBN 0-0700-0079-4.
• Marian Pour-El and Ian Richards (1989), Computability in Analysis and Physics, Springer-Verlag.
• Stephen G. Simpson (1999), Subsystems of second-order arithmetic.
• Klaus Weihrauch (2000), Computable analysis, Springer, ISBN 3-540-66817-9.

बाहरी संबंध

• Computability and Complexity in Analysis Network