संगणनीय कार्य

रिकर्सन सिद्धांत में गणना योग्य कार्य अध्ययन की मूल वस्तुएं हैं। कंप्यूटेबल फ़ंक्शंस एल्गोरिदम की सहज धारणा का औपचारिक एनालॉग हैं, इस अर्थ में कि एक फ़ंक्शन गणना योग्य है यदि कोई एल्गोरिदम मौजूद है जो फ़ंक्शन का काम कर सकता है, यानी फ़ंक्शन डोमेन का इनपुट दिया गया है तो यह संबंधित आउटपुट वापस कर सकता है। कम्प्यूटेशनल फ़ंक्शंस का उपयोग गणना के किसी ठोस मॉडल जैसे ट्यूरिंग मशीन या रजिस्टर मशीनों का संदर्भ दिए बिना कम्प्यूटेबिलिटी पर चर्चा करने के लिए किया जाता है। हालाँकि, किसी भी परिभाषा में गणना के कुछ विशिष्ट मॉडल का संदर्भ होना चाहिए, लेकिन सभी मान्य परिभाषाएँ समान वर्ग के कार्य उत्पन्न करती हैं। कंप्यूटेबिलिटी के विशेष गणना का मॉडल फ़ंक्शंस के सेट को जन्म देते हैं वे ट्यूरिंग-कम्प्यूटेबल फ़ंक्शन और सामान्य पुनरावर्ती फ़ंक्शंस हैं।

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

चर्च-ट्यूरिंग थीसिस के अनुसार, गणना योग्य कार्य वास्तव में वे कार्य हैं जिनकी गणना असीमित मात्रा में समय और भंडारण स्थान दिए जाने पर यांत्रिक गणना उपकरण का उपयोग करके की जा सकती है। समान रूप से, यह थीसिस बताती है कि एक फ़ंक्शन गणना योग्य है यदि और केवल तभी जब उसमें एक एल्गोरिदम हो। इस अर्थ में एक कलन विधि को उन चरणों के अनुक्रम के रूप में समझा जाता है जिनका पालन असीमित समय और कलम और कागज की असीमित आपूर्ति वाला व्यक्ति कर सकता है।

ब्लम सिद्धांतों का उपयोग गणना योग्य कार्यों के सेट पर एक अमूर्त कम्प्यूटेशनल जटिलता सिद्धांत को परिभाषित करने के लिए किया जा सकता है। कम्प्यूटेशनल जटिलता सिद्धांत में, एक गणना योग्य फ़ंक्शन की जटिलता को निर्धारित करने की समस्या को फ़ंक्शन समस्या के रूप में जाना जाता है।

परिभाषा

See also: Total Turing machine

किसी फ़ंक्शन की संगणना एक अनौपचारिक धारणा है। इसका वर्णन करने का एक तरीका यह है कि कोई फ़ंक्शन गणना योग्य है यदि उसका मान किसी प्रभावी विधि द्वारा प्राप्त किया जा सकता है। अधिक कठोरता के साथ, एक कार्य $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ गणना योग्य तभी है जब कोई प्रभावी प्रक्रिया हो k-टपल $\mathbf {x}$ प्राकृतिक संख्याओं का, मूल्य उत्पन्न करेगा $f(\mathbf {x} )$. इस परिभाषा के साथ समझौते में, इस लेख का शेष भाग मानता है कि गणना योग्य कार्य तर्क के रूप में कई प्राकृतिक संख्याओं को लेते हैं और एक मान उत्पन्न करते हैं जो एक एकल प्राकृतिक संख्या है।

इस अनौपचारिक विवरण के समकक्षों के रूप में, कई औपचारिक, गणितीय परिभाषाएँ मौजूद हैं। गणना योग्य कार्यों के वर्ग को गणना के कई समकक्ष मॉडल में परिभाषित किया जा सकता है, जिनमें शामिल हैं

