गणनीय संख्या: Difference between revisions
No edit summary |
No edit summary |
||
(4 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
{{short description|Real number that can be computed within arbitrary precision}} | {{short description|Real number that can be computed within arbitrary precision}} | ||
[[File:10,000 digits of pi - poster.svg|thumb| π की गणना एकपक्षीय परिशुद्धता के लिए की जा सकती है, जबकि [[लगभग हर|लगभग प्रत्येक]] वास्तविक संख्या की गणना नहीं की जा सकती है।]][[गणित]] में, गणनीय संख्याएँ [[वास्तविक संख्या]]एँ होती हैं, जिनकी गणना परिमित, समाप्ति [[कलन विधि]] द्वारा किसी भी वांछित परिशुद्धता के अंदर की जा सकती है। उन्हें पुनरावर्ती संख्याओं, प्रभावी संख्याओं{{sfnp|van der Hoeven|2006}} या गणनीय वास्तविक या पुनरावर्ती वास्तविक के रूप में भी जाना जाता है।{{cn|reason=Give a source for each naming variant.|date=September 2019}} | [[File:10,000 digits of pi - poster.svg|thumb| π की गणना एकपक्षीय परिशुद्धता के लिए की जा सकती है, जबकि [[लगभग हर|लगभग प्रत्येक]] वास्तविक संख्या की गणना नहीं की जा सकती है।]][[गणित]] में, '''गणनीय संख्याएँ''' [[वास्तविक संख्या]]एँ होती हैं, जिनकी गणना परिमित, समाप्ति [[कलन विधि]] द्वारा किसी भी वांछित परिशुद्धता के अंदर की जा सकती है। उन्हें पुनरावर्ती संख्याओं, प्रभावी संख्याओं{{sfnp|van der Hoeven|2006}} या गणनीय वास्तविक या पुनरावर्ती वास्तविक के रूप में भी जाना जाता है।{{cn|reason=Give a source for each naming variant.|date=September 2019}} गणनीय वास्तविक संख्या की अवधारणा [[एमिल बोरेल]] द्वारा 1912 में उस समय उपलब्ध अभिकलनीयता की अंतःप्रज्ञात्मक धारणा का उपयोग करके प्रस्तुत की गई थी।<ref>P. Odifreddi, ''Classical Recursion Theory'' (1989), p.8. North-Holland, 0-444-87295-7</ref> | ||
एल्गोरिदम के औपचारिक प्रतिनिधित्व के रूप में μ-पुनरावर्ती फलन, [[ट्यूरिंग मशीनें|परिगणन (ट्यूरिंग) मशीनें]], या | एल्गोरिदम के औपचारिक प्रतिनिधित्व के रूप में μ-पुनरावर्ती फलन, [[ट्यूरिंग मशीनें|परिगणन (ट्यूरिंग) मशीनें]], या λ-गणना का उपयोग करके समतुल्य परिभाषाएं दी जा सकती हैं। गणनीय संख्याएं [[वास्तविक बंद क्षेत्र|वास्तविक संवृत क्षेत्र]] बनाती हैं और वास्तविक संख्याओं के स्थान पर कई गणितीय उद्देश्यों के लिए नहीं बल्कि अधिक के लिए उपयोग की जा सकती हैं।। | ||
== उदाहरण के रूप में | == उदाहरण के रूप में परिगणन युक्ति का उपयोग करके अनौपचारिक परिभाषा == | ||
निम्नलिखित में, [[मार्विन मिंस्की]] ने 1936 में [[एलन ट्यूरिंग|एलन परिगणन]] द्वारा परिभाषित किए गए तरीकों के समान गणना की जाने वाली संख्याओं को परिभाषित किया;{{sfnp|Turing|1936}} अर्थात, 0 और 1 के बीच दशमलव अंशों के रूप में व्याख्या किए गए अंकों के अनुक्रम के रूप में:{{sfnp|Minsky|1967}} | निम्नलिखित में, [[मार्विन मिंस्की]] ने 1936 में [[एलन ट्यूरिंग|एलन परिगणन]] द्वारा परिभाषित किए गए तरीकों के समान गणना की जाने वाली संख्याओं को परिभाषित किया;{{sfnp|Turing|1936}} अर्थात, 0 और 1 के बीच दशमलव अंशों के रूप में व्याख्या किए गए अंकों के अनुक्रम के रूप में:{{sfnp|Minsky|1967}} | ||
{{quote|text=संगणनीय संख्या [है] जिसके लिए परिगणन युक्ति है, जो कि इसके प्रारंभिक टेप पर ''n'' दी गई है, उस संख्या के ''n'' वें अंक के साथ समाप्त होती है [इसके टेप पर एन्कोडेड]।}} | {{quote|text=संगणनीय संख्या [है] जिसके लिए परिगणन युक्ति है, जो कि इसके प्रारंभिक टेप पर ''n'' दी गई है, उस संख्या के ''n'' वें अंक के साथ समाप्त होती है [इसके टेप पर एन्कोडेड]।}} | ||
परिभाषा में मुख्य धारणाएं हैं (1) कि कुछ n प्रारंभ में निर्दिष्ट हैं, (2) किसी भी n के लिए गणना केवल परिमित संख्या के चरण होते है, जिसके बाद यंत्र वांछित | परिभाषा में मुख्य धारणाएं हैं (1) कि कुछ n प्रारंभ में निर्दिष्ट हैं, (2) किसी भी n के लिए गणना केवल परिमित संख्या के चरण होते है, जिसके बाद यंत्र वांछित निर्गम उत्पन्न करती है और समाप्त हो जाती है। | ||
(2) का एक वैकल्पिक रूप - यंत्र क्रमिक रूप से अपने टेप पर सभी n अंकों को मुद्रित करती है, nवें को मुद्रित करने के बाद रुकने से मिंस्की के अवलोकन पर जोर देती है: (3) कि | (2) का एक वैकल्पिक रूप - यंत्र क्रमिक रूप से अपने टेप पर सभी n अंकों को मुद्रित करती है, nवें को मुद्रित करने के बाद रुकने से मिंस्की के अवलोकन पर जोर देती है: (3) कि परिगणन युक्ति के उपयोग से, परिमित परिभाषा के रूप में यंत्र की अवस्था सारणी का उपयोग दशमलव अंकों की संभावित अनंत शृंखला को परिभाषित करने के लिए किया जा रहा है। | ||
हालांकि यह आधुनिक परिभाषा नहीं है जिसके लिए किसी भी परिशुद्धता के अंदर केवल परिणाम की आवश्यकता होती है। उपरोक्त अनौपचारिक परिभाषा पूर्णांकन समस्या के अधीन है जिसे तालिका-निर्माता का विकल्प कहा जाता है जबकि आधुनिक परिभाषा नहीं है। | हालांकि यह आधुनिक परिभाषा नहीं है जिसके लिए किसी भी परिशुद्धता के अंदर केवल परिणाम की आवश्यकता होती है। उपरोक्त अनौपचारिक परिभाषा पूर्णांकन समस्या के अधीन है जिसे तालिका-निर्माता का विकल्प कहा जाता है जबकि आधुनिक परिभाषा नहीं है। | ||
Line 22: | Line 22: | ||
*परिमेय संख्याओं का गणनीय अनुक्रम है, <math>q_i</math> में अभिसरण <math>a</math> ऐसा है कि <math>|q_i - q_{i+1}| < 2^{-i}\,</math> प्रत्येक i के लिए | *परिमेय संख्याओं का गणनीय अनुक्रम है, <math>q_i</math> में अभिसरण <math>a</math> ऐसा है कि <math>|q_i - q_{i+1}| < 2^{-i}\,</math> प्रत्येक i के लिए | ||
गणनीय डेडेकिन्ड-कट के माध्यम से गणनीय संख्याओं की अन्य समतुल्य परिभाषा है। एक 'गणनीय [[डेडेकाइंड कट]]' एक गणनीय फलन | गणनीय डेडेकिन्ड-कट के माध्यम से गणनीय संख्याओं की अन्य समतुल्य परिभाषा है। एक 'गणनीय [[डेडेकाइंड कट|डेडेकिन्ड-कट]]' एक गणनीय फलन <math>D\;</math> है जो परिमेय संख्या के साथ प्रदान किया जाता है <math>r</math> निविष्ट प्रतिफल के रूप में <math>D(r)=\mathrm{true}\;</math> या <math>D(r)=\mathrm{false}\;</math>, निम्नलिखित शर्तों को पूरा करना: | ||
:<math>\exists r D(r)=\mathrm{true}\;</math> | :<math>\exists r D(r)=\mathrm{true}\;</math> | ||
:<math>\exists r D(r)=\mathrm{false}\;</math> | :<math>\exists r D(r)=\mathrm{false}\;</math> | ||
Line 30: | Line 30: | ||
:<math>p^3<3 q^3 \Rightarrow D(p/q)=\mathrm{true}\;</math> | :<math>p^3<3 q^3 \Rightarrow D(p/q)=\mathrm{true}\;</math> | ||
:<math>p^3>3 q^3 \Rightarrow D(p/q)=\mathrm{false}.\;</math> | :<math>p^3>3 q^3 \Rightarrow D(p/q)=\mathrm{false}.\;</math> | ||
एक वास्तविक संख्या की गणना तभी की जा सकती है जब और केवल तभी जब कोई गणनीय डेडेकिन्ड-कट D इसके अनुरूप है। फलन डी प्रत्येक गणना योग्य संख्या के लिए अद्वितीय है (हालांकि निश्चित रूप से दो अलग-अलग | एक वास्तविक संख्या की गणना तभी की जा सकती है जब और केवल तभी जब कोई गणनीय डेडेकिन्ड-कट D इसके अनुरूप है। फलन डी प्रत्येक गणना योग्य संख्या के लिए अद्वितीय है (हालांकि निश्चित रूप से दो अलग-अलग क्रमादेश समान फलन प्रदान कर सकते हैं)। | ||
एक सम्मिश्र संख्या को गणनीय कहा जाता है यदि उसके वास्तविक और काल्पनिक भाग गणनीय हों। | एक सम्मिश्र संख्या को गणनीय कहा जाता है यदि उसके वास्तविक और काल्पनिक भाग गणनीय हों। | ||
Line 37: | Line 37: | ||
=== गणनीय रूप से गणना योग्य नहीं === | === गणनीय रूप से गणना योग्य नहीं === | ||
प्रत्येक | प्रत्येक परिगणन युक्ति परिभाषा के लिए गोडेल संख्या निर्दिष्ट करना गणनीय संख्याओं के अनुरूप [[प्राकृतिक संख्या]]ओं का उपसमुच्चय <math>S</math> उत्पन्न करता है और <math>S</math> से गणना योग्य संख्याओं के लिए अन्य अनुमान की पहचान करता है। केवल गणनीय कई परिगणन युक्ति हैं, जो दर्शाती हैं कि गणना योग्य संख्याएँ [[उपगणनीय]] हैं। हालांकि इन गोडेल संख्याओं समुच्चय <math>S</math>, गणनीय रूप से [[गणना योग्य]] नहीं है (और परिणामस्वरूप, न तो <math>S</math> के उपसमुच्चय हैं जिन्हें इसके संदर्भ में परिभाषित किया गया है)। ऐसा इसलिए है क्योंकि यह निर्धारित करने के लिए कोई एल्गोरिथ्म नहीं है कि कौन से गोडेल नंबर परिगणन मशीनों के अनुरूप हैं जो गणना योग्य वास्तविक उत्पादन करते हैं। गणना योग्य वास्तविक का उत्पादन करने के लिए, परिगणन युक्ति को कुल फलन की गणना करनी चाहिए, लेकिन संगत [[निर्णय समस्या|परिणाम समस्या]] [[ट्यूरिंग डिग्री|परिगणन]] श्रेणी 0 में है। परिणामस्वरूप, प्राकृतिक संख्याओं से गणनीय वास्तविक तक कोई विशेषण गणनीय फलन नहीं है, और कैंटर के विकर्ण तर्क का उपयोग रचनात्मक रूप से (गणित) उनमें से कई को प्रदर्शित करने के लिए नहीं किया जा सकता है। | ||
जबकि वास्तविक संख्याओं का समुच्चय [[बेशुमार|असंख्य]] है, गणनीय संख्याओं का समूह श्रेणीबद्ध रूप से गणना योग्य है और इस प्रकार [[लगभग सभी]] वास्तविक संख्याएँ गणनीय नहीं हैं। यहाँ, किसी भी गणना योग्य संख्या के लिए <math>x,</math> | जबकि वास्तविक संख्याओं का समुच्चय [[बेशुमार|असंख्य]] है, गणनीय संख्याओं का समूह श्रेणीबद्ध रूप से गणना योग्य है और इस प्रकार [[लगभग सभी]] वास्तविक संख्याएँ गणनीय नहीं हैं। यहाँ, किसी भी गणना योग्य संख्या के लिए <math>x,</math> क्रमित सिद्धांत प्रदान करता है कि इसमें एक न्यूनतम तत्व <math>S</math> है जो <math>x</math> के अनुरूप है, और इसलिए न्यूनतम तत्वों से युक्त एक उपसमुच्चय सम्मिलित है, जिस पर मानचित्र द्विअंत:क्षेपण है। इस आक्षेप का व्युत्क्रम गणनीय संख्याओं की प्राकृतिक संख्याओं में विशेषण फलन है, यह प्रमाणित करता है कि वे गणनीय हैं। लेकिन, पुनः, यह उपसमुच्चय गणनीय नहीं है, यद्यपि गणनीय वास्तविक स्वयं क्रमित किया गया हो। | ||
=== क्षेत्र के रूप में गुण === | === क्षेत्र के रूप में गुण === | ||
गणनीय संख्याओं पर अंकगणितीय संक्रियाएँ स्वयं इस अर्थ में गणनीय हैं कि जब भी वास्तविक संख्याएँ a और b गणनीय होती हैं तो निम्नलिखित वास्तविक संख्याएँ भी गणनीय होती हैं: a + b, a - b, ab, और a/b यदि b अशून्य है। ये संक्रिया वास्तव में समान रूप से गणनीय हैं; उदाहरण के लिए, | गणनीय संख्याओं पर अंकगणितीय संक्रियाएँ स्वयं इस अर्थ में गणनीय हैं कि जब भी वास्तविक संख्याएँ a और b गणनीय होती हैं तो निम्नलिखित वास्तविक संख्याएँ भी गणनीय होती हैं: a + b, a - b, ab, और a/b यदि b अशून्य है। ये संक्रिया वास्तव में समान रूप से गणनीय हैं; उदाहरण के लिए, परिगणन युक्ति है जो निविष्ट (''A'', ''B'', <math>\epsilon</math>) निर्गम r का उत्पादन करता है, जहां ''A'' अनुमानित परिगणन युक्ति का विवरण है, ''a'', ''B'' अनुमानित परिगणन युक्ति का विवरण है, और r ''a''+''b'' का <math>\epsilon</math> सन्निकटन है। | ||
तथ्य यह है कि गणनीय वास्तविक संख्याएँ एक [[क्षेत्र (गणित)]] को पहली बार 1954 में [[हेनरी गॉर्डन राइस]] द्वारा सिद्ध किया गया था।{{sfnp|Rice|1954}} | तथ्य यह है कि गणनीय वास्तविक संख्याएँ एक [[क्षेत्र (गणित)]] को पहली बार 1954 में [[हेनरी गॉर्डन राइस]] द्वारा सिद्ध किया गया था।{{sfnp|Rice|1954}} | ||
Line 49: | Line 49: | ||
=== क्रम की गैर-अभिकलनीयता === | === क्रम की गैर-अभिकलनीयता === | ||
गणनीय संख्याओं पर क्रम संबंध गणनीय नहीं है। बता दें कि A संख्या का अनुमान लगाने वाली | गणनीय संख्याओं पर क्रम संबंध गणनीय नहीं है। बता दें कि 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>, जो एक प्रकार की वास्तविक संख्या है जो रुकने की समस्या के बराबर है। | ||
ये दोनों उदाहरण वास्तव में प्रत्येक [[यूनिवर्सल ट्यूरिंग मशीन| | ये दोनों उदाहरण वास्तव में प्रत्येक [[यूनिवर्सल ट्यूरिंग मशीन|सार्वभौमिक परिगणन युक्ति]] के लिए निश्चित, अगणनीय संख्याओं के अनंत समुच्चय को परिभाषित करते हैं। अतः वास्तविक संख्या की गणना की जा सकती है यदि और केवल तभी जब प्राकृतिक संख्याओं का वह समुच्चय (जब बाइनरी में लिखा जाता है और अन्य विशिष्ट फलन के रूप में देखा जाता है) गणना योग्य होता है। | ||
गणनीय वास्तविक संख्याओं का समुच्चय (साथ ही प्रत्येक गणनीय, सघन रूप से बिना सिरों के गणनीय वास्तविकों का उपसमुच्चय) | गणनीय वास्तविक संख्याओं का समुच्चय (साथ ही प्रत्येक गणनीय, सघन रूप से बिना सिरों के गणनीय वास्तविकों का उपसमुच्चय) परिमेय संख्याओं के समुच्चय के लिए [[आदेश-समरूपी|क्रम-तुल्याकारी]] है। | ||
== | == अंकों की शृंखला और कैंटर और बेयर-समष्टि == | ||
परिगणन के मूल पेपर में गणना योग्य संख्याओं को निम्नानुसार परिभाषित किया गया है: | परिगणन के मूल पेपर में गणना योग्य संख्याओं को निम्नानुसार परिभाषित किया गया है: | ||
{{quote|text=वास्तविक संख्या की गणना की जा सकती है यदि इसके अंक अनुक्रम को किसी कलन विधि या परिगणन युक्ति द्वारा निर्मित किया जा सकता है। एल्गोरिदम | {{quote|text=वास्तविक संख्या की गणना की जा सकती है यदि इसके अंक अनुक्रम को किसी कलन विधि या परिगणन युक्ति द्वारा निर्मित किया जा सकता है। एल्गोरिदम निर्दिष्ट के रूप में पूर्णांक <math>n \ge 1</math>लेता है और निर्गत के रूप में वास्तविक संख्या के दशमलव विस्तार के <math>n</math>-वें अंक का उत्पादन करता है।}} | ||
(a का दशमलव विस्तार केवल दशमलव बिंदु के बाद वाले अंकों को संदर्भित करता है।) | (a का दशमलव विस्तार केवल दशमलव बिंदु के बाद वाले अंकों को संदर्भित करता है।) | ||
परिगणन जानते थे कि यह परिभाषा | परिगणन जानते थे कि यह परिभाषा ऊपर दी गई <math>\epsilon</math>-सन्निकटन परिभाषा ऊपर दी गई है परिभाषा के समतुल्य है। तर्क इस प्रकार आगे बढ़ता है: यदि कोई संख्या परिगणन अर्थ में गणना योग्य है, तो यह <math>\epsilon</math> अर्थ मे भी गणना योग्य है: यदि <math>n > \log_{10} (1/\epsilon)</math>, तो a के लिए दशमलव विस्तार के पहले n अंक a प्रदान करने के लिए <math>\epsilon</math> का सन्निकटन है। प्रतिलोम के लिए, हम एक <math>\epsilon</math> गणना योग्य वास्तविक संख्या a चयन करते है और दशमलव बिंदु के बाद nवें अंक तक निश्चित रूप से परिशुद्ध सन्निकटन उत्पन्न करते हैं। यह सदैव एक के बराबर a दशमलव विस्तार उत्पन्न करता है लेकिन यह 9 के अनंत अनुक्रम में अनुचित रूप से समाप्त हो सकता है, इस स्थिति में इसका परिमित (और इस प्रकार गणना योग्य) उपयुक्त दशमलव विस्तार होना चाहिए। | ||
जब तक वास्तविक संख्याओं के कुछ सामयिक गुण प्रासंगिक नहीं होते हैं, तब तक के | जब तक वास्तविक संख्याओं के कुछ सामयिक गुण प्रासंगिक नहीं होते हैं, तब तक<math>[0,1]</math> में वास्तविक संख्या के स्थान पर <math>2^{\omega}</math> (कुल 0,1 मूल्यवान फलन) के तत्वों से विभाजन करने के लिए प्रायः अधिक सुविधाजनक होता है। <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> सन्निकटन मे प्रभावी रूप से पहचान करना असंभव है। हिस्ट ने दर्शाया है कि कोई एल्गोरिदम नहीं है जो निविष्ट के रूप में परिगणन युक्ति का विवरण लेता है जो गणना योग्य संख्या A के लिए <math>\epsilon</math> सन्निकटन उत्पादन करता है, और निर्गम के रूप में परिगणन युक्ति के रूप मे उत्पन्न करता है जो परिगणन की परिभाषा के अर्थ में a के अंकों की गणना करता है।{{sfnp|Hirst|2007}} इसी प्रकार, इसका अर्थ है कि गणना योग्य वास्तविक पर अंकगणितीय संक्रिया दशमलव संख्याओं को जोड़ते समय उनके दशमलव निरूपण पर प्रभावी नहीं होते हैं। एक अंक का उत्पादन करने के लिए, यह निर्धारित करने के लिए कि क्या वर्तमान स्थिति पर कोई कैरी (हासिल) है, अव्यवस्थित रूप से दाईं ओर देखना आवश्यक हो सकता है। एकरूपता की यह कमी एक कारण है कि गणना योग्य संख्याओं की समकालीन परिभाषा दशमलव विस्तार के स्थान पर <math>\epsilon</math> सन्निकटन का उपयोग करती है। | ||
हालाँकि, एक [[संगणनीयता सिद्धांत|अभिकलनीयता सिद्धांत]] या [[माप सिद्धांत]] के दृष्टिकोण से, दो संरचनाएँ <math>2^{\omega}</math> और <math>[0,1]</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>\omega^{\omega}</math> के तत्वों को कभी-कभी वास्तविक भी कहा जाता है और यद्यपि <math>\mathbb{R}</math> इसमें [[होमियोमोर्फिज्म|समरूपी]] छवि युक्त <math>\omega^{\omega}</math> स्थानीय रूप [[स्थानीय रूप से कॉम्पैक्ट स्थान|स्थानीय रूप से सुसम्बद्ध]] भी नहीं है (पूरी तरह से वियोजित होने के अतिरिक्त)। इससे गणनीय गुणों में वास्तविक अंतर होता है। उदाहरण के लिए <math>x \in \mathbb{R}</math> शर्तों को पूरा करने वाले <math>\forall(n \in \omega)\phi(x,n)</math> के साथ <math>\phi(x,n)</math> परिमाणक मुक्त, अद्वितीय <math>x \in \omega^{\omega}</math> होने पर गणना योग्य होना चाहिए, सार्वभौमिक सूत्र को पूरा करने से अति-अंकगणित [[हाइपरअरिथमेटिक पदानुक्रम|पदानुक्रम]] में अव्यवस्थित रूप से उच्च स्थिति हो सकती है। | |||
== | == तत्व के स्थान पर प्रयोग करें == | ||
गणना योग्य संख्याओं में विशिष्ट वास्तविक संख्याएँ सम्मिलित होती हैं जो व्यवहार में दिखाई देती हैं, जिसमें सभी वास्तविक [[बीजगणितीय संख्या]]एँ, साथ ही | गणना योग्य संख्याओं में विशिष्ट वास्तविक संख्याएँ सम्मिलित होती हैं जो व्यवहार में दिखाई देती हैं, जिसमें सभी वास्तविक [[बीजगणितीय संख्या]]एँ, साथ ही e, π, और कई अन्य [[पारलौकिक संख्या]]एँ सम्मिलित हैं। यद्यपि गणनीय वास्तविक उन वास्तविकताओं को समाप्त कर देते हैं जिनकी हम गणना या अनुमान लगा सकते हैं, यह धारणा कि सभी वास्तविक गणना योग्य हैं, वास्तविक संख्याओं के बारे में काफी भिन्न निष्कर्ष निकालते हैं। स्वाभाविक रूप से यह प्रश्न होता है कि क्या सभी गणित के लिए वास्तविक के पूर्ण समुच्चय का समाधान करना और गणना योग्य संख्याओं का उपयोग करना संभव है। यह विचार एक रचनावाद (गणित) के दृष्टिकोण से आकर्षक है, और एरेट बिशप और फ्रेड रिचमैन द्वारा रचनात्मक गणित के रूसी स्कूल कहे जाने के कारण इसका अनुसरण किया गया है।{{cn|date=October 2021}} <ref>{{Citation | ||
| contribution = Russian School of Constructive Mathematics | | contribution = Russian School of Constructive Mathematics | ||
| title = Constructive Mathematics | | title = Constructive Mathematics | ||
Line 91: | Line 90: | ||
| publisher = Metaphysics Research Lab, Stanford University | | publisher = Metaphysics Research Lab, Stanford University | ||
| date = 2022}}</ref> | | date = 2022}}</ref> | ||
गणना योग्य संख्याओं पर वास्तव में विश्लेषण विकसित करने के लिए, कुछ सावधानी रखनी चाहिए। उदाहरण के लिए, यदि कोई अनुक्रम की उत्कृष्ट परिभाषा का उपयोग करता है, तो गणना योग्य संख्याओं का समुच्चय सीमित अनुक्रम के सर्वोच्च को लेने के मूल संचालन के अंतर्गत बंद नहीं होता है (उदाहरण के लिए, स्पेकर अनुक्रम पर विचार करें, ऊपर अनुभाग देखें)। इस कठिनाई को केवल उन अनुक्रमों पर विचार करके संबोधित किया जाता है जिनमें अभिसरण का एक गणनीय मापांक होता है। परिणामी गणितीय सिद्धांत को गणनीय विश्लेषण कहा जाता है। | |||
सन्निकटन की गणना करने वाले | |||
== परिशुद्ध अंकगणित का कार्यान्वयन == | |||
सन्निकटन की गणना करने वाले क्रमानुदेश के रूप में वास्तविक संख्याओं का प्रतिनिधित्व करने वाले कंप्यूटर पैकेजों को <nowiki>''परिशुद्ध अंकगणित''</nowiki> नाम के अंतर्गत 1985 के प्रारंभ में प्रस्तावित किया गया है।<ref>{{cite journal |last1=Boehm |first1=Hans-J. |last2=Cartwright |first2=Robert |last3=Riggle |first3=Mark |last4=O'Donnell |first4=Michael J. |title=Exact real arithmetic: a case study in higher order programming |journal=Proceedings of the 1986 ACM conference on LISP and functional programming |date=8 August 1986 |pages=162–173 |doi=10.1145/319838.319860 |url=http://fricas-wiki.math.uni.wroc.pl/public/refs/exact-real-p162-boehm.pdf |archive-url=https://web.archive.org/web/20200924021221/http://fricas-wiki.math.uni.wroc.pl/public/refs/exact-real-p162-boehm.pdf |archive-date=2020-09-24 |url-status=live}}</ref> आधुनिक उदाहरणों में सीओआरएन लाइब्रेरी (Coq),<ref>{{cite journal |last1=O’Connor |first1=Russell |title=Certified Exact Transcendental Real Number Computation in Coq |journal=Theorem Proving in Higher Order Logics |date=2008 |pages=246–261 |doi=10.1007/978-3-540-71067-7_21 |url=https://arxiv.org/pdf/0805.2438.pdf |archive-url=https://web.archive.org/web/20220324193343/https://arxiv.org/pdf/0805.2438.pdf |archive-date=2022-03-24 |url-status=live}}</ref> और रीयललिब पैकेज (सी ++) सम्मिलित है।{{sfnp|Lambov|2015}} फलन की संबंधित रेखा वास्तविक रैम क्रमादेश लेने और पर्याप्त परिशुद्धता के तर्कसंगत या चलबिंदु संख्या के साथ चलाने पर आधारित है, जैसे आईआरआरएएम पैकेज।<ref>{{cite journal |last1=Gowland |first1=Paul |last2=Lester |first2=David |title=A Survey of Exact Arithmetic Implementations |journal=Computability and Complexity in Analysis |date=2001 |pages=30–47 |doi=10.1007/3-540-45335-0_3 |url=https://link.springer.com/content/pdf/10.1007%2F3-540-45335-0_3.pdf |archive-url=https://web.archive.org/web/20220324193302/https://link.springer.com/content/pdf/10.1007%2F3-540-45335-0_3.pdf |archive-date=2022-03-24 |url-status=live |publisher=Springer |language=en}}</ref> | |||
Line 131: | Line 132: | ||
{{Number systems}} | {{Number systems}} | ||
{{DEFAULTSORT:Computable Number}} | {{DEFAULTSORT:Computable Number}} | ||
[[Category: | [[Category:All articles with unsourced statements|Computable Number]] | ||
[[Category:Created On 03/02/2023]] | [[Category:Articles with unsourced statements from October 2021|Computable Number]] | ||
[[Category:Articles with unsourced statements from September 2019|Computable Number]] | |||
[[Category:CS1 English-language sources (en)]] | |||
[[Category:Collapse templates|Computable Number]] | |||
[[Category:Created On 03/02/2023|Computable Number]] | |||
[[Category:Lua-based templates|Computable Number]] | |||
[[Category:Machine Translated Page|Computable Number]] | |||
[[Category:Navigational boxes| ]] | |||
[[Category:Navigational boxes without horizontal lists|Computable Number]] | |||
[[Category:Pages with math errors|Computable Number]] | |||
[[Category:Pages with math render errors|Computable Number]] | |||
[[Category:Pages with script errors|Computable Number]] | |||
[[Category:Short description with empty Wikidata description|Computable Number]] | |||
[[Category:Sidebars with styles needing conversion|Computable Number]] | |||
[[Category:Template documentation pages|Documentation/doc]] | |||
[[Category:Templates Vigyan Ready|Computable Number]] | |||
[[Category:Templates generating microformats|Computable Number]] | |||
[[Category:Templates that add a tracking category|Computable Number]] | |||
[[Category:Templates that are not mobile friendly|Computable Number]] | |||
[[Category:Templates that generate short descriptions|Computable Number]] | |||
[[Category:Templates using TemplateData|Computable Number]] | |||
[[Category:Wikipedia metatemplates|Computable Number]] | |||
[[Category:संगणना का सिद्धांत|Computable Number]] | |||
[[Category:संगणनीयता सिद्धांत|Computable Number]] |
Latest revision as of 09:09, 12 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वें अंक तक निश्चित रूप से परिशुद्ध सन्निकटन उत्पन्न करते हैं। यह सदैव एक के बराबर a दशमलव विस्तार उत्पन्न करता है लेकिन यह 9 के अनंत अनुक्रम में अनुचित रूप से समाप्त हो सकता है, इस स्थिति में इसका परिमित (और इस प्रकार गणना योग्य) उपयुक्त दशमलव विस्तार होना चाहिए।
जब तक वास्तविक संख्याओं के कुछ सामयिक गुण प्रासंगिक नहीं होते हैं, तब तक में वास्तविक संख्या के स्थान पर (कुल 0,1 मूल्यवान फलन) के तत्वों से विभाजन करने के लिए प्रायः अधिक सुविधाजनक होता है। के इकाई बाइनरी दशमलव विस्तार के साथ पहचाना जा सकता है, लेकिन दशमलव विस्तार के बाद से और एक ही वास्तविक संख्या, अंतराल को निरूपित करें, केवल के उपसमुच्चय के साथ पहचाने जाने वाले सभी 1 में समाप्त नहीं होने के कारण (और उपसमुच्चय सांस्थिति के अंतर्गत समरूपी रूप से) हो सकता है।
ध्यान दें कि दशमलव विस्तार की इस गुण का तात्पर्य है कि दशमलव विस्तार के संदर्भ में परिभाषित गणनीय वास्तविक संख्याओं और सन्निकटन मे प्रभावी रूप से पहचान करना असंभव है। हिस्ट ने दर्शाया है कि कोई एल्गोरिदम नहीं है जो निविष्ट के रूप में परिगणन युक्ति का विवरण लेता है जो गणना योग्य संख्या A के लिए सन्निकटन उत्पादन करता है, और निर्गम के रूप में परिगणन युक्ति के रूप मे उत्पन्न करता है जो परिगणन की परिभाषा के अर्थ में a के अंकों की गणना करता है।[8] इसी प्रकार, इसका अर्थ है कि गणना योग्य वास्तविक पर अंकगणितीय संक्रिया दशमलव संख्याओं को जोड़ते समय उनके दशमलव निरूपण पर प्रभावी नहीं होते हैं। एक अंक का उत्पादन करने के लिए, यह निर्धारित करने के लिए कि क्या वर्तमान स्थिति पर कोई कैरी (हासिल) है, अव्यवस्थित रूप से दाईं ओर देखना आवश्यक हो सकता है। एकरूपता की यह कमी एक कारण है कि गणना योग्य संख्याओं की समकालीन परिभाषा दशमलव विस्तार के स्थान पर सन्निकटन का उपयोग करती है।
हालाँकि, एक अभिकलनीयता सिद्धांत या माप सिद्धांत के दृष्टिकोण से, दो संरचनाएँ और अनिवार्य रूप से समान हैं। इस प्रकार, अभिकलनीयता सिद्धांतकार प्रायः इकाइयों को वास्तविक के रूप में संदर्भित करते हैं। जबकि पूरी तरह से वियोजित हो गया है, कक्षाओं या यादृच्छिकता के बारे मे प्रश्नों के लिए मे कार्य करना आसान होता है।
के तत्वों को कभी-कभी वास्तविक भी कहा जाता है और यद्यपि इसमें समरूपी छवि युक्त स्थानीय रूप स्थानीय रूप से सुसम्बद्ध भी नहीं है (पूरी तरह से वियोजित होने के अतिरिक्त)। इससे गणनीय गुणों में वास्तविक अंतर होता है। उदाहरण के लिए शर्तों को पूरा करने वाले के साथ परिमाणक मुक्त, अद्वितीय होने पर गणना योग्य होना चाहिए, सार्वभौमिक सूत्र को पूरा करने से अति-अंकगणित पदानुक्रम में अव्यवस्थित रूप से उच्च स्थिति हो सकती है।
तत्व के स्थान पर प्रयोग करें
गणना योग्य संख्याओं में विशिष्ट वास्तविक संख्याएँ सम्मिलित होती हैं जो व्यवहार में दिखाई देती हैं, जिसमें सभी वास्तविक बीजगणितीय संख्याएँ, साथ ही e, π, और कई अन्य पारलौकिक संख्याएँ सम्मिलित हैं। यद्यपि गणनीय वास्तविक उन वास्तविकताओं को समाप्त कर देते हैं जिनकी हम गणना या अनुमान लगा सकते हैं, यह धारणा कि सभी वास्तविक गणना योग्य हैं, वास्तविक संख्याओं के बारे में काफी भिन्न निष्कर्ष निकालते हैं। स्वाभाविक रूप से यह प्रश्न होता है कि क्या सभी गणित के लिए वास्तविक के पूर्ण समुच्चय का समाधान करना और गणना योग्य संख्याओं का उपयोग करना संभव है। यह विचार एक रचनावाद (गणित) के दृष्टिकोण से आकर्षक है, और एरेट बिशप और फ्रेड रिचमैन द्वारा रचनात्मक गणित के रूसी स्कूल कहे जाने के कारण इसका अनुसरण किया गया है।[citation needed] [9]
गणना योग्य संख्याओं पर वास्तव में विश्लेषण विकसित करने के लिए, कुछ सावधानी रखनी चाहिए। उदाहरण के लिए, यदि कोई अनुक्रम की उत्कृष्ट परिभाषा का उपयोग करता है, तो गणना योग्य संख्याओं का समुच्चय सीमित अनुक्रम के सर्वोच्च को लेने के मूल संचालन के अंतर्गत बंद नहीं होता है (उदाहरण के लिए, स्पेकर अनुक्रम पर विचार करें, ऊपर अनुभाग देखें)। इस कठिनाई को केवल उन अनुक्रमों पर विचार करके संबोधित किया जाता है जिनमें अभिसरण का एक गणनीय मापांक होता है। परिणामी गणितीय सिद्धांत को गणनीय विश्लेषण कहा जाता है।
परिशुद्ध अंकगणित का कार्यान्वयन
सन्निकटन की गणना करने वाले क्रमानुदेश के रूप में वास्तविक संख्याओं का प्रतिनिधित्व करने वाले कंप्यूटर पैकेजों को ''परिशुद्ध अंकगणित'' नाम के अंतर्गत 1985 के प्रारंभ में प्रस्तावित किया गया है।[10] आधुनिक उदाहरणों में सीओआरएन लाइब्रेरी (Coq),[11] और रीयललिब पैकेज (सी ++) सम्मिलित है।[12] फलन की संबंधित रेखा वास्तविक रैम क्रमादेश लेने और पर्याप्त परिशुद्धता के तर्कसंगत या चलबिंदु संख्या के साथ चलाने पर आधारित है, जैसे आईआरआरएएम पैकेज।[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.