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

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

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

उपरोक्त प्रेरक परिणामों का बिशप के रचनात्मक विश्लेषण में कोई समकक्ष नहीं है। इसके स्थान पर, यह ब्रौवर द्वारा विकसित रचनात्मक विश्लेषण का प्रभावशाली रूप है जो रचनात्मक तर्क में समकक्ष प्रदान करता है।

आधारभूत निर्माण

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

प्रकार 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