• ट्यूरिंग मशीनें
• μ-पुनरावर्ती कार्य
• लैम्ब्डा कैलकुलस
• पोस्ट मशीनें (पोस्ट-ट्यूरिंग मशीनें और टैग प्रणाली )।
• मशीनें पंजीकृत करें

हालाँकि ये मॉडल फ़ंक्शंस, उनके इनपुट और उनके आउटपुट के लिए अलग-अलग अभ्यावेदन का उपयोग करते हैं, अनुवाद किन्हीं दो मॉडलों के बीच मौजूद होते हैं, और इसलिए प्रत्येक मॉडल अनिवार्य रूप से फ़ंक्शंस के एक ही वर्ग का वर्णन करता है, जिससे यह राय बनती है कि औपचारिक कम्प्यूटेबिलिटी प्राकृतिक भी है और बहुत ज्यादा भी नहीं। सँकरा। अनौपचारिक गणना योग्य शब्द के विपरीत, इन कार्यों को कभी-कभी पुनरावर्ती के रूप में संदर्भित किया जाता है, क्लेन और गोडेल के बीच 1934 की चर्चा से उपजा भेद।^पृ.6

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

समान रूप से, गणना योग्य कार्यों को उन कार्यों के रूप में औपचारिक रूप दिया जा सकता है जिनकी गणना एक आदर्श कंप्यूटिंग एजेंट जैसे ट्यूरिंग मशीन या रजिस्टर मशीन द्वारा की जा सकती है। औपचारिक रूप से कहें तो, एक आंशिक कार्य $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ इसकी गणना तभी की जा सकती है जब निम्नलिखित गुणों वाला कोई कंप्यूटर प्रोग्राम मौजूद हो:

1. अगर $f(\mathbf {x} )$ परिभाषित किया गया है, तो प्रोग्राम इनपुट पर समाप्त हो जाएगा $\mathbf {x}$ मूल्य के साथ $f(\mathbf {x} )$ कंप्यूटर मेमोरी में संग्रहीत.
2. अगर $f(\mathbf {x} )$ अपरिभाषित है, तो प्रोग्राम कभी भी इनपुट पर समाप्त नहीं होता है $\mathbf {x}$.

संगणनीय कार्यों की विशेषताएँ

Main article: Algorithm

एक गणना योग्य फ़ंक्शन की मूल विशेषता यह है कि फ़ंक्शन की गणना कैसे करें, यह बताने वाली एक सीमित प्रक्रिया (एक एल्गोरिदम) होनी चाहिए। ऊपर सूचीबद्ध गणना के मॉडल एक प्रक्रिया क्या है और इसका उपयोग कैसे किया जाता है, इसकी अलग-अलग व्याख्याएं देते हैं, लेकिन ये व्याख्याएं कई गुणों को साझा करती हैं। तथ्य यह है कि ये मॉडल गणना योग्य कार्यों के समतुल्य वर्ग देते हैं, इस तथ्य से उपजा है कि प्रत्येक मॉडल किसी अन्य मॉडल के लिए एक प्रक्रिया को पढ़ने और उसकी नकल करने में सक्षम है, ठीक उसी तरह जैसे एक संकलक एक कंप्यूटर भाषा में निर्देश पढ़ने और निर्देशों को उत्सर्जित करने में सक्षम है। अन्य भाषा।

हर्बर्ट एंडर्टन [1977] एक गणना योग्य फ़ंक्शन की गणना के लिए एक प्रक्रिया की निम्नलिखित विशेषताएं देता है; इसी तरह के लक्षण ट्यूरिंग [1936], रोजर्स [1967] और अन्य द्वारा दिए गए हैं।

