गणनीय संख्या

File:10,000 digits of pi - poster.svg

π की गणना एकपक्षीय परिशुद्धता के लिए की जा सकती है, जबकि लगभग प्रत्येक वास्तविक संख्या की गणना नहीं की जा सकती है।

गणित में, गणनीय संख्याएँ वास्तविक संख्याएँ होती हैं, जिनकी गणना परिमित, समाप्ति कलन विधि द्वारा किसी भी वांछित परिशुद्धता के अंदर की जा सकती है। उन्हें पुनरावर्ती संख्याओं, प्रभावी संख्याओं या गणनीय वास्तविक या पुनरावर्ती वास्तविक के रूप में भी जाना जाता है। गणनीय वास्तविक संख्या की अवधारणा एमिल बोरेल द्वारा 1912 में उस समय उपलब्ध अभिकलनीयता की अंतःप्रज्ञात्मक धारणा का उपयोग करके प्रस्तुत की गई थी।

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

उदाहरण के रूप में परिगणन युक्ति का उपयोग करके अनौपचारिक परिभाषा

निम्नलिखित में, मार्विन मिंस्की ने 1936 में एलन परिगणन द्वारा परिभाषित किए गए तरीकों के समान गणना की जाने वाली संख्याओं को परिभाषित किया; अर्थात, 0 और 1 के बीच दशमलव अंशों के रूप में व्याख्या किए गए अंकों के अनुक्रम के रूप में:

संगणनीय संख्या [है] जिसके लिए परिगणन युक्ति है, जो कि इसके प्रारंभिक टेप पर n दी गई है, उस संख्या के n वें अंक के साथ समाप्त होती है [इसके टेप पर एन्कोडेड]।

परिभाषा में मुख्य धारणाएं हैं (1) कि कुछ n प्रारंभ में निर्दिष्ट हैं, (2) किसी भी n के लिए गणना केवल परिमित संख्या के चरण होते है, जिसके बाद यंत्र वांछित निर्गम उत्पन्न करती है और समाप्त हो जाती है।

(2) का एक वैकल्पिक रूप - यंत्र क्रमिक रूप से अपने टेप पर सभी n अंकों को मुद्रित करती है, nवें को मुद्रित करने के बाद रुकने से मिंस्की के अवलोकन पर जोर देती है: (3) कि परिगणन युक्ति के उपयोग से, परिमित परिभाषा के रूप में यंत्र की अवस्‍था सारणी का उपयोग दशमलव अंकों की संभावित अनंत शृंखला को परिभाषित करने के लिए किया जा रहा है।

हालांकि यह आधुनिक परिभाषा नहीं है जिसके लिए किसी भी परिशुद्धता के अंदर केवल परिणाम की आवश्यकता होती है। उपरोक्त अनौपचारिक परिभाषा पूर्णांकन समस्या के अधीन है जिसे तालिका-निर्माता का विकल्प कहा जाता है जबकि आधुनिक परिभाषा नहीं है।

औपचारिक परिभाषा

एक वास्तविक संख्या a 'गणना योग्य' है यदि इसे किसी गणना योग्य फलन द्वारा अनुमानित किया जा सकता है $f:\mathbb {N} \to \mathbb {Z}$ निम्नलिखित तरीके से: किसी भी सकारात्मक पूर्णांक n को देखते हुए, फलन पूर्णांक f(n) उत्पन्न करता है जैसे कि:

${f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.$

इसी तरह की दो परिभाषाएँ हैं जो समकक्ष हैं:

• एक गणनीय फलन सम्मिलित है, जो किसी भी सकारात्मक तर्कसंगत त्रुटि के लिए बाध्य है $\varepsilon$, एक परिमेय संख्या r उत्पन्न करता है जैसे कि $|r-a|\leq \varepsilon .$
• परिमेय संख्याओं का गणनीय अनुक्रम है, $q_{i}$ में अभिसरण $a$ ऐसा है कि $|q_{i}-q_{i+1}|<2^{-i}\,$ प्रत्येक i के लिए

गणनीय डेडेकिन्ड-कट के माध्यम से गणनीय संख्याओं की अन्य समतुल्य परिभाषा है। एक 'गणनीय डेडेकिन्ड-कट' एक गणनीय फलन $D\;$ है जो परिमेय संख्या के साथ प्रदान किया जाता है $r$ निविष्ट प्रतिफल के रूप में $D(r)=\mathrm {true} \;$ या $D(r)=\mathrm {false} \;$, निम्नलिखित शर्तों को पूरा करना:

$\exists rD(r)=\mathrm {true} \;$

$\exists rD(r)=\mathrm {false} \;$

$(D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;$

$D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true} .\;$

क्रमादेश D द्वारा एक उदाहरण दिया गया है जो 3 के घनमूल को परिभाषित करता है। मान लीजिए $q>0\;$ के द्वारा परिभाषित किया गया है:

$p^{3}<3q^{3}\Rightarrow D(p/q)=\mathrm {true} \;$

$p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false} .\;$

एक वास्तविक संख्या की गणना तभी की जा सकती है जब और केवल तभी जब कोई गणनीय डेडेकिन्ड-कट D इसके अनुरूप है। फलन डी प्रत्येक गणना योग्य संख्या के लिए अद्वितीय है (हालांकि निश्चित रूप से दो अलग-अलग क्रमादेश समान फलन प्रदान कर सकते हैं)।

एक सम्मिश्र संख्या को गणनीय कहा जाता है यदि उसके वास्तविक और काल्पनिक भाग गणनीय हों।

गुण

गणनीय रूप से गणना योग्य नहीं

प्रत्येक परिगणन युक्ति परिभाषा के लिए गोडेल संख्या निर्दिष्ट करना गणनीय संख्याओं के अनुरूप प्राकृतिक संख्याओं का उपसमुच्चय $S$ उत्पन्न करता है और $S$ से गणना योग्य संख्याओं के लिए अन्य अनुमान की पहचान करता है। केवल गणनीय कई परिगणन युक्ति हैं, जो दर्शाती हैं कि गणना योग्य संख्याएँ उपगणनीय हैं। हालांकि इन गोडेल संख्याओं समुच्चय $S$, गणनीय रूप से गणना योग्य नहीं है (और परिणामस्वरूप, न तो $S$ के उपसमुच्चय हैं जिन्हें इसके संदर्भ में परिभाषित किया गया है)। ऐसा इसलिए है क्योंकि यह निर्धारित करने के लिए कोई एल्गोरिथ्म नहीं है कि कौन से गोडेल नंबर परिगणन मशीनों के अनुरूप हैं जो �