संगणनीयता सिद्धांत

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

संगणनीयता सिद्धांत द्वारा संबोधित मूल प्रश्नों में निम्नलिखित प्रश्न सम्मिलित हैं:

• प्राकृतिक संख्याओं के फलन का गणना योग्य होने का क्या अर्थ है?
• गैर-संगणनीय फलनों को उनके गैर-संगणनीयता के स्तर के आधार पर पदानुक्रम में कैसे वर्गीकृत किया जा सकता है?

यद्यपि ज्ञान और विधियों के संदर्भ में पर्याप्त अधिव्यापन है, गणितीय संगणक सिद्धांतवादी सापेक्ष संगणनीयता, न्यूनीकरण धारणाओं और श्रेणी संरचनाओं के सिद्धांत का अध्ययन करते हैं; संगणक विज्ञान क्षेत्र के लोग संगणनात्मक जटिलता सिद्धांत, औपचारिक विधि और औपचारिक भाषाओं के सिद्धांत पर ध्यान केंद्रित करते हैं।

परिचय

n	2	3	4	5	6	7	...
Σ(n)	4	6	13	4098 ?	> 3.5×1018267	> 1010101018705353	?
Does not appearव्यस्त बीवर कार्य किसी भी संगणनीय कार्य की तुलना में तेज़ी से बढ़ता है।इसलिए, यह गणना योग्य नहीं है;केवल कुछ ही मान ज्ञात हैं।

अनुकूलता सिद्धांत की उत्पत्ति 1930 के दशक में कर्ट गोडेल, अलोंजो चर्च, रोजसा पेटर, एलन ट्यूरिंग, स्टीफन क्लेन और एमिल पोस्ट के कार्य से हुई थी।

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

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

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

इन प्रारंभिक उदाहरणों को स्थापित करने के पश्चात गणित में अनेको समस्याओं को अनिर्णीत प्रदर्शित किया गया है। 1947 में, एंड्री मार्कोव जूनियर और पोस्ट ने स्वतंत्र पत्र प्रकाशित किए, जिसमें प्रदर्शित किया कि उपसमूह के लिए शब्द समस्या प्रभावी ढंग से तय नहीं की जा सकती। इस परिणाम का विस्तार करते हुए, पीटर नोविकोव और विलियम बून ने 1950 के दशक में स्वतंत्र रूप से प्रदर्शित कि समूहों के लिए शब्द समस्या प्रभावी रूप से हल करने योग्य नहीं है और न ही कोई प्रभावी प्रक्रिया है जो अंतिम रूप से प्रस्तुत समूह में एक शब्द दिया हो, यह तय करे कि क्या शब्द द्वारा दर्शाया गया तत्व समूह का पहचान तत्व है। 1970 में, यूरी मटियासेविच ने जूलिया रॉबिन्सन के परिणामों का उपयोग करके मटियासेविच के प्रमेय को प्रमाणित किया, जिसका अर्थ है कि हिल्बर्ट की दसवीं समस्या का कोई प्रभावी समाधान नहीं है; इस समस्या के पश्चात उन्होंने पूछा कि क्या यह तय करने के लिए कोई प्रभावी प्रक्रिया है। अनिर्णीत समस्याओं की सूची अतिरिक्त उदाहरण देती है जिनका कोई संगणनीय समाधान नहीं है।

जिन गणितीय रचनाओं का अध्ययन प्रभावी ढंग से किया जा सकता है, उन्हें कभी-कभी पुनरावर्ती गणित कहा जाता है;इस क्षेत्र में कई ज्ञात परिणामों को सम्मिलित किया गया है।

ट्यूरिंग संगंणनीयता

संगंणनीयता सिद्धांत में अध्ययन की गई संगंणनीयता का मुख्य रूप 1936 ई. में ट्यूरिंग द्वारा प्रस्तुत किया गया था।प्राकृतिक संख्याओं के एक समुच्चय को संगणनीय समुच्चय कहा जाता है, जिसे एक निर्णायक पुनरावर्ती, या ट्यूरिंग गणना योग्य समुच्चय भी कहा जाता है। यदि कोई ट्यूरिंग यंत्र है, जिसे संख्या n दी गई है, निर्गत 1 के साथ रुकता है यदि n समुच्चय में है और रुकता है एवं निर्गत 0 के साथ यदि n समुच्चय में नहीं है। प्राकृतिक संख्याओं तक कार्य f एक संगंणनीय कार्य या पुनरावर्ती कार्य है यदि कोई ट्यूरिंग यंत्र है, जो निविष्ट n पर रुकती है और निर्गत f (n) लौटाती है। यहाँ ट्यूरिंग यंत्रों का उपयोग आवश्यक नहीं है; संगंणकता के कई अन्य प्रारूप हैं जिनकी संगंणन शक्ति ट्यूरिंग यंत्रों के समान है; उदाहरण के लिए प्रारंभिक पुनरावर्तन और μ संकार्य से प्राप्त μ-पुनरावर्ती कार्य।

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

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

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