• प्रक्रिया के लिए सटीक निर्देश (अर्थात् एक प्रोग्राम) होने चाहिए, जिनकी लंबाई सीमित होनी चाहिए। इस प्रकार प्रत्येक गणना योग्य फ़ंक्शन में एक सीमित प्रोग्राम होना चाहिए जो पूरी तरह से वर्णन करता है कि फ़ंक्शन की गणना कैसे की जानी है। केवल निर्देशों का पालन करके फ़ंक्शन की गणना करना संभव है; किसी अनुमान या विशेष अंतर्दृष्टि की आवश्यकता नहीं है।
• यदि प्रक्रिया को f के डोमेन में k-tuple 'x' दिया गया है, तो अलग-अलग चरणों की एक सीमित संख्या के बाद प्रक्रिया को समाप्त होना चाहिए और f('x') उत्पन्न करना चाहिए। सहज रूप से, गणना के प्रत्येक चरण में क्या करना है, इसे कवर करने के लिए एक विशिष्ट नियम के साथ, प्रक्रिया चरण दर चरण आगे बढ़ती है। फ़ंक्शन का मान लौटाने से पहले केवल सीमित चरण ही पूरे किए जा सकते हैं।
• यदि प्रक्रिया को k-टुपल 'x' दिया गया है जो कि f के डोमेन में नहीं है, तो प्रक्रिया हमेशा के लिए चल सकती है, कभी नहीं रुकेगी। या यह किसी बिंदु पर अटक सकता है (यानी, इसके निर्देशों में से एक को निष्पादित नहीं किया जा सकता है), लेकिन इसे 'x' पर f के लिए मान उत्पन्न करने का दिखावा नहीं करना चाहिए। इस प्रकार यदि f('x') के लिए कोई मान कभी पाया जाता है, तो यह सही मान होना चाहिए। कंप्यूटिंग एजेंट के लिए सही परिणामों को गलत परिणामों से अलग करना आवश्यक नहीं है क्योंकि प्रक्रिया को तभी सही माना जाता है जब वह कोई परिणाम उत्पन्न करती है।

एंडर्टन एक गणना योग्य फ़ंक्शन के लिए प्रक्रिया की इन 3 आवश्यकताओं के कई स्पष्टीकरणों को सूचीबद्ध करता है:

1. प्रक्रिया को सैद्धांतिक रूप से मनमाने ढंग से बड़े तर्कों के लिए काम करना चाहिए। उदाहरण के लिए, यह नहीं माना जाता है कि तर्क पृथ्वी में परमाणुओं की संख्या से छोटे हैं।
2. आउटपुट उत्पन्न करने के लिए प्रक्रिया को कई चरणों के बाद रोकना आवश्यक है, लेकिन रुकने से पहले इसमें मनमाने ढंग से कई कदम लग सकते हैं। कोई समय सीमा नहीं मानी गई है.
3. यद्यपि प्रक्रिया सफल गणना के दौरान केवल सीमित मात्रा में भंडारण स्थान का उपयोग कर सकती है, लेकिन उपयोग किए जाने वाले स्थान की मात्रा पर कोई सीमा नहीं है। यह माना जाता है कि जब भी प्रक्रिया इसके लिए मांग करेगी तो प्रक्रिया को अतिरिक्त भंडारण स्थान दिया जा सकता है।

संक्षेप में, इस दृश्य के आधार पर एक फ़ंक्शन गणना योग्य है यदि:

1. given an input from its domain, possibly relying on unbounded storage space, it can give the corresponding output by following a procedure (program, algorithm) that is formed by a finite number of exact unambiguous instructions;
2. it returns such output (halts) in a finite number of steps; and
3. if given an input which is not in its domain it either never halts or it gets stuck.

कम्प्यूटेशनल जटिलता सिद्धांत अध्ययन का क्षेत्र एक सफल गणना में अनुमत समय और/या स्थान पर निर्धारित सीमा के साथ कार्य करता है।

संगणनीय सेट और संबंध

एक सेट A प्राकृतिक संख्याओं को गणना योग्य कहा जाता है (समानार्थक शब्द: पुनरावर्ती, निर्णायक) यदि कोई गणना योग्य, कुल कार्य है f जैसे कि किसी भी प्राकृतिक संख्या के लिए n, f(n) = 1 अगर n में है A और f(n) = 0 अगर n इसमें नहीं है A.

