संगणनीय फलन

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

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

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

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

परिभाषा

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 है, max (f, g), min (f, g), arg max{y ≤ f(x)} और कई और संयुक्त है।

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

• फलन f (n) = 1 यदि दशमलव विस्तार में कम से कम n लगातार पाँचों का एक अनुक्रम है π, और f (n) = 0 अन्यथा, गणना योग्य है। (फलन F या तो स्थिरांक 1 फलन है, जो गणना योग्य है, 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) की गणना करने के लिए एक तुच्छ एल्गोरिथ्म सम्मलित है (भले ही यह कभी भी ज्ञात या किसी के द्वारा निर्मित नहीं हो सकता है) σ (0), σ (1), σ (2), ..., σ n।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Main article: अनिर्णीत समस्याओं की सूची

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

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

इसी तरह, प्राकृत संख्याओं के अधिकांश उपसमुच्चय संगणनीय नहीं हैं। हॉल्टिंग की समस्या निर्मित होने वाला पहला ऐसा सेट था। डेविड हिल्बर्ट द्वारा प्रस्तावित एंट्सचेइडुंगस्प्रोबल ने पूछा कि क्या यह निर्धारित करने के लिए एक प्रभावी प्रक्रिया है कि कौन से गणितीय कथन (प्राकृतिक संख्या के रूप में कोडित) सत्य हैं। ट्यूरिंग और चर्च ने 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.