अनुसंधान के क्षेत्र

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

सापेक्ष संगणनीयता और ट्यूरिंग श्रेणी

Main articles: Turing reduction and Turing degree

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

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

समुच्चय के प्राकृतिक उदाहरण जो गणना योग्य नहीं हैं, जिसमें कई अलग-अलग समुच्चय सम्मिलित हैं जो विरामतः समस्या के प्रकार को एनकोड करते हैं, उनमें दो गुण समान हैं:

1. वे पुनरावर्ती रूप से गणना योग्य हैं,और
2. प्रत्येक को अनेक-एक अपचयन के माध्यम से किसी अन्य में अनुवादित किया जा सकता है। अर्थात्, ऐसे समुच्चय A और B दिए गए हैं, कुल संगणनीय फलन f ऐसा है कि A = {x : f(x) ∈ B}। इन समुच्चयों को एका-एक समकक्ष या एम-समतुल्य कहा जाता है।

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

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

ऐसे कई समुच्चय हैं जो संगणनीय रूप से गणना योग्य नहीं हैं, और सभी समुच्चयों की ट्यूरिंग श्रेणी की जांच संगंणनीयता सिद्धांत में उतनी ही केंद्रीय है जितनी कि गणना योग्य ट्यूरिंग श्रेणी की जांच। विशेष गुणों के साथ कई श्रेणियों का निर्माण किया गया: अतिप्रतिरक्षा -मुक्त श्रेणिया जहां उस श्रेणी के सापेक्ष प्रत्येक कार्य की गणना एक असंबद्ध संगणनीय कार्य द्वारा की जाती है; उच्च श्रेणी जिसके सापेक्ष कोई एक कार्य f की गणना कर सकता है जो प्रत्येक गणना योग्य कार्य g पर हावी है, इस अर्थ में कि g के आधार पर एक स्थिर c है जैसे कि g(x) <f(x) for all x > c; एल्गोरिथम यादृच्छिक समुच्चय युक्त यादृच्छिक श्रेणी; 1-जेनेरिक समुच्चय की 1-जेनेरिक श्रेणी; और सीमित रिकर्सिव लिमिट-संगंणनीय समुच्चय की विरामतः समस्या से नीचे की श्रेणी।

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

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

अन्य कमी

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

प्रबल कटौती में सम्मिलित हैं:

एक-एक कमी: A, B के लिए एक-एक कम करने योग्य (या 1-कम करने योग्य) है यदि कुल संगणनीय अंतःक्षेपण फलन f ऐसा है कि प्रत्येक n A में है यदि और केवल यदि f(n) है बी में।

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

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

लेख में आगे की कमी और सकारात्मक, वियोगात्मक, संयोजन, रैखिक और उनके कमजोर और बंधे हुए संस्करण पर चर्चा की गई है।

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

ट्यूरिंग अपचेयक की तुलना में दुर्बल अपचेयक का भी अध्ययन किया गया है। सबसे प्रसिद्ध अंकगणितीय अपचेयक और अंकगणितीय कमी हैं। ये अपचेयक अंकगणित के मानक प्रारूप पर निश्चितता एवं निकटता से जुड़ी हुई हैं।

राइस का प्रमेय और अंकगणितीय पदानुक्रम

हेनरी गॉर्डन राइस ने प्रदर्शित कि प्रत्येक असतहीय वर्ग C के लिए सूचकांक समुच्चय E = {e: eth c.e. समुच्चय डब्ल्यू_eis in C} में यह गुण है कि या तो विरामतः समस्या या इसकी प्रशंसा एका-बहुल अपचेयक E के लिए है, अर्थात, E के लिए एकाबहुल अपचयन का उपयोग करके दोष रहित किया जा सकता है। लेकिन, इनमें से कई अच्छे समुच्चय विरामतः समस्या से भी अधिक जटिल हैं। इस प्रकार के समुच्चयों को अंकगणितीय पदानुक्रम का उपयोग करके वर्गीकृत किया जा सकता है। उदाहरण के लिए, सभी अनंत समुच्चयों के वर्ग का सूचकांक समुच्चय FIN स्तर Σ पर है₂, सभी पुनरावर्ती समुच्चयों के वर्ग का सूचकांक समुच्चय REC स्तर Σ पर है₃, सभी कॉफिनिट समुच्चयों का अच्छे समुच्चय COFIN भी Σ के स्तर पर है₃ और सभी ट्यूरिंग-पूर्ण समुच्चयों के वर्ग का सूचकांक समुच्चय COMP₄. इन पदानुक्रम स्तरों को आगमनात्मक रूप से परिभाषित किया गया है, Σ_n+1 केवल सभी समुच्चय सम्मिलित हैं जो Σ के सापेक्ष गणना योग्य हैं_n; एस₁ संगणनीय रूप से गणना करने योग्य समुच्चय सम्मिलित हैं। यहां दिए गए अच्छे समुच्चय अपने स्तरों के लिए भी पूर्ण हैं, यानी इन स्तरों के सभी समुच्चय दिए गए अच्छे समुच्चयों में एका-एक घटाए जा सकते हैं।