प्राकृतिक संख्याओं के एक सेट को गणना योग्य फ़ंक्शन होने पर गणना योग्य (समानार्थक शब्द: पुनरावर्ती गणना योग्य, अर्धनिर्णय योग्य) कहा जाता है। f ऐसा कि प्रत्येक संख्या के लिए n, f(n) को यदि और केवल यदि परिभाषित किया गया है n सेट में है. इस प्रकार एक सेट गणना योग्य है यदि और केवल यदि यह किसी गणना योग्य फ़ंक्शन का डोमेन है। गणना योग्य शब्द का उपयोग इसलिए किया जाता है क्योंकि निम्नलिखित एक गैर-रिक्त उपसमुच्चय के समतुल्य हैं B प्राकृतिक संख्याओं का:

• B एक संगणनीय फ़ंक्शन का डोमेन है।
• B कुल गणना योग्य फ़ंक्शन की सीमा है। अगर B अनंत है तो फ़ंक्शन को इंजेक्शन माना जा सकता है।

यदि एक सेट B किसी फ़ंक्शन की सीमा है f तो फ़ंक्शन को एक के रूप में देखा जा सकता है की गणना B, क्योंकि सूची f(0), f(1), ... का प्रत्येक तत्व शामिल होगा B.

क्योंकि प्राकृतिक संख्याओं पर प्रत्येक परिमित संबंध को प्राकृतिक संख्याओं के परिमित अनुक्रमों के संगत सेट के साथ पहचाना जा सकता है, गणना योग्य संबंध और गणना योग्य संबंध की धारणाओं को सेट के लिए उनके एनालॉग्स से परिभाषित किया जा सकता है।

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

Main article: Formal language

कम्प्यूटेबिलिटी सिद्धांत (कंप्यूटर विज्ञान) में, औपचारिक भाषाओं पर विचार करना आम बात है। 'वर्णमाला' एक मनमाना समुच्चय है। वर्णमाला पर एक 'शब्द' वर्णमाला के प्रतीकों का एक सीमित क्रम है; एक ही प्रतीक का प्रयोग एक से अधिक बार किया जा सकता है। उदाहरण के लिए, बाइनरी स्ट्रिंग बिल्कुल वर्णमाला के शब्द हैं {0, 1} . एक भाषा एक निश्चित वर्णमाला के सभी शब्दों के संग्रह का एक उपसमूह है। उदाहरण के लिए, सभी बाइनरी स्ट्रिंग्स का संग्रह जिसमें बिल्कुल 3 हैं, बाइनरी वर्णमाला पर एक भाषा है।

औपचारिक भाषा की एक प्रमुख विशेषता यह तय करने के लिए आवश्यक कठिनाई का स्तर है कि कोई दिया गया शब्द भाषा में है या नहीं। एक संगणनीय फ़ंक्शन को भाषा में एक मनमाने शब्द को इनपुट के रूप में लेने की अनुमति देने के लिए कुछ कोडिंग प्रणाली विकसित की जानी चाहिए; इसे आमतौर पर नियमित माना जाता है। यदि कोई गणना योग्य फ़ंक्शन है तो एक भाषा को गणना योग्य (समानार्थी शब्द: पुनरावर्ती, निर्णायक) कहा जाता है f ऐसा कि प्रत्येक शब्द के लिए w वर्णमाला के ऊपर, f(w) = 1यदि शब्द भाषा में है और f(w) = 0यदि शब्द भाषा में नहीं है। इस प्रकार एक भाषा तभी गणना योग्य होती है जब ऐसी कोई प्रक्रिया हो जो सही ढंग से यह बताने में सक्षम हो कि भाषा में मनमाने शब्द हैं या नहीं।

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

उदाहरण

निम्नलिखित कार्य गणना योग्य हैं:

