गणनीय संख्या: Difference between revisions
No edit summary |
No edit summary |
||
Line 49: | Line 49: | ||
=== क्रम की गैर-अभिकलनीयता === | === क्रम की गैर-अभिकलनीयता === | ||
गणनीय संख्याओं पर क्रम संबंध गणनीय नहीं है। बता दें कि A संख्या का अनुमान लगाने वाली परिगणन युक्ति का विवरण <math>a</math> है। फिर कोई परिगणन युक्ति नहीं है जो निविष्ट A पर <nowiki>''हाँ''</nowiki> को <math>a > 0</math> और यदि <nowiki>''नहीं''</nowiki> को <math>a \le 0</math> निर्गम करती है। यह देखने के लिए, मान लीजिए कि ''A'' द्वारा वर्णित यंत्र को निर्गम 0 के रूप मे <math>\epsilon</math> सन्निकटन के रूप मे रखा जाता है। | गणनीय संख्याओं पर क्रम संबंध गणनीय नहीं है। बता दें कि A संख्या का अनुमान लगाने वाली परिगणन युक्ति का विवरण <math>a</math> है। फिर कोई परिगणन युक्ति नहीं है जो निविष्ट A पर <nowiki>''हाँ''</nowiki> को <math>a > 0</math> और यदि <nowiki>''नहीं''</nowiki> को <math>a \le 0</math> निर्गम करती है। यह देखने के लिए, मान लीजिए कि ''A'' द्वारा वर्णित यंत्र को निर्गम 0 के रूप मे <math>\epsilon</math> सन्निकटन के रूप मे रखा जाता है। यह स्पष्ट नहीं है कि यह तय करने से पहले कितना समय प्रतीक्षा करना चाहिए है कि यंत्र कभी भी सन्निकटन का उत्पादन नहीं करेगी जो a को सकारात्मक होने के लिए बाध्य करती है। इस प्रकार यंत्र को अंततः यह अनुमान लगाना होगा कि निर्गम का उत्पादन करने के लिए संख्या 0 के बराबर होगी; अनुक्रम बाद में 0 से भिन्न हो सकता है। इस विचार का उपयोग यह दिखाने के लिए किया जा सकता है कि यंत्र कुछ अनुक्रमों पर गलत है यदि यह कुल फलन की गणना करती है। इसी प्रकार की समस्या तब होती है जब गणना करने योग्य वास्तविकताओं को डेडेकिंड-कट के रूप में दर्शाया जाता है। समानता संबंध के लिए भी समानता परीक्षण गणना योग्य नहीं है। | ||
जबकि पूर्ण क्रम संबंध गणनीय नहीं है, असमान संख्याओं के जोड़े के लिए इसका प्रतिबंध गणनीय है। | जबकि पूर्ण क्रम संबंध गणनीय नहीं है, असमान संख्याओं के जोड़े के लिए इसका प्रतिबंध गणनीय है। अर्थात्, क्रमादेश है जो निविष्ट के रूप में दो परिगणन युक्ति ''A'' और ''B'' अनुमानित संख्या <math> a</math> और <math> b</math> के रूप मे लेता है, जहां <math>a \ne b</math>, और निर्गम करता है या नहीं <math>a < b</math> या <math>a > b</math> है। यह प्रयोग करने के लिए पर्याप्त है <math>\epsilon</math>- सन्निकटन जहां <math> \epsilon < |b-a|/2,</math> इसलिए तेजी से कम करके <math>\epsilon</math> (0 के निकट), अंतत: कोई यह तय कर सकता है कि क्या <math>a < b</math> या <math>a > b</math> है। | ||
=== अन्य गुण === | === अन्य गुण === | ||
गणना योग्य वास्तविक संख्याएँ विश्लेषण में प्रयुक्त वास्तविक संख्याओं के सभी गुणों को साझा नहीं करती हैं। उदाहरण के लिए, गणनीय वास्तविक संख्याओं के परिबद्ध बढ़ते गणनीय अनुक्रम की कम से कम ऊपरी सीमा गणनीय वास्तविक संख्या नहीं होनी चाहिए।{{sfnp|Bridges|Richman|1987|p=58}} इस | गणना योग्य वास्तविक संख्याएँ विश्लेषण में प्रयुक्त वास्तविक संख्याओं के सभी गुणों को साझा नहीं करती हैं। उदाहरण के लिए, गणनीय वास्तविक संख्याओं के परिबद्ध बढ़ते गणनीय अनुक्रम की कम से कम ऊपरी सीमा गणनीय वास्तविक संख्या नहीं होनी चाहिए।{{sfnp|Bridges|Richman|1987|p=58}} इस गुण के साथ एक अनुक्रम को [[स्पेकर अनुक्रम]] के रूप में जाना जाता है, क्योंकि पहला निर्माण 1949 में [[अर्नस्ट स्पेकर]] के कारण हुआ था।{{sfnp|Specker|1949}} इस तरह के प्रति-उदाहरणों के स्थिति के होते हुए भी, गणना योग्य संख्याओं के क्षेत्र में कलन और वास्तविक विश्लेषण के कुछ भागों को विकसित किया जा सकता है, जिससे [[गणना योग्य विश्लेषण]] का अध्ययन किया जा सकता है। | ||
प्रत्येक गणनीय संख्या निश्चित संख्या है | प्रत्येक गणनीय संख्या निश्चित संख्या है अंकगणित में निश्चितता, लेकिन इसके विपरीत नहीं है। कई अंकगणितीय निश्चित, गैर-गणना योग्य वास्तविक संख्याएँ हैं, जिनमें सम्मिलित हैं: | ||
*कोई भी संख्या जो किसी चुनी हुई एन्कोडिंग योजना के अनुसार हॉल्टिंग समस्या (या किसी अन्य [[अनिर्णीत समस्या]]) के समाधान को एनकोड करती है। | *कोई भी संख्या जो किसी चुनी हुई एन्कोडिंग योजना के अनुसार हॉल्टिंग समस्या (या किसी अन्य [[अनिर्णीत समस्या]]) के समाधान को एनकोड करती है। | ||
*चैटिन स्थिरांक, <math>\Omega</math>, जो एक प्रकार की वास्तविक संख्या है जो हॉल्टिंग समस्या के लिए परिगणन डिग्री है। | *चैटिन स्थिरांक, <math>\Omega</math>, जो एक प्रकार की वास्तविक संख्या है जो हॉल्टिंग समस्या के लिए परिगणन डिग्री है। | ||
Line 77: | Line 77: | ||
जब तक वास्तविक संख्याओं के कुछ सामयिक गुण प्रासंगिक नहीं होते हैं, तब तक के तत्वों से निपटना प्रायः अधिक सुविधाजनक होता है <math>2^{\omega}</math> (कुल 0,1 मूल्यवान फलन) वास्तविक संख्याओं के बजाय <math>[0,1]</math>. के सदस्य <math>2^{\omega}</math> बाइनरी दशमलव विस्तार के साथ पहचाना जा सकता है, लेकिन दशमलव विस्तार के बाद से <math>.d_1d_2\ldots d_n0111\ldots</math> और <math>.d_1d_2\ldots d_n10</math> एक ही वास्तविक संख्या, अंतराल को निरूपित करें <math>[0,1]</math> के उपसमुच्चय के साथ पहचाने जाने पर केवल जैविक रूप से (और उपसमुच्चय टोपोलॉजी के तहत होमोमोर्फिक रूप से) हो सकता है <math>2^{\omega}</math> सभी 1 में समाप्त नहीं हो रहा है। | जब तक वास्तविक संख्याओं के कुछ सामयिक गुण प्रासंगिक नहीं होते हैं, तब तक के तत्वों से निपटना प्रायः अधिक सुविधाजनक होता है <math>2^{\omega}</math> (कुल 0,1 मूल्यवान फलन) वास्तविक संख्याओं के बजाय <math>[0,1]</math>. के सदस्य <math>2^{\omega}</math> बाइनरी दशमलव विस्तार के साथ पहचाना जा सकता है, लेकिन दशमलव विस्तार के बाद से <math>.d_1d_2\ldots d_n0111\ldots</math> और <math>.d_1d_2\ldots d_n10</math> एक ही वास्तविक संख्या, अंतराल को निरूपित करें <math>[0,1]</math> के उपसमुच्चय के साथ पहचाने जाने पर केवल जैविक रूप से (और उपसमुच्चय टोपोलॉजी के तहत होमोमोर्फिक रूप से) हो सकता है <math>2^{\omega}</math> सभी 1 में समाप्त नहीं हो रहा है। | ||
ध्यान दें कि दशमलव विस्तार की इस | ध्यान दें कि दशमलव विस्तार की इस गुण का तात्पर्य है कि दशमलव विस्तार के संदर्भ में परिभाषित गणनीय वास्तविक संख्याओं की प्रभावी ढंग से पहचान करना असंभव है और जो दशमलव विस्तार में परिभाषित हैं <math>\epsilon</math> सन्निकटन भाव। हिस्ट ने दिखाया है कि ऐसा कोई एल्गोरिदम नहीं है जो निविष्ट के रूप में एक परिगणन युक्ति का विवरण लेता है जो उत्पादन करता है <math>\epsilon</math> गणना योग्य संख्या a के लिए सन्निकटन, और निर्गम के रूप में एक परिगणन युक्ति उत्पन्न करता है जो परिगणन की परिभाषा के अर्थ में a के अंकों की गणना करता है।{{sfnp|Hirst|2007}} इसी प्रकार, इसका अर्थ है कि गणना योग्य वास्तविक पर अंकगणितीय संचालन दशमलव संख्याओं को जोड़ते समय उनके दशमलव निरूपण पर प्रभावी नहीं होते हैं। एक अंक का उत्पादन करने के लिए, यह निर्धारित करने के लिए कि क्या वर्तमान स्थान पर कोई कैरी है, मनमाने ढंग से दाईं ओर देखना आवश्यक हो सकता है। एकरूपता की यह कमी एक कारण है कि गणना योग्य संख्याओं की समकालीन परिभाषा का उपयोग क्यों किया जाता है <math>\epsilon</math> दशमलव विस्तार के बजाय सन्निकटन। | ||
हालाँकि, एक [[संगणनीयता सिद्धांत|अभिकलनीयता सिद्धांत]] या [[माप सिद्धांत]] के दृष्टिकोण से, दो संरचनाएँ <math>2^{\omega}</math> और <math>[0,1]</math> मूलतः समान हैं। इस प्रकार, कम्प्यूटेबिलिटी सिद्धांतकार प्रायः सदस्यों को संदर्भित करते हैं <math>2^{\omega}</math> वास्तविक के रूप में। जबकि <math>2^{\omega}</math> के बारे में सवालों के लिए [[पूरी तरह से डिस्कनेक्ट किया गया स्थान]] है <math>\Pi^0_1</math> कक्षाओं या यादृच्छिकता में काम करना आसान होता है <math>2^{\omega}</math>. | हालाँकि, एक [[संगणनीयता सिद्धांत|अभिकलनीयता सिद्धांत]] या [[माप सिद्धांत]] के दृष्टिकोण से, दो संरचनाएँ <math>2^{\omega}</math> और <math>[0,1]</math> मूलतः समान हैं। इस प्रकार, कम्प्यूटेबिलिटी सिद्धांतकार प्रायः सदस्यों को संदर्भित करते हैं <math>2^{\omega}</math> वास्तविक के रूप में। जबकि <math>2^{\omega}</math> के बारे में सवालों के लिए [[पूरी तरह से डिस्कनेक्ट किया गया स्थान]] है <math>\Pi^0_1</math> कक्षाओं या यादृच्छिकता में काम करना आसान होता है <math>2^{\omega}</math>. |
Revision as of 12:06, 8 February 2023
गणित में, गणनीय संख्याएँ वास्तविक संख्याएँ होती हैं, जिनकी गणना परिमित, समाप्ति कलन विधि द्वारा किसी भी वांछित परिशुद्धता के अंदर की जा सकती है। उन्हें पुनरावर्ती संख्याओं, प्रभावी संख्याओं[1] या गणनीय वास्तविक या पुनरावर्ती वास्तविक के रूप में भी जाना जाता है।[citation needed] गणनीय वास्तविक संख्या की अवधारणा एमिल बोरेल द्वारा 1912 में उस समय उपलब्ध अभिकलनीयता की अंतःप्रज्ञात्मक धारणा का उपयोग करके प्रस्तुत की गई थी।[2]
एल्गोरिदम के औपचारिक प्रतिनिधित्व के रूप में μ-पुनरावर्ती फलन, परिगणन (ट्यूरिंग) मशीनें, या λ-गणना का उपयोग करके समतुल्य परिभाषाएं दी जा सकती हैं। गणनीय संख्याएं वास्तविक संवृत क्षेत्र बनाती हैं और वास्तविक संख्याओं के स्थान पर कई गणितीय उद्देश्यों के लिए नहीं बल्कि अधिक के लिए उपयोग की जा सकती हैं।।
उदाहरण के रूप में परिगणन युक्ति का उपयोग करके अनौपचारिक परिभाषा
निम्नलिखित में, मार्विन मिंस्की ने 1936 में एलन परिगणन द्वारा परिभाषित किए गए तरीकों के समान गणना की जाने वाली संख्याओं को परिभाषित किया;[3] अर्थात, 0 और 1 के बीच दशमलव अंशों के रूप में व्याख्या किए गए अंकों के अनुक्रम के रूप में:[4]
संगणनीय संख्या [है] जिसके लिए परिगणन युक्ति है, जो कि इसके प्रारंभिक टेप पर n दी गई है, उस संख्या के n वें अंक के साथ समाप्त होती है [इसके टेप पर एन्कोडेड]।
परिभाषा में मुख्य धारणाएं हैं (1) कि कुछ n प्रारंभ में निर्दिष्ट हैं, (2) किसी भी n के लिए गणना केवल परिमित संख्या के चरण होते है, जिसके बाद यंत्र वांछित निर्गम उत्पन्न करती है और समाप्त हो जाती है।
(2) का एक वैकल्पिक रूप - यंत्र क्रमिक रूप से अपने टेप पर सभी n अंकों को मुद्रित करती है, nवें को मुद्रित करने के बाद रुकने से मिंस्की के अवलोकन पर जोर देती है: (3) कि परिगणन युक्ति के उपयोग से, परिमित परिभाषा के रूप में यंत्र की अवस्था सारणी का उपयोग दशमलव अंकों की संभावित अनंत शृंखला को परिभाषित करने के लिए किया जा रहा है।
हालांकि यह आधुनिक परिभाषा नहीं है जिसके लिए किसी भी परिशुद्धता के अंदर केवल परिणाम की आवश्यकता होती है। उपरोक्त अनौपचारिक परिभाषा पूर्णांकन समस्या के अधीन है जिसे तालिका-निर्माता का विकल्प कहा जाता है जबकि आधुनिक परिभाषा नहीं है।
औपचारिक परिभाषा
एक वास्तविक संख्या a 'गणना योग्य' है यदि इसे किसी गणना योग्य फलन द्वारा अनुमानित किया जा सकता है निम्नलिखित तरीके से: किसी भी सकारात्मक पूर्णांक n को देखते हुए, फलन पूर्णांक f(n) उत्पन्न करता है जैसे कि:
इसी तरह की दो परिभाषाएँ हैं जो समकक्ष हैं:
- एक गणनीय फलन सम्मिलित है, जो किसी भी सकारात्मक तर्कसंगत त्रुटि के लिए बाध्य है , एक परिमेय संख्या r उत्पन्न करता है जैसे कि
- परिमेय संख्याओं का गणनीय अनुक्रम है, में अभिसरण ऐसा है कि प्रत्येक i के लिए
गणनीय डेडेकिन्ड-कट के माध्यम से गणनीय संख्याओं की अन्य समतुल्य परिभाषा है। एक 'गणनीय डेडेकाइंड कट' एक गणनीय फलन है जो परिमेय संख्या के साथ प्रदान किया जाता है निविष्ट प्रतिफल के रूप में या , निम्नलिखित शर्तों को पूरा करना:
क्रमादेश D द्वारा एक उदाहरण दिया गया है जो 3 के घनमूल को परिभाषित करता है। मान लीजिए के द्वारा परिभाषित किया गया है:
एक वास्तविक संख्या की गणना तभी की जा सकती है जब और केवल तभी जब कोई गणनीय डेडेकिन्ड-कट D इसके अनुरूप है। फलन डी प्रत्येक गणना योग्य संख्या के लिए अद्वितीय है (हालांकि निश्चित रूप से दो अलग-अलग क्रमादेश समान फलन प्रदान कर सकते हैं)।
एक सम्मिश्र संख्या को गणनीय कहा जाता है यदि उसके वास्तविक और काल्पनिक भाग गणनीय हों।
गुण
गणनीय रूप से गणना योग्य नहीं
प्रत्येक परिगणन युक्ति परिभाषा के लिए गोडेल संख्या निर्दिष्ट करना गणनीय संख्याओं के अनुरूप प्राकृतिक संख्याओं का उपसमुच्चय उत्पन्न करता है और से गणना योग्य संख्याओं के लिए अन्य अनुमान की पहचान करता है। केवल गणनीय कई परिगणन युक्ति हैं, जो दर्शाती हैं कि गणना योग्य संख्याएँ उपगणनीय हैं। हालांकि इन गोडेल संख्याओं समुच्चय , गणनीय रूप से गणना योग्य नहीं है (और परिणामस्वरूप, न तो के उपसमुच्चय हैं जिन्हें इसके संदर्भ में परिभाषित किया गया है)। ऐसा इसलिए है क्योंकि यह निर्धारित करने के लिए कोई एल्गोरिथ्म नहीं है कि कौन से गोडेल नंबर परिगणन मशीनों के अनुरूप हैं जो गणना योग्य वास्तविक उत्पादन करते हैं। गणना योग्य वास्तविक का उत्पादन करने के लिए, परिगणन युक्ति को कुल फलन की गणना करनी चाहिए, लेकिन संगत परिणाम समस्या परिगणन श्रेणी 0 में है। परिणामस्वरूप, प्राकृतिक संख्याओं से गणनीय वास्तविक तक कोई विशेषण गणनीय फलन नहीं है, और कैंटर के विकर्ण तर्क का उपयोग रचनात्मक रूप से (गणित) उनमें से कई को प्रदर्शित करने के लिए नहीं किया जा सकता है।
जबकि वास्तविक संख्याओं का समुच्चय असंख्य है, गणनीय संख्याओं का समूह श्रेणीबद्ध रूप से गणना योग्य है और इस प्रकार लगभग सभी वास्तविक संख्याएँ गणनीय नहीं हैं। यहाँ, किसी भी गणना योग्य संख्या के लिए क्रमित सिद्धांत प्रदान करता है कि इसमें एक न्यूनतम तत्व है जो के अनुरूप है, और इसलिए न्यूनतम तत्वों से युक्त एक उपसमुच्चय सम्मिलित है, जिस पर मानचित्र द्विअंत:क्षेपण है। इस आक्षेप का व्युत्क्रम गणनीय संख्याओं की प्राकृतिक संख्याओं में विशेषण फलन है, यह प्रमाणित करता है कि वे गणनीय हैं। लेकिन, पुनः, यह उपसमुच्चय गणनीय नहीं है, यद्यपि गणनीय वास्तविक स्वयं क्रमित किया गया हो।
क्षेत्र के रूप में गुण
गणनीय संख्याओं पर अंकगणितीय संक्रियाएँ स्वयं इस अर्थ में गणनीय हैं कि जब भी वास्तविक संख्याएँ a और b गणनीय होती हैं तो निम्नलिखित वास्तविक संख्याएँ भी गणनीय होती हैं: a + b, a - b, ab, और a/b यदि b अशून्य है। ये संक्रिया वास्तव में समान रूप से गणनीय हैं; उदाहरण के लिए, परिगणन युक्ति है जो निविष्ट (A, B, ) निर्गम r का उत्पादन करता है, जहां A अनुमानित परिगणन युक्ति का विवरण है, a, B अनुमानित परिगणन युक्ति का विवरण है, और r a+b का सन्निकटन है।
तथ्य यह है कि गणनीय वास्तविक संख्याएँ एक क्षेत्र (गणित) को पहली बार 1954 में हेनरी गॉर्डन राइस द्वारा सिद्ध किया गया था।[5]
गणनीय वास्तविक हालांकि एक गणनीय क्षेत्र नहीं बनाते हैं, क्योंकि गणनीय क्षेत्र की परिभाषा के लिए प्रभावी समानता की आवश्यकता होती है।
क्रम की गैर-अभिकलनीयता
गणनीय संख्याओं पर क्रम संबंध गणनीय नहीं है। बता दें कि A संख्या का अनुमान लगाने वाली परिगणन युक्ति का विवरण है। फिर कोई परिगणन युक्ति नहीं है जो निविष्ट A पर ''हाँ'' को और यदि ''नहीं'' को निर्गम करती है। यह देखने के लिए, मान लीजिए कि A द्वारा वर्णित यंत्र को निर्गम 0 के रूप मे सन्निकटन के रूप मे रखा जाता है। यह स्पष्ट नहीं है कि यह तय करने से पहले कितना समय प्रतीक्षा करना चाहिए है कि यंत्र कभी भी सन्निकटन का उत्पादन नहीं करेगी जो a को सकारात्मक होने के लिए बाध्य करती है। इस प्रकार यंत्र को अंततः यह अनुमान लगाना होगा कि निर्गम का उत्पादन करने के लिए संख्या 0 के बराबर होगी; अनुक्रम बाद में 0 से भिन्न हो सकता है। इस विचार का उपयोग यह दिखाने के लिए किया जा सकता है कि यंत्र कुछ अनुक्रमों पर गलत है यदि यह कुल फलन की गणना करती है। इसी प्रकार की समस्या तब होती है जब गणना करने योग्य वास्तविकताओं को डेडेकिंड-कट के रूप में दर्शाया जाता है। समानता संबंध के लिए भी समानता परीक्षण गणना योग्य नहीं है।
जबकि पूर्ण क्रम संबंध गणनीय नहीं है, असमान संख्याओं के जोड़े के लिए इसका प्रतिबंध गणनीय है। अर्थात्, क्रमादेश है जो निविष्ट के रूप में दो परिगणन युक्ति A और B अनुमानित संख्या और के रूप मे लेता है, जहां , और निर्गम करता है या नहीं या है। यह प्रयोग करने के लिए पर्याप्त है - सन्निकटन जहां इसलिए तेजी से कम करके (0 के निकट), अंतत: कोई यह तय कर सकता है कि क्या या है।
अन्य गुण
गणना योग्य वास्तविक संख्याएँ विश्लेषण में प्रयुक्त वास्तविक संख्याओं के सभी गुणों को साझा नहीं करती हैं। उदाहरण के लिए, गणनीय वास्तविक संख्याओं के परिबद्ध बढ़ते गणनीय अनुक्रम की कम से कम ऊपरी सीमा गणनीय वास्तविक संख्या नहीं होनी चाहिए।[6] इस गुण के साथ एक अनुक्रम को स्पेकर अनुक्रम के रूप में जाना जाता है, क्योंकि पहला निर्माण 1949 में अर्नस्ट स्पेकर के कारण हुआ था।[7] इस तरह के प्रति-उदाहरणों के स्थिति के होते हुए भी, गणना योग्य संख्याओं के क्षेत्र में कलन और वास्तविक विश्लेषण के कुछ भागों को विकसित किया जा सकता है, जिससे गणना योग्य विश्लेषण का अध्ययन किया जा सकता है।
प्रत्येक गणनीय संख्या निश्चित संख्या है अंकगणित में निश्चितता, लेकिन इसके विपरीत नहीं है। कई अंकगणितीय निश्चित, गैर-गणना योग्य वास्तविक संख्याएँ हैं, जिनमें सम्मिलित हैं:
- कोई भी संख्या जो किसी चुनी हुई एन्कोडिंग योजना के अनुसार हॉल्टिंग समस्या (या किसी अन्य अनिर्णीत समस्या) के समाधान को एनकोड करती है।
- चैटिन स्थिरांक, , जो एक प्रकार की वास्तविक संख्या है जो हॉल्टिंग समस्या के लिए परिगणन डिग्री है।
ये दोनों उदाहरण वास्तव में प्रत्येक यूनिवर्सल परिगणन युक्ति के लिए निश्चित, अगणनीय संख्याओं के एक अनंत समुच्चय को परिभाषित करते हैं। एक वास्तविक संख्या की गणना की जा सकती है यदि और केवल तभी जब प्राकृतिक संख्याओं का वह समुच्चय (जब बाइनरी में लिखा जाता है और एक विशिष्ट फलन के रूप में देखा जाता है) गणना योग्य होता है।
गणनीय वास्तविक संख्याओं का समुच्चय (साथ ही प्रत्येक गणनीय, सघन रूप से बिना सिरों के गणनीय वास्तविकों का उपसमुच्चय) तर्कसंगत संख्याओं के समुच्चय के लिए आदेश-समरूपी है।
डिजिट स्ट्रिंग्स और कैंटर और बायर स्पेस
परिगणन के मूल पेपर में गणना योग्य संख्याओं को निम्नानुसार परिभाषित किया गया है:
वास्तविक संख्या की गणना की जा सकती है यदि इसके अंक अनुक्रम को किसी कलन विधि या परिगणन युक्ति द्वारा निर्मित किया जा सकता है। एल्गोरिदम इनपुट के रूप में एक पूर्णांक लेता है और आउटपुट के रूप में वास्तविक संख्या के दशमलव विस्तार के -वें अंक का उत्पादन करता है।
(a का दशमलव विस्तार केवल दशमलव बिंदु के बाद वाले अंकों को संदर्भित करता है।)
परिगणन जानते थे कि यह परिभाषा इसके समतुल्य है -अनुमान परिभाषा ऊपर दी गई है। तर्क इस प्रकार आगे बढ़ता है: यदि कोई संख्या परिगणन अर्थ में गणना योग्य है, तो यह भी गणना योग्य है भावार्थ: यदि , तो a के लिए दशमलव प्रसार के पहले n अंक a प्रदान करते हैं ए का अनुमान। बातचीत के लिए, हम एक चुनते हैं गणना योग्य वास्तविक संख्या a और दशमलव बिंदु के बाद n वें अंक तक निश्चित रूप से परिशुद्ध सन्निकटन उत्पन्न करते हैं। यह हमेशा एक के बराबर एक दशमलव विस्तार उत्पन्न करता है लेकिन यह 9 के अनंत अनुक्रम में अनुचित रूप से समाप्त हो सकता है, इस मामले में इसका एक परिमित (और इस प्रकार गणना योग्य) उचित दशमलव विस्तार होना चाहिए।
जब तक वास्तविक संख्याओं के कुछ सामयिक गुण प्रासंगिक नहीं होते हैं, तब तक के तत्वों से निपटना प्रायः अधिक सुविधाजनक होता है (कुल 0,1 मूल्यवान फलन) वास्तविक संख्याओं के बजाय . के सदस्य बाइनरी दशमलव विस्तार के साथ पहचाना जा सकता है, लेकिन दशमलव विस्तार के बाद से और एक ही वास्तविक संख्या, अंतराल को निरूपित करें के उपसमुच्चय के साथ पहचाने जाने पर केवल जैविक रूप से (और उपसमुच्चय टोपोलॉजी के तहत होमोमोर्फिक रूप से) हो सकता है सभी 1 में समाप्त नहीं हो रहा है।
ध्यान दें कि दशमलव विस्तार की इस गुण का तात्पर्य है कि दशमलव विस्तार के संदर्भ में परिभाषित गणनीय वास्तविक संख्याओं की प्रभावी ढंग से पहचान करना असंभव है और जो दशमलव विस्तार में परिभाषित हैं सन्निकटन भाव। हिस्ट ने दिखाया है कि ऐसा कोई एल्गोरिदम नहीं है जो निविष्ट के रूप में एक परिगणन युक्ति का विवरण लेता है जो उत्पादन करता है गणना योग्य संख्या a के लिए सन्निकटन, और निर्गम के रूप में एक परिगणन युक्ति उत्पन्न करता है जो परिगणन की परिभाषा के अर्थ में a के अंकों की गणना करता है।[8] इसी प्रकार, इसका अर्थ है कि गणना योग्य वास्तविक पर अंकगणितीय संचालन दशमलव संख्याओं को जोड़ते समय उनके दशमलव निरूपण पर प्रभावी नहीं होते हैं। एक अंक का उत्पादन करने के लिए, यह निर्धारित करने के लिए कि क्या वर्तमान स्थान पर कोई कैरी है, मनमाने ढंग से दाईं ओर देखना आवश्यक हो सकता है। एकरूपता की यह कमी एक कारण है कि गणना योग्य संख्याओं की समकालीन परिभाषा का उपयोग क्यों किया जाता है दशमलव विस्तार के बजाय सन्निकटन।
हालाँकि, एक अभिकलनीयता सिद्धांत या माप सिद्धांत के दृष्टिकोण से, दो संरचनाएँ और मूलतः समान हैं। इस प्रकार, कम्प्यूटेबिलिटी सिद्धांतकार प्रायः सदस्यों को संदर्भित करते हैं वास्तविक के रूप में। जबकि के बारे में सवालों के लिए पूरी तरह से डिस्कनेक्ट किया गया स्थान है कक्षाओं या यादृच्छिकता में काम करना आसान होता है .
के तत्व कभी-कभी वास्तविक भी कहा जाता है और यद्यपि इसमें होमियोमोर्फिज्म की छवि होती है , स्थानीय रूप स्थानीय रूप से कॉम्पैक्ट स्थान भी नहीं है (पूरी तरह से डिस्कनेक्ट होने के अलावा)। इससे गणनीय गुणों में वास्तविक अंतर होता है। उदाहरण के लिए संतुष्टि देने वाला , साथ क्वांटिफायर मुक्त, अद्वितीय होने पर गणना योग्य होना चाहिए एक सार्वभौमिक सूत्र को संतुष्ट करने से हाइपरअरिथमेटिक पदानुक्रम में मनमाने ढंग से उच्च स्थान हो सकता है।
== वास्तविक == के स्थान पर प्रयोग करें
गणना योग्य संख्याओं में विशिष्ट वास्तविक संख्याएँ सम्मिलित होती हैं जो व्यवहार में दिखाई देती हैं, जिसमें सभी वास्तविक बीजगणितीय संख्याएँ, साथ ही ई, π, और कई अन्य पारलौकिक संख्याएँ सम्मिलित हैं। यद्यपि गणनीय वास्तविक उन वास्तविकताओं को समाप्त कर देते हैं जिनकी हम गणना या अनुमान लगा सकते हैं, यह धारणा कि सभी वास्तविक गणना योग्य हैं, वास्तविक संख्याओं के बारे में काफी भिन्न निष्कर्ष निकालते हैं। स्वाभाविक रूप से यह प्रश्न उठता है कि क्या सभी गणित के लिए वास्तविक के पूर्ण समुच्चय का निपटान करना और गणना योग्य संख्याओं का उपयोग करना संभव है। यह विचार एक रचनावाद (गणित) के दृष्टिकोण से आकर्षक है, और बिशप बचाओ और फ्रेड रिचमैन द्वारा रचनात्मक गणित के रूसी स्कूल को क्या कहते हैं, इसका पालन किया गया है।[citation needed] [9] गणना योग्य संख्याओं पर वास्तव में विश्लेषण विकसित करने के लिए, कुछ सावधानी बरतनी चाहिए। उदाहरण के लिए, यदि कोई अनुक्रम की शास्त्रीय परिभाषा का उपयोग करता है, तो गणना योग्य संख्याओं का समुच्चय एक बंधे हुए अनुक्रम के सर्वोच्च को लेने के मूल संचालन के तहत बंद नहीं होता है (उदाहरण के लिए, स्पेकर अनुक्रम पर विचार करें, ऊपर अनुभाग देखें)। इस कठिनाई को केवल उन अनुक्रमों पर विचार करके संबोधित किया जाता है जिनमें अभिसरण का एक गणनीय मापांक होता है। परिणामी गणितीय सिद्धांत को गणनीय विश्लेषण कहा जाता है।
== परिशुद्ध अंकगणित == का कार्यान्वयन
सन्निकटन की गणना करने वाले कार्यक्रमों के रूप में वास्तविक संख्याओं का प्रतिनिधित्व करने वाले कंप्यूटर पैकेजों को परिशुद्ध अंकगणित नाम के तहत 1985 की शुरुआत में प्रस्तावित किया गया है।[10] आधुनिक उदाहरणों में CoRN लाइब्रेरी (Coq) सम्मिलित है,[11] और रीयललिब पैकेज (सी ++)।[12] फलन की एक संबंधित रेखा एक वास्तविक रैम क्रमादेश लेने और पर्याप्त परिशुद्धता के तर्कसंगत या फ्लोटिंग-पॉइंट संख्या के साथ चलाने पर आधारित है, जैसे iRRAM पैकेज।[13]
यह भी देखें
- रचनात्मक संख्या
- परिभाषित करने योग्य संख्या
- अर्धगणना योग्य फलन
- परिकलन संबंधी समस्या
टिप्पणियाँ
- ↑ van der Hoeven (2006).
- ↑ P. Odifreddi, Classical Recursion Theory (1989), p.8. North-Holland, 0-444-87295-7
- ↑ Turing (1936).
- ↑ Minsky (1967).
- ↑ Rice (1954).
- ↑ Bridges & Richman (1987), p. 58.
- ↑ Specker (1949).
- ↑ Hirst (2007).
- ↑ Zalta, Edward N., ed. (2022), "Russian School of Constructive Mathematics", Constructive Mathematics, Metaphysics Research Lab, Stanford University
- ↑ Boehm, Hans-J.; Cartwright, Robert; Riggle, Mark; O'Donnell, Michael J. (8 August 1986). "Exact real arithmetic: a case study in higher order programming" (PDF). Proceedings of the 1986 ACM conference on LISP and functional programming: 162–173. doi:10.1145/319838.319860. Archived (PDF) from the original on 2020-09-24.
- ↑ O’Connor, Russell (2008). "Certified Exact Transcendental Real Number Computation in Coq" (PDF). Theorem Proving in Higher Order Logics: 246–261. doi:10.1007/978-3-540-71067-7_21. Archived (PDF) from the original on 2022-03-24.
- ↑ Lambov (2015).
- ↑ Gowland, Paul; Lester, David (2001). "A Survey of Exact Arithmetic Implementations" (PDF). Computability and Complexity in Analysis (in English). Springer: 30–47. doi:10.1007/3-540-45335-0_3. Archived (PDF) from the original on 2022-03-24.
संदर्भ
- Bridges, Douglas; Richman, Fred (1987). Varieties of Constructive Mathematics. Cambridge University Press. ISBN 978-0-521-31802-0.
- Hirst, Jeffry L. (2007). "Representations of reals in reverse mathematics". Bulletin of the Polish Academy of Sciences, Mathematics. 55 (4): 303–316. doi:10.4064/ba55-4-2.
- Lambov, Branimir (5 April 2015). "RealLib". GitHub.
- Minsky, Marvin (1967). "9. The Computable Real Numbers". Computation: Finite and Infinite Machines. Prentice-Hall. ISBN 0-13-165563-9. OCLC 0131655639.
- Rice, Henry Gordon (1954). "Recursive real numbers". Proceedings of the American Mathematical Society. 5 (5): 784–791. doi:10.1090/S0002-9939-1954-0063328-5. JSTOR 2031867.
- Specker, E. (1949). "Nicht konstruktiv beweisbare Sätze der Analysis" (PDF). Journal of Symbolic Logic. 14 (3): 145–158. doi:10.2307/2267043. JSTOR 2267043. Archived (PDF) from the original on 2018-07-21.
- Turing, A. M. (1936). "On Computable Numbers, with an Application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2 (published 1937). 42 (1): 230–65. doi:10.1112/plms/s2-42.1.230.
Turing, A. M. (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem: A correction". Proceedings of the London Mathematical Society. Series 2 (published 1937). 43 (6): 544–6. doi:10.1112/plms/s2-43.6.544. Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences. - van der Hoeven, Joris (2006). "Computations with effective real numbers". Theoretical Computer Science. 351 (1): 52–60. doi:10.1016/j.tcs.2005.09.060.
आगे की पढाई
- Aberth, Oliver (1968). "Analysis in the Computable Number Field". Journal of the Association for Computing Machinery. 15 (2): 276–299. doi:10.1145/321450.321460. S2CID 18135005. This paper describes the development of the calculus over the computable number field.
- Bishop, Errett; Bridges, Douglas (1985). Constructive Analysis. Springer. ISBN 0-387-15066-8.
- Stoltenberg-Hansen, V.; Tucker, J.V. (1999). "Computable Rings and Fields". In Griffor, E.R. (ed.). Handbook of Computability Theory. Elsevier. pp. 363–448. ISBN 978-0-08-053304-9.
- Weihrauch, Klaus (2000). Computable analysis. Texts in Theoretical Computer Science. Springer. ISBN 3-540-66817-9. §1.3.2 introduces the definition by nested sequences of intervals converging to the singleton real. Other representations are discussed in §4.1.
- Weihrauch, Klaus (1995). A simple introduction to computable analysis. Fernuniv., Fachbereich Informatik.