संगणनीय फलन

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

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

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

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

परिभाषा

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

किसी कार्य की संगणनीयता एक अनौपचारिक धारणा है। इसका वर्णन करने का एक नियम यह है कि एक कार्य गणना योग्य है यदि इसका मूल्य एक प्रभावी विधि द्वारा प्राप्त किया जा सकता है। अधिक कठोरता के साथ, एक कार्य $f:\mathbb {N} ^{k}\rightarrow \mathbb {N}$ संगणनीय है यदि एकमात्र कोई प्रभावी प्रक्रिया है, तो अभिकलनात्‍मक है k-टपल $\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. और यदि कोई इनपुट दिया जाता है जो उसके डोमेन में नहीं है तो भी वह कभी रुकता नहीं है और न ही कभी अटकता है।

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

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

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

संगणनीयता का विस्तार

सापेक्ष संगणनीयता

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

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

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

अति संगणना

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

यह भी देखें

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

संदर्भ

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