• प्रत्येक फ़ंक्शन एक फ़ंक्शन के एक सीमित डोमेन के साथ; उदाहरण के लिए, प्राकृतिक संख्याओं का कोई भी सीमित क्रम।
• प्रत्येक स्थिर फलन f : 'N'^क → 'एन', एफ(एन)।₁,...एन_k) := एन.
• अतिरिक्त एफ : 'एन'² → N, f(n₁,एन₂) := एन₁ + एन₂
• दो संख्याओं का सबसे बड़ा सामान्य भाजक
• दो संख्याओं का बेज़आउट गुणांक
• किसी संख्या का सबसे छोटा अभाज्य गुणनखंड

यदि f और g गणना योग्य हैं, तो ये भी हैं: f + g, गुणन|f * g, फ़ंक्शन संरचना|$\color {Blue}f\circ g$अगर एफ यूनरी ऑपरेशन है, अधिकतम(एफ,जी), न्यूनतम(एफ,जी), arg max{y ≤ f(x)} और कई अन्य संयोजन।

निम्नलिखित उदाहरण बताते हैं कि एक फ़ंक्शन गणना योग्य हो सकता है, हालांकि यह ज्ञात नहीं है कि कौन सा एल्गोरिदम इसकी गणना करता है।

• फ़ंक्शन f ऐसा है कि f(n) = 1 यदि दशमलव विस्तार में कम से कम n लगातार पांच का क्रम है π, और f(n) = 0 अन्यथा, गणना योग्य है। (फ़ंक्शन f या तो स्थिर 1 फ़ंक्शन है, जो गणना योग्य है, या फिर एक k है जैसे कि f(n) = 1 यदि n < k और f(n) = 0 यदि n ≥ k। ऐसा प्रत्येक फ़ंक्शन गणना योग्य है। यह ज्ञात नहीं है कि π के दशमलव विस्तार में पाँचों की मनमाने ढंग से लंबी श्रृंखलाएँ हैं, इसलिए हम नहीं जानते कि उनमें से कौन सा फ़ंक्शन f है। फिर भी, हम जानते हैं कि फ़ंक्शन f गणना योग्य होना चाहिए।)
• प्राकृतिक संख्याओं के एक अगणनीय अनुक्रम का प्रत्येक परिमित खंड (जैसे कि व्यस्त बीवर # व्यस्त बीवर फ़ंक्शन Σ Σ) गणना योग्य है। उदाहरण के लिए, प्रत्येक प्राकृतिक संख्या n के लिए, एक एल्गोरिथ्म मौजूद है जो परिमित अनुक्रम Σ(0), Σ(1), Σ(2), ..., Σ(n) की गणना करता है - इस तथ्य के विपरीत कि कोई नहीं है एल्गोरिथ्म जो संपूर्ण Σ-अनुक्रम की गणना करता है, अर्थात सभी n के लिए Σ(n)। इस प्रकार, प्रिंट 0, 1, 4, 6, 13 Σ(0), Σ(1), Σ(2), Σ(3), Σ(4) की गणना करने के लिए एक तुच्छ एल्गोरिदम है; इसी तरह, n के किसी भी दिए गए मान के लिए, Σ(0), Σ(1), Σ(2), ..., Σ( एन)।

चर्च-ट्यूरिंग थीसिस

Main article: Church–Turing thesis

चर्च-ट्यूरिंग थीसिस में कहा गया है कि एक प्रक्रिया से गणना योग्य कोई भी फ़ंक्शन जिसमें सूचीबद्ध तीन गुण होते हैं #गणना योग्य कार्यों की विशेषताएं एक गणना योग्य कार्य है। क्योंकि इन तीन गुणों को औपचारिक रूप से नहीं बताया गया है, चर्च-ट्यूरिंग थीसिस को साबित नहीं किया जा सकता है। निम्नलिखित तथ्यों को अक्सर थीसिस के प्रमाण के रूप में लिया जाता है:

• गणना के कई समकक्ष मॉडल ज्ञात हैं, और वे सभी गणना योग्य फ़ंक्शन (या कुछ उदाहरणों में कमजोर संस्करण) की एक ही परिभाषा देते हैं।
• गणना का कोई मजबूत मॉडल जिसे आम तौर पर प्रभावी ढंग से गणना करने योग्य माना जाता है, प्रस्तावित नहीं किया गया है।

चर्च-ट्यूरिंग थीसिस का उपयोग कभी-कभी गणना के लिए एक प्रक्रिया का ठोस विवरण देकर यह प्रमाणित करने के लिए प्रमाणों में किया जाता है कि एक विशेष फ़ंक्शन गणना योग्य है। इसकी अनुमति है क्योंकि यह माना जाता है कि थीसिस के ऐसे सभी उपयोगों को गणना के कुछ मॉडल में फ़ंक्शन के लिए औपचारिक प्रक्रिया लिखने की कठिन प्रक्रिया द्वारा हटाया जा सकता है।

संभाव्यता

किसी फ़ंक्शन (या, इसी तरह, एक सेट) को देखते हुए, किसी को न केवल यह दिलचस्पी हो सकती है कि यह गणना योग्य है, बल्कि यह भी कि क्या इसे किसी विशेष प्रमाण प्रणाली (आमतौर पर प्रथम-क्रम तर्क पीनो अंकगणित) में सिद्ध किया जा सकता है। एक फ़ंक्शन जिसे गणना योग्य सिद्ध किया जा सकता है उसे 'प्रोवेबली टोटल' कहा जाता है।

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

पुनरावर्ती रूप से परिभाषित कार्यों से संबंध

पुनरावर्ती परिभाषा द्वारा परिभाषित फ़ंक्शन में, प्रत्येक मान को उसी फ़ंक्शन या अन्य फ़ंक्शन के अन्य, पहले से परिभाषित मानों के एक निश्चित प्रथम-क्रम सूत्र द्वारा परिभाषित किया जाता है, जो केवल स्थिरांक हो सकते हैं। इनका एक उपसमुच्चय आदिम पुनरावर्ती कार्य है। ऐसा प्रत्येक फ़ंक्शन सिद्ध रूप से कुल है: ऐसे arity|k-ary फ़ंक्शन f के लिए, प्रत्येक मान $f(n_{1},n_{2}...n_{k})$ परिभाषा का पीछे की ओर, पुनरावृत्तीय रूप से अनुसरण करके गणना की जा सकती है, और पुनरावृत्ति की सीमित संख्या के बाद (जैसा कि आसानी से सिद्ध किया जा सकता है), एक स्थिरांक तक पहुंच जाता है।

इसका विपरीत सत्य नहीं है, क्योंकि प्रत्येक सिद्ध कुल फ़ंक्शन आदिम पुनरावर्ती नहीं है। वास्तव में, कोई भी सभी आदिम पुनरावर्ती कार्यों की गणना कर सकता है और एक फ़ंक्शन को इस तरह परिभाषित कर सकता है कि सभी n, m के लिए: en(n,m) = f_n(एम), जहां एफ_n n-वें आदिम पुनरावर्ती फ़ंक्शन है (arity|k-ary फ़ंक्शंस के लिए, इसे f पर सेट किया जाएगा)_n(म,म...म)). अब, g(n) = en(n,n)+1 एक विकर्ण लेम्मा तर्क द्वारा सिद्ध रूप से कुल है, लेकिन आदिम पुनरावर्ती नहीं है: यदि कोई j ऐसा होता कि g = f_j, हमें g(j) = en(j,j)+1 = f मिला होगा_j (जे)+1= जी(जे)+1, एक विरोधाभास। (सभी आदिम पुनरावर्ती कार्यों की गोडेल संख्याओं को एक आदिम पुनरावर्ती फ़ंक्शन द्वारा गिना जा सकता है, हालांकि आदिम पुनरावर्ती कार्यों के मान नहीं हो सकते हैं।)

