संगणनीय फलन

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

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

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

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

परिभाषा

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: कलन विधि

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

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

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

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

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

संक्षेप में, इस दृश्य के आधार पर एक कार्य की गणना की जा सकती है:

1. अपने डोमेन से एक इनपुट दिया गया है, संभवतः असीमित स्टोरेज स्पेस पर भरोसा करते हुए, यह एक प्रक्रिया (प्रोग्राम, एल्गोरिदम) का पालन करके संबंधित आउटपुट दे सकता है जो सटीक स्पष्ट निर्देशों की एक सीमित संख्या से बनता है;
2. यह इस तरह के आउटपुट (हॉल्ट्स) को सीमित चरणों में लौटाता है;
3. और यदि कोई इनपुट दिया जाता है जो उसके डोमेन में नहीं है तो भी वह कभी रुकता नहीं है और न ही कभी अटकता है।

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

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

प्राकृतिक संख्याओं के एक सेट को संगणनीय कहा जाता है (समानार्थी: पुनरावर्ती,निर्णायक) यदि कोई संगणनीय, कुल कार्य 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: औपचारिक भाषा

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

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

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

उदाहरण

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

• एक फ़ंक्शन के परिमित डोमेन के साथ प्रत्येक फ़ंक्शन;जैसे, प्राकृतिक संख्याओं का कोई परिमित अनुक्रम।
• प्रत्येक निरंतर फ़ंक्शन 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.