संगणनीय फलन

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

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

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

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

परिभाषा

See also: कुल ट्यूरिंग मशीन

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

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

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

यद्यपि ये मॉडल कार्यों, उनके इनपुट, और उनके आउटपुट के लिए अलग -अलग प्रतिनिधित्व का उपयोग करते हैं, अनुवाद किसी भी दो मॉडलों के बीच सम्मलित हैं, और इसलिए प्रत्येक मॉडल अनिवार्य रूप से कार्यों के समान वर्ग का वर्णन करता है, इसका अभिप्राय यह है कि औपचारिक संगणनीयता स्वाभाविक है संकीर्ण। इन कार्यों को कभी -कभी पुनरावर्ती के रूप में संदर्भित किया जाता है, क्लेन और गोडेल के बीच 1934 की चर्चा से उपजी एक अंतर।^p.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-tuple '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।

प्राकृतिक संख्याओं के एक सेट को कम्प्यूटेशनल रूप से enumerable कहा जाता है (समानार्थक शब्द: पुनरावर्ती रूप से enumerable, semidecidable) यदि एक कम्प्यूटेबल फ़ंक्शन है f ऐसा कि प्रत्येक संख्या के लिए n, f(n) परिभाषित किया गया है अगर और केवल अगर n सेट में है।इस प्रकार एक सेट कम्प्यूटिक रूप से यदि और केवल अगर यह कुछ कम्प्यूटेबल फ़ंक्शन का डोमेन है।Enumerable शब्द का उपयोग किया जाता है क्योंकि निम्नलिखित एक गैर -रिक्त सबसेट के बराबर हैं 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 यदि शब्द भाषा में नहीं है।इस प्रकार एक भाषा कम्प्यूटेबल होती है, बस एक ऐसी प्रक्रिया होती है जो सही ढंग से बताने में सक्षम होती है कि क्या मनमाने शब्द भाषा में हैं।

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

उदाहरण

निम्नलिखित कार्य कम्प्यूटेशनल हैं:

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

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

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

• फ़ंक्शन f जैसे कि f (n) = 1 यदि दशमलव विस्तार में कम से कम n लगातार fives का एक अनुक्रम है π, और f (n) = 0 अन्यथा, कम्प्यूटेशनल है।(फ़ंक्शन F या तो निरंतर 1 फ़ंक्शन है, जो कम्प्यूटेशनल है, या फिर एक k है जैसे कि f (n) = 1 यदि n <k और f (n) = 0 यदि n ≥ k। ऐसा प्रत्येक फ़ंक्शन कम्प्यूटेशनल है।यह ज्ञात नहीं है कि क्या π के दशमलव विस्तार में मनमाने ढंग से लंबे समय तक फाइव्स हैं, इसलिए हम नहीं जानते कि उन कार्यों में से कौन सी है। फिर भी, हम जानते हैं कि फ़ंक्शन 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

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

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

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

प्रोवेबिलिटी

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

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

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

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

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

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

कुल कार्य जो कुल नहीं हैं

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

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

अप्रभावी कार्य और अनहोनी समस्याएं

Main article: List of undecidable problems

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

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

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

कम्प्यूटिबिलिटी का एक्सटेंशन

सापेक्ष कम्प्यूटिबिलिटी

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

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

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

हाइपर-कंप्यूटेशन

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

यह भी देखें

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

संदर्भ

• 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.