ऐसा एक फ़ंक्शन, जो कुल सिद्ध है लेकिन आदिम पुनरावर्ती नहीं है, एकरमैन फ़ंक्शन है: चूंकि इसे पुनरावर्ती रूप से परिभाषित किया गया है, इसलिए इसकी गणनात्मकता साबित करना वास्तव में आसान है (हालांकि, पुनरावर्ती परिभाषा द्वारा परिभाषित सभी कार्यों के लिए एक समान विकर्णीकरण तर्क भी बनाया जा सकता है ; इस प्रकार, ऐसे सिद्ध कुल कार्य हैं जिन्हें पुनरावर्ती रूप से परिभाषित नहीं किया जा सकता है).

कुल कार्य जो सिद्ध रूप से कुल नहीं हैं

एक सुदृढ़ता प्रमाण प्रणाली में, प्रत्येक सिद्ध कुल कार्य वास्तव में कुल होता है, लेकिन इसका विपरीत सत्य नहीं है: प्रत्येक प्रथम-क्रम प्रमाण प्रणाली में जो पर्याप्त रूप से मजबूत और ध्वनि (पीनो अंकगणित सहित) है, कोई (किसी अन्य प्रमाण प्रणाली में) साबित कर सकता है कुल कार्यों का अस्तित्व जिन्हें प्रमाण प्रणाली में कुल सिद्ध नहीं किया जा सकता है।