प्रतिलोम गणित

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

संख्यांकन

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

प्राथमिकता विधि

पोस्ट की समस्या को एक विधि से हल किया गया जिसे प्राथमिकता विधि कहा जाता है; इस पद्धति का उपयोग करने वाले प्रमाण को प्राथमिकता तर्क कहा जाता है। इस पद्धति का मुख्य रूप से विशेष गुणों के साथ संगणनीय गणना योग्य समुच्चय बनाने के लिए उपयोग किया जाता है। इस पद्धति का उपयोग करने के लिए, निर्मित किए जाने वाले समुच्चय के वांछित गुणों को लक्ष्यों की एक अनंत सूची में विभाजित किया जाता है, जिसे आवश्यकताओं के रूप में जाना जाता है, ताकि सभी आवश्यकताओं को पूरा करने के कारण समुच्चय में वांछित गुण हों। प्रत्येक आवश्यकता को आवश्यकता की प्राथमिकता का प्रतिनिधित्व करने वाली प्राकृतिक संख्या को सौंपा गया है; इसलिए 0 को सबसे महत्वपूर्ण प्राथमिकता दी जाती है, 1 को दूसरी सबसे महत्वपूर्ण प्राथमिकता दी जाती है, और इसी तरह आगे भी। प्रायः समुच्चय का निर्माण चरणों में किया जाता है, प्रत्येक चरण समुच्चय में संख्याओं को जोड़कर या समुच्चय से संख्याओं को प्रतिबंधित करके एक से अधिक आवश्यकताओं को पूरा करने का प्रयास करता है ताकि अंतिम समुच्चय आवश्यकता को पूरा करे। ऐसा हो सकता है कि एक आवश्यकता को पूरा करने से दूसरी असंतुष्ट हो जाए; ऐसी घटना में क्या करना है, यह तय करने के लिए प्राथमिकता क्रम का उपयोग किया जाता है।

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

संगणनीय रूप से गणना योग्य समुच्चयों की जाली

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

स्वसमाकृतिकता समस्याएं

एक अन्य महत्वपूर्ण प्रश्न संगंणनीयता-सैद्धांतिक संरचनाओं में स्वसमाकृतिकता का अस्तित्व है। इन संरचनाओं में से एक यह है कि समावेशन के सापेक्ष अनंत अंतर के अनुसार गणना योग्य समुच्चयों में से एक; इस संरचना में, A, B से नीचे है यदि और केवल यदि समुच्चय अंतर B − A अनंत है। मैक्सिमल समुच्चय में संपत्ति कि वे गैर-मैक्सिमल समुच्चय के लिए स्वसमाकृतिक नहीं हो सकते हैं, अर्थात, यदि संरचना के तहत संगंणकताल रूप से गणना करने योग्य समुच्चय का एक स्वसमाकृतिकता है, तो हर अधिकतम समुच्चय को आलेख्यपत्र किया जाता है। 1974 में, सोरेने प्रदर्शित कि इसका विपरीत भी धारण करता है, अर्थात प्रत्येक दो अधिकतम समुच्चय स्वतः रूपी होते हैं। तो अधिकतम समुच्चय एक कक्षा बनाते हैं, अर्थात, प्रत्येक स्वसमाकृतिक अधिकतमता को बरकरार रखता है और किसी भी दो अधिकतम समुच्चय एक दूसरे में कुछ स्वसमाकृतिकता द्वारा परिवर्तित हो जाते हैं। हैरिंगटन ने एक स्वसमाकृतिक संपत्ति का एक और उदाहरण दिया: रचनात्मक समुच्चयों का समुच्चय, जो एका-एक विरामतः समस्या के बराबर हैं।

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

कोलमोगोरोव जटिलता

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

आवृत्ति गणना

