AFAIK, ट्यूरिंग गणना करने योग्य संख्याएं संख्याएं हैं जिनकी आई-थ इंडेक्स एक ट्यूरिंग मशीन द्वारा वापस की जा सकती है। तो एक गैर-गणना योग्य संख्या ऐसी संख्या की तरह होगी, जिसका दशमलव बिंदु तय किया जाता है यदि कुछ अन्य कार्यक्रम किसी अन्य इनपुट पर रोक लगाते हैं, लेकिन फिर फिर, पीआई एक असली संख्या है, जिसे टीएम द्वारा समझा नहीं जा सकता है। और इस प्रकार, गणना नहीं की जा सकती है? तो विचार का कौन सा स्कूल सही है?क्या पीआई एक ट्यूरिंग गणना योग्य संख्या है?
उत्तर
हां, π
गणना योग्य है। कम्प्यूटेबल की कुछ समकक्ष परिभाषाएं हैं, लेकिन यहां सबसे उपयोगी एक है जिसे आपने ऊपर दिया है: वास्तविक संख्या r
कंप्यूटेबल है यदि n
वें अंक को खोजने के लिए एल्गोरिदम मौजूद है। Here ऐसा एल्गोरिदम है।
आपका अंतिम तर्क ध्वनि नहीं है; आपने परिभाषा को भ्रमित कर दिया है "n
वें अंक" के साथ "सभी अंकों का आकलन कर सकते हैं"। उत्तरार्द्ध एक उपयोगी परिभाषा नहीं है: यह सभी irrationals और कई राशनों को भी नियम बनाता है!
एक दिलचस्प तथ्य यह है कि गणना करने योग्य संख्या वास्तव में गणना योग्य हैं, क्योंकि हम उन्हें उत्पन्न करने वाली ट्यूरिंग मशीनों की गोडेल-संख्या कर सकते हैं। इसलिए लगभग कोई वास्तविकता computable हैं।
मुझे लगता है कि आपका मतलब है कि लगभग सभी वास्तविक संख्याएं * नहीं * computable हैं, क्योंकि ट्यूरिंग मशीनों का सेट गणनीय है। –
@ लार्समैन: हां, ज़ाहिर है =) – katrielalex
इसे साफ़ करने के लिए धन्यवाद! चीयर्स! –
मुझे पूरा यकीन नहीं है कि "पीआई एक वास्तविक संख्या है, जिसे टीएम द्वारा समझा नहीं जा सकता"। हां, वास्तविक संख्याएं संख्यात्मक नहीं हैं, लेकिन मुझे नहीं लगता कि यह कैसे प्रभावित करता है कि पीआई गणना योग्य है या नहीं। '4' भी एक वास्तविक संख्या है, लेकिन इसका मतलब यह नहीं है कि यह गणना योग्य नहीं है। – sepp2k
उम, मेरा मतलब था, मैंने सोचा था कि पीआई की गणना करने के लिए यह असीमित लंबी ट्यूरिंग मशीन लेगा क्योंकि पीआई स्वयं असीम रूप से लंबा है। –
@ गौरव: उस तर्क से, क्या '1/3' की गणना करने के लिए एक असीमित लंबी ट्यूरिंग मशीन लेनी होगी, क्योंकि' 1/3 = 0.333333 ... 'असीम रूप से लंबी है? – katrielalex