यदि कुल गणना योग्य कार्यों की गणना ट्यूरिंग मशीनों के माध्यम से की जाती है जो उन्हें उत्पन्न करती है, तो उपरोक्त कथन को दिखाया जा सकता है, यदि प्रमाण प्रणाली सही है, तो ऊपर दिए गए समान विकर्णीकरण तर्क द्वारा, पहले दिए गए सिद्ध कुल कार्यों की गणना का उपयोग करके। कोई ट्यूरिंग मशीन का उपयोग करता है जो प्रासंगिक प्रमाणों की गणना करता है, और प्रत्येक इनपुट के लिए n कॉल f करता है_n(एन) (जहाँ एफ_n इस गणना द्वारा एन-वें फ़ंक्शन है) ट्यूरिंग मशीन को लागू करके जो एन-वें प्रमाण के अनुसार इसकी गणना करता है। यदि प्रूफ सिस्टम दुरुस्त है तो ऐसी ट्यूरिंग मशीन के रुकने की गारंटी है।

अगणनीय कार्य और अघुलनशील समस्याएँ

Main article: List of undecidable problems

प्रत्येक गणना योग्य फ़ंक्शन की एक सीमित प्रक्रिया होती है जो इसकी गणना करने के तरीके पर स्पष्ट, स्पष्ट निर्देश देती है। इसके अलावा, इस प्रक्रिया को कम्प्यूटेशनल मॉडल द्वारा उपयोग किए जाने वाले परिमित वर्णमाला में एन्कोड किया जाना है, इसलिए केवल गणना योग्य कई कार्य हैं। उदाहरण के लिए, फ़ंक्शंस को बिट्स की एक स्ट्रिंग (वर्णमाला) का उपयोग करके एन्कोड किया जा सकता है Σ = {0, 1}).

वास्तविक संख्याएँ बेशुमार होती हैं इसलिए अधिकांश वास्तविक संख्याएँ गणना योग्य नहीं होती हैं। गणना योग्य संख्या#गुण देखें। प्राकृतिक संख्याओं पर अंतिम कार्यों का सेट बेशुमार है इसलिए अधिकांश गणना योग्य नहीं हैं। ऐसे कार्यों के ठोस उदाहरण हैं व्यस्त बीवर, कोलमोगोरोव जटिलता, या कोई भी फ़ंक्शन जो गैर-गणना योग्य संख्या के अंकों को आउटपुट करता है, जैसे कि चैतिन का स्थिरांक।

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