संगणनीयता सिद्धांत की इस शाखा ने निम्नलिखित प्रश्न का विश्लेषण किया: नियत m और n के लिए 0 < m < n के साथ, किन कार्यों के लिए A किसी भिन्न n निविष्ट x के लिए गणना करना संभव है₁, एक्स₂, ..., एक्स_nn संख्या y का एक टपल₁, वाई₂, ..., और_nऐसा है कि कम से कम m समीकरणों की A(x_k) = और_kसच हैं। इस तरह के समुच्चय को (एम, एन) -रिकर्सिव समुच्चय के रूप में जाना जाता है। संगंणनीयता सिद्धांत की इस शाखा में पहला प्रमुख परिणाम ट्रेखटेनब्रॉट का परिणाम है कि एक समुच्चय की गणना की जा सकती है यदि यह एम, एन है - कुछ एम के लिए पुनरावर्ती, 2 एम> एन के साथ एन। दूसरी ओर, जॉकश के सेमीरिकर्सिव समुच्चय जो कि जॉकश द्वारा 1968 में पेश किए जाने से पहले से ही अनौपचारिक रूप से ज्ञात थे एक समुच्चय के उदाहरण हैं जो (m, n)-रिकर्सिव है यदि केवल 2m < n + 1। अनगिनत हैं तो इनमें से कई समुच्चय इस प्रकार के कुछ संगणनीय गणना योग्य परन्तु गैर-गणना योग्य समुच्चय भी है । बाद में, डेग्टेव ने संगणनीय रूप से गणना करने योग्य समुच्चयों का एक पदानुक्रम स्थापित किया जो (1, n + 1)-रिकर्सिव हैं लेकिन (1, n)-रिकर्सिव नहीं हैं। रूसी वैज्ञानिकों द्वारा शोध के एक लंबे चरण के बाद, यह विषय पश्चिम में बेगेल की थीसिस द्वारा बाध्य प्रश्नों पर फिर से लोकप्रिय हो गया, जिसने आवृत्ति संगणना को उपर्युक्त परिबद्ध न्यूनताओं और अन्य संबंधित धारणाओं से जोड़ा। प्रमुख परिणामों में से एक कुमेर की कार्डिनैलिटी थ्योरी थी जिसमें कहा गया है कि एक समुच्चय ए की गणना की जा सकती है अगर और केवल अगर ऐसा एन है कि कुछ एल्गोरिदम इस समुच्चय की प्रमुखता के कई संभावित विकल्पों तक एन अलग-अलग संख्याओं के प्रत्येक टपल के लिए गणना करता है। एन संख्या ए के साथ छेड़छाड़ की; इन विकल्पों में सही प्रमुखता से होनी चाहिए लेकिन कम से कम एक गलत को छोड़ दें।

आगमनात्मक अनुमान

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

ट्यूरिंग संगंणनीयता का सामान्यीकरण

संगंणनीयता सिद्धान्त में इस क्षेत्र की सामान्यीकृत धारणाओं का अध्ययन सम्मिलित है जैसे कि अंकगणित अपचेयता, अंकगणितीय अपचयन और अल्फा पुनरावर्तन सिद्धांत | α-पुनरावर्तन सिद्धांत, जैसा कि 1990 में सैक्स द्वारा वर्णित है।इन सामान्यीकृत धारणाओं में अपचेयक सम्मिलित हैं जिन्हें ट्यूरिंग यंत्रों द्वारा निष्पादित नहीं किया जा सकता है, लेकिन फिर भी ट्यूरिंग अपचेयक के प्राकृतिक सामान्यीकरण हैं। इन अध्ययनों में विश्लेषणात्मक पदानुक्रम की जांच करने के दृष्टिकोण सम्मिलित हैं जो अलग-अलग संख्याओं पर परिमाणीकरण के अतिरिक्त प्राकृतिक संख्याओं के समुच्चय पर परिमाणीकरण की अनुमति देकर अंकगणितीय पदानुक्रम से भिन्न होते हैं। ये क्षेत्र सुव्यवस्था और वृक्षों के सिद्धांतों से जुड़े हुए हैं; उदाहरण के लिए अनंत शाखाओं के बिना संगंणकताल पेड़ों के सभी सूचकांकों का समुच्चय स्तर के लिए पूरा हो गया है $\Pi _{1}^{1}$ विश्लेषणात्मक पदानुक्रम की। प्रभावी वर्णनात्मक समुच्चय सिद्धांत के क्षेत्र में ट्यूरिंग अपचेयता और अत्यंत अंक-सम्बन्धी अपचेयक दोनों ही महत्वपूर्ण हैं। समुच्चय सिद्धान्त में निर्माण की श्रेणी की और भी सामान्य धारणा का अध्ययन किया जाता है।