कम्प्यूटेबिलिटी का विस्तार

सापेक्ष संगणना

किसी फ़ंक्शन की संगणना की धारणा प्राकृतिक संख्या ए के एक मनमाने ढंग से सेट (गणित) के सापेक्ष संगणनीयता हो सकती है। एक फ़ंक्शन एफ को 'ए में संगणनीय' (समकक्ष 'ए-गणना योग्य' या 'ए के सापेक्ष संगणनीय') के रूप में परिभाषित किया गया है। जब यह एक गणना योग्य फ़ंक्शन की परिभाषा को संशोधनों के साथ संतुष्ट करता है जो ए को ओरेकल (कम्प्यूटेबिलिटी) के रूप में पहुंच की अनुमति देता है। एक संगणनीय फ़ंक्शन की अवधारणा के साथ सापेक्ष संगणना को संगणना के कई अलग-अलग मॉडलों में समकक्ष परिभाषाएँ दी जा सकती हैं। यह आम तौर पर एक अतिरिक्त आदिम ऑपरेशन के साथ गणना के मॉडल को पूरक करके पूरा किया जाता है जो पूछता है कि क्या कोई दिया गया पूर्णांक ए का सदस्य है। हम इसके ग्राफ के साथ जी की पहचान करके एफ के 'जी में गणना योग्य' होने के बारे में भी बात कर सकते हैं।

उच्च प्रत्यावर्तन सिद्धांत

हाइपररिथमेटिकल सिद्धांत उन सेटों का अध्ययन करता है जिनकी गणना खाली सेट के ट्यूरिंग जंप के पुनरावृत्तों की गणना योग्य क्रमिक संख्या से की जा सकती है। यह दूसरे क्रम के अंकगणित की भाषा में और हाइपरकंप्यूटेशन के कुछ मॉडलों में सार्वभौमिक और अस्तित्वगत सूत्र दोनों द्वारा परिभाषित सेट के बराबर है। और भी सामान्य पुनरावर्ती सिद्धांतों का अध्ययन किया गया है, जैसे कि ई-पुनरावर्ती सिद्धांत जिसमें किसी भी सेट को ई-पुनरावर्ती फ़ंक्शन के तर्क के रूप में उपयोग किया जा सकता है।

हाइपर-गणना

यद्यपि चर्च-ट्यूरिंग थीसिस में कहा गया है कि गणना योग्य कार्यों में एल्गोरिदम के साथ सभी फ़ंक्शन शामिल हैं, कार्यों के व्यापक वर्गों पर विचार करना संभव है जो एल्गोरिदम के पास होने वाली आवश्यकताओं को शिथिल करते हैं। हाइपरकंप्यूटेशन का क्षेत्र गणना के ऐसे मॉडलों का अध्ययन करता है जो सामान्य ट्यूरिंग गणना से परे जाते हैं।

यह भी देखें

• गणना योग्य संख्या
• प्रभावी विधि
• गणना का सिद्धांत
• पुनरावर्तन सिद्धांत
• ट्यूरिंग डिग्री
• अंकगणितीय पदानुक्रम
• हाइपरकंप्यूटेशन
• सुपर-पुनरावर्ती एल्गोरिथ्म
• अर्ध संगणनीय कार्य

संदर्भ

• Cutland, Nigel. Computability. Cambridge University Press, 1980.
• Enderton, H.B. Elements of recursion theory. Handbook of Mathematical Logic (North-Holland 1977) pp. 527–566.
• Rogers, H. Theory of recursive functions and effective computation (McGraw–Hill 1967).
• Turing, A. (1937), On Computable Numbers, With an Application to the Entscheidungsproblem. Proceedings of the London Mathematical Society, Series 2, Volume 42 (1937), p.230–265. Reprinted in M. Davis (ed.), The Undecidable, Raven Press, Hewlett, NY, 1965.