सतत संगणनीयता सिद्धांत

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

निश्चितता, प्रमाण और संगणनीयता के बीच संबंध

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

संगंणनीयता सिद्धांत दूसरे क्रम अंकगणित से भी जुड़ा हुआ है, प्राकृतिक संख्याओं का औपचारिक सिद्धांत और प्राकृतिक संख्याओं का समुच्चय है। तथ्य यह है कि कुछ समुच्चय संगणनीय या अपेक्षाकृत संगणनीय हैं, इसका अर्थ प्रायः यह होता है कि इन समुच्चयों को दूसरे क्रम के अंकगणित के कमजोर उप-प्रणालियों में परिभाषित किया जा सकता है। प्रतिलोम गणितीय का कार्य इन उप-प्रणाली का उपयोग प्रसिद्ध गणितीय प्रमेयों में निहित गैर-संगंणनीयता को मापने के लिए करता है। 1999 में, सिम्पसन ने दूसरे क्रम के अंकगणित और प्रतिलोम गणित के कई पहलुओं पर चर्चा की।

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

नाम

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

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

व्यावसायिक संगठन

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

यह भी देखें

• पुनरावर्तन (कंप्यूटर विज्ञान)
• संगणनीयता तर्क
• ट्रांसकंप्यूटेशनल समस्या

अग्रिम पठन

Undergraduate level texts

• Cooper, S. Barry (2004). Computability Theory. Chapman & Hall/CRC. ISBN 1-58488-237-9.
• Matiyasevich, Yuri Vladimirovich (1993). Hilbert's Tenth Problem. MIT Press. ISBN 0-262-13295-8.

Advanced texts

• Jain, Sanjay; Osherson, Daniel Nathan; Royer, James S.; Sharma, Arun (1999). Systems that learn: an introduction to learning theory (2nd ed.). Bradford Book / MIT Press. ISBN 0-262-10077-0. LCCN 98-34861.
• Lerman, Manuel (1983). Degrees of unsolvability. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 3-540-12155-2.
• Nies, André (2009). Computability and Randomness. Oxford University Press. ISBN 978-0-19-923076-1.
• Odifreddi, Piergiorgio (1989). Classical Recursion Theory. North-Holland. ISBN 0-444-87295-7.
• Odifreddi, Piergiorgio (1999). Classical Recursion Theory. Vol. II. Elsevier. ISBN 0-444-50205-X.

Survey papers and collections

• Enderton, Herbert Bruce (1977). "Elements of Recursion Theory". In Barwise, Jon (ed.). Handbook of Mathematical Logic. North-Holland. pp. 527–566. ISBN 0-7204-2285-X.

Research papers and collections

• Burgin, Mark; Klinger, Allen (2004). "Experience, Generations, and Limits in Machine Learning". Theoretical Computer Science. 317 (1–3): 71–91. doi:10.1016/j.tcs.2003.12.005.
• Friedberg, Richard M. (1958). "Three theorems on recursive enumeration: I. Decomposition, II. Maximal Set, III. Enumeration without repetition". The Journal of Symbolic Logic. 23 (3): 309–316. doi:10.2307/2964290. JSTOR 2964290. S2CID 25834814.
• Gold, E. Mark (1967). "Language Identification in the Limit" (PDF). Information and Control. 10 (5): 447–474. doi:10.1016/s0019-9958(67)91165-5. [1]
• Jockusch, Carl Groos Jr. (1968). "Semirecursive sets and positive reducibility". Transactions of the American Mathematical Society. 137 (2): 420–436. doi:10.1090/S0002-9947-1968-0220595-7. JSTOR 1994957.
• Kleene, Stephen Cole; Post, Emil Leon (1954). "The upper semi-lattice of degrees of recursive unsolvability". Annals of Mathematics. Series 2. 59 (3): 379–407. doi:10.2307/1969708. JSTOR 1969708.
• Myhill, John R. Sr. (1956). "The lattice of recursively enumerable sets". The Journal of Symbolic Logic. 21: 215–220. doi:10.1017/S002248120008525X. S2CID 123260425.
• Post, Emil Leon (1947). "Recursive unsolvability of a problem of Thue". Journal of Symbolic Logic. 12 (1): 1–11. doi:10.2307/2267170. JSTOR 2267170. S2CID 30320278. Reprinted in Davis 1965.

बाहरी संबंध

• Association for Symbolic Logic homepage
• Computability in Europe homepage
• Webpage on Recursion Theory Course at Graduate Level with approximately 100 pages of lecture notes
• German language lecture notes on inductive inference