संगणनीयता सिद्धांत: Difference between revisions

Latest revision as of 11:29, 15 September 2023

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

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

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

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

परिचय

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

^[1]

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

अन्य कमी

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

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

एक-एक कमी: 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 में, सिम्पसन^[17]कार्यक्रम की विस्तृत चर्चा भी की। प्रश्न में समुच्चय-अस्तित्व के स्वयंसिद्ध अनौपचारिक रूप से स्वयंसिद्धों के अनुरूप होते हैं, जो कहते हैं कि प्राकृतिक संख्याओं की शक्तियाँ विभिन्न न्यूनीकरण धारणाओं के अनुसार बंद हैं। प्रतिलोम गणित में अध्ययन किया गया सबसे दुर्बल स्वयंसिद्ध पुनरावर्त समझौता है, जो बताता है कि ट्यूरिंग अपचेयक के तहत प्राकृतिक सत्ता स्थापित को बंद कर दिया गया है।

संख्यांकन

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

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

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

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

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

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

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

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

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

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

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

आवृत्ति गणना

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

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

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

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

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

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

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

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

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

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

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

नाम

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

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

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

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

यह भी देखें

↑ Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.
↑ The homepage of André Nies has a list of open problems in Kolmogorov complexity.
↑ MathSciNet searches for the titles like "computably enumerable" and "c.e." show that many papers have been published with this terminology as well as with the other one.

संदर्भ

↑ Radó, Tibor (May 1962). "On non-computable functions". Bell System Technical Journal. 41 (3): 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.
↑ Soare, Robert Irving (2011-12-22). "Computability Theory and Applications: The Art of Classical Computability" (PDF). Department of Mathematics. University of Chicago. Archived (PDF) from the original on 2022-06-30. Retrieved 2017-08-23.
↑ ^3.0 ^3.1 Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. pp. 300, 376. ISBN 0-7204-2103-9.
↑ ^4.0 ^4.1 Davis, Martin, ed. (2004) [1965]. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Dover Publications, Inc. p. 84. ISBN 978-0-486-43228-1. p. 84: Kurt Gödel (1946): Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen.
↑ Church, Alonzo (1936a). "An unsolvable problem of elementary number theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. Reprinted in Davis 1965.
↑ Church, Alonzo (1936b). "A note on the Entscheidungsproblem". Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. S2CID 42323521. Reprinted in Davis 1965.
↑ ^7.0 ^7.1 Turing, Alan Mathison (1937) [1936]. "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2: 42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. Turing, Alan Mathison (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction" (PDF). Proceedings of the London Mathematical Society. Series 2: 43 (1): 544–546. doi:10.1112/plms/s2-43.6.544. Archived (PDF) from the original on 2022-07-18. Retrieved 2022-08-08. Reprinted in Davis 1965.
↑ Gödel, Kurt (1990). "[Gödel (1946)]". In Feferman, Solomon; et al. (eds.). Kurt Gödel Publications 1938–1974 Volume II. Vol. II. New York, USA: Oxford University Press. pp. 144ff. ISBN 978-0-19-514721-6. p. 150: To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function f is called computable in S if there is in S a computable term representing f. (NB. This volume also includes the 1946 paper by Kurt Gödel (with commentary by Charles Parsons at pp. 144ff.). This 1990 edition has the cited footnote added by Gödel on p. 150 (which had also been added to Gödel's reprint in Davis' 1965 compilation).)
↑ Ershov, Yury Leonidovich; Goncharov, Sergei Savostyanovich [at Wikidata]; Nerode, Anil; Remmel, Jeffrey B. (1998). Handbook of Recursive Mathematics. North-Holland. ISBN 0-7204-2285-X.
↑ Cutland, Nigel J. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 0-521-29465-7.
↑ ^11.0 ^11.1 Soare, Robert Irving (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 0-387-15299-7.
↑ ^12.0 ^12.1 Soare, Robert Irving (1996). "Computability and recursion" (PDF). Bulletin of Symbolic Logic. 2 (3): 284–321. doi:10.2307/420992. JSTOR 420992. S2CID 5894394.
↑ Turing, Alan Mathison (1939). "Systems of logic based on ordinals". Proceedings of the London Mathematical Society. Series 2: 45 (1): 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. Reprinted in Davis 1965.
↑ Shore, Richard Arnold; Slaman, Theodore Allen (1999). "Defining the Turing Jump". Mathematical Research Letters. 6 (6): 711–722. doi:10.4310/mrl.1999.v6.n6.a10. ISSN 1073-2780. MR 1739227.
↑ ^15.0 ^15.1 Ambos-Spies, Klaus [at Wikidata]; Fejer, Peter A. (2006). "Degrees of Unsolvability" (PDF). Archived from the original (PDF) on 2013-04-20. Retrieved 2006-10-27. Unpublished preprint.
↑ ^16.0 ^16.1 Post, Emil Leon (1944). "Recursively enumerable sets of positive integers and their decision problems". Bulletin of the American Mathematical Society. 50 (5): 284–316. doi:10.1090/S0002-9904-1944-08111-1. MR 0010514. Reprinted in Davis 1965.
↑ ^17.0 ^17.1 Simpson, Steven George (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN 3-540-64882-8.
↑ Harrington, Leo Anthony; Soare, Robert Irving (1991). "Post's Program and incomplete recursively enumerable sets". Proceedings of the National Academy of Sciences USA. 88 (22): 10242–10246. Bibcode:1991PNAS...8810242H. doi:10.1073/pnas.88.22.10242. PMC 52904. PMID 11607241.
↑ Soare, Robert Irving (1974). "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets". Annals of Mathematics. 100 (1): 80–120. doi:10.2307/1970842. JSTOR 1970842.
↑ Slaman, Theodore Allen; Woodin, William Hugh (1986). "Definability in the Turing degrees". Illinois Journal of Mathematics. 30 (2): 320–334. doi:10.1215/ijm/1256044641. MR 0840131.
↑ Conference on Logic, Computability and Randomness, 2007-01-13 [2007-01-11], archived from the original on 2007-12-26
↑ Sacks, Gerald Enoch (1990). Higher Recursion Theory. Springer-Verlag. ISBN 3-540-19305-7.
↑ Orponen, Pekka (1997). "A survey of continuous-time computation theory". Advances in Algorithms, Languages, and Complexity: 209–224. CiteSeerX 10.1.1.53.1991. doi:10.1007/978-1-4613-3394-4_11. ISBN 978-1-4613-3396-8.
↑ Moore, Cris (1996). "Recursion theory on the reals and continuous-time computation". Theoretical Computer Science. 162 (1): 23–44. CiteSeerX 10.1.1.6.5519. doi:10.1016/0304-3975(95)00248-0.
↑ Fairtlough, Matt; Wainer, Stanley S. (1998). "Hierarchies of Provably Recursive Functions". In Buss, Samuel R. (ed.). Handbook of Proof Theory. Elsevier. pp. 149–208. ISBN 978-0-08-053318-6.
↑ Fortnow, Lance Jeremy (2004-02-15). "Is it Recursive, Computable or Decidable?". Archived from the original on 2022-08-07. Retrieved 2018-03-22.
↑ Simpson, Stephen George (1998-08-24). "What is computability theory?". FOM email list. Archived from the original on 2021-12-18. Retrieved 2006-01-09.
↑ Friedman, Harvey (1998-08-28). "Renaming recursion theory". FOM email list. Archived from the original on 2022-03-01. Retrieved 2006-01-09.
↑ Rogers, Hartley Jr. (1987). The Theory of Recursive Functions and Effective Computability (2nd ed.). MIT Press. ISBN 0-262-68052-1.{{cite book}}: CS1 maint: ref duplicates default (link)

अग्रिम पठन

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.

बाहरी संबंध

[NB_Davis_1965-3] Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.

[NB_Nies-23] The homepage of André Nies has a list of open problems in Kolmogorov complexity.

[NB_MathSciNet-28] MathSciNet searches for the titles like "computably enumerable" and "c.e." show that many papers have been published with this terminology as well as with the other one.

[Rado_1962-1] Radó, Tibor (May 1962). "On non-computable functions". Bell System Technical Journal. 41 (3): 877–884. doi:10.1002/j.1538-7305.1962.tb00480.x.

[Soare_2011-2] Soare, Robert Irving (2011-12-22). "Computability Theory and Applications: The Art of Classical Computability" (PDF). Department of Mathematics. University of Chicago. Archived (PDF) from the original on 2022-06-30. Retrieved 2017-08-23.

[Kleene_1952-4] 3.0 ^3.1 Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. pp. 300, 376. ISBN 0-7204-2103-9.

[Davis_1965-5] 4.0 ^4.1 Davis, Martin, ed. (2004) [1965]. The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions. Dover Publications, Inc. p. 84. ISBN 978-0-486-43228-1. p. 84: Kurt Gödel (1946): Tarski has stressed in his lecture (and I think justly) the great importance of the concept of general recursiveness (or Turing's computability). It seems to me that this importance is largely due to the fact that with this concept one has for the first time succeeded in giving an absolute notion to an interesting epistemological notion, i.e., one not depending on the formalism chosen.

[Church_1936a-6] Church, Alonzo (1936a). "An unsolvable problem of elementary number theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. Reprinted in Davis 1965.

[Church_1936b-7] Church, Alonzo (1936b). "A note on the Entscheidungsproblem". Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. S2CID 42323521. Reprinted in Davis 1965.

[Turing_1936-8] 7.0 ^7.1 Turing, Alan Mathison (1937) [1936]. "On computable numbers, with an application to the Entscheidungsproblem". Proceedings of the London Mathematical Society. Series 2: 42 (1): 230–265. doi:10.1112/plms/s2-42.1.230. S2CID 73712. Turing, Alan Mathison (1938). "On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction" (PDF). Proceedings of the London Mathematical Society. Series 2: 43 (1): 544–546. doi:10.1112/plms/s2-43.6.544. Archived (PDF) from the original on 2022-07-18. Retrieved 2022-08-08. Reprinted in Davis 1965.

[Feferman_1990-9] Gödel, Kurt (1990). "[Gödel (1946)]". In Feferman, Solomon; et al. (eds.). Kurt Gödel Publications 1938–1974 Volume II. Vol. II. New York, USA: Oxford University Press. pp. 144ff. ISBN 978-0-19-514721-6. p. 150: To be more precise: a function of integers is computable in any formal system containing arithmetic if and only if it is computable in arithmetic, where a function f is called computable in S if there is in S a computable term representing f. (NB. This volume also includes the 1946 paper by Kurt Gödel (with commentary by Charles Parsons at pp. 144ff.). This 1990 edition has the cited footnote added by Gödel on p. 150 (which had also been added to Gödel's reprint in Davis' 1965 compilation).)

[Ershov-Goncharov-Nerode-Remmel-1998-10] Ershov, Yury Leonidovich; Goncharov, Sergei Savostyanovich [at Wikidata]; Nerode, Anil; Remmel, Jeffrey B. (1998). Handbook of Recursive Mathematics. North-Holland. ISBN 0-7204-2285-X.

[Cutland_1980-11] Cutland, Nigel J. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 0-521-29465-7.

[Soare_1987-12] 11.0 ^11.1 Soare, Robert Irving (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 0-387-15299-7.

[Soare_1996-13] 12.0 ^12.1 Soare, Robert Irving (1996). "Computability and recursion" (PDF). Bulletin of Symbolic Logic. 2 (3): 284–321. doi:10.2307/420992. JSTOR 420992. S2CID 5894394.

[Turing_1939-14] Turing, Alan Mathison (1939). "Systems of logic based on ordinals". Proceedings of the London Mathematical Society. Series 2: 45 (1): 161–228. doi:10.1112/plms/s2-45.1.161. hdl:21.11116/0000-0001-91CE-3. Reprinted in Davis 1965.

[Shore-Slaman_1999-15] Shore, Richard Arnold; Slaman, Theodore Allen (1999). "Defining the Turing Jump". Mathematical Research Letters. 6 (6): 711–722. doi:10.4310/mrl.1999.v6.n6.a10. ISSN 1073-2780. MR 1739227.

[Ambos-Spies-Fejer_2006-16] 15.0 ^15.1 Ambos-Spies, Klaus [at Wikidata]; Fejer, Peter A. (2006). "Degrees of Unsolvability" (PDF). Archived from the original (PDF) on 2013-04-20. Retrieved 2006-10-27. Unpublished preprint.

[Post_1944-17] 16.0 ^16.1 Post, Emil Leon (1944). "Recursively enumerable sets of positive integers and their decision problems". Bulletin of the American Mathematical Society. 50 (5): 284–316. doi:10.1090/S0002-9904-1944-08111-1. MR 0010514. Reprinted in Davis 1965.

[Simpson_1999-18] 17.0 ^17.1 Simpson, Steven George (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN 3-540-64882-8.

[Harrington-Soare_1991-19] Harrington, Leo Anthony; Soare, Robert Irving (1991). "Post's Program and incomplete recursively enumerable sets". Proceedings of the National Academy of Sciences USA. 88 (22): 10242–10246. Bibcode:1991PNAS...8810242H. doi:10.1073/pnas.88.22.10242. PMC 52904. PMID 11607241.

[Soare_1974-20] Soare, Robert Irving (1974). "Automorphisms of the lattice of recursively enumerable sets, Part I: Maximal sets". Annals of Mathematics. 100 (1): 80–120. doi:10.2307/1970842. JSTOR 1970842.

[Slaman-Woodin_1986-21] Slaman, Theodore Allen; Woodin, William Hugh (1986). "Definability in the Turing degrees". Illinois Journal of Mathematics. 30 (2): 320–334. doi:10.1215/ijm/1256044641. MR 0840131.

[Logic_2007-22] Conference on Logic, Computability and Randomness, 2007-01-13 [2007-01-11], archived from the original on 2007-12-26

[Sacks_1990-24] Sacks, Gerald Enoch (1990). Higher Recursion Theory. Springer-Verlag. ISBN 3-540-19305-7.

[Orponen_1997-25] Orponen, Pekka (1997). "A survey of continuous-time computation theory". Advances in Algorithms, Languages, and Complexity: 209–224. CiteSeerX 10.1.1.53.1991. doi:10.1007/978-1-4613-3394-4_11. ISBN 978-1-4613-3396-8.

[Moore_1996-26] Moore, Cris (1996). "Recursion theory on the reals and continuous-time computation". Theoretical Computer Science. 162 (1): 23–44. CiteSeerX 10.1.1.6.5519. doi:10.1016/0304-3975(95)00248-0.

[Fairtlough-Wainer_1998-27] Fairtlough, Matt; Wainer, Stanley S. (1998). "Hierarchies of Provably Recursive Functions". In Buss, Samuel R. (ed.). Handbook of Proof Theory. Elsevier. pp. 149–208. ISBN 978-0-08-053318-6.

[Fortnow_2004-29] Fortnow, Lance Jeremy (2004-02-15). "Is it Recursive, Computable or Decidable?". Archived from the original on 2022-08-07. Retrieved 2018-03-22.

[Simpson_1998-30] Simpson, Stephen George (1998-08-24). "What is computability theory?". FOM email list. Archived from the original on 2021-12-18. Retrieved 2006-01-09.

[Friedman_1998-31] Friedman, Harvey (1998-08-28). "Renaming recursion theory". FOM email list. Archived from the original on 2022-03-01. Retrieved 2006-01-09.

[Rogers_1987-32] Rogers, Hartley Jr. (1987). The Theory of Recursive Functions and Effective Computability (2nd ed.). MIT Press. ISBN 0-262-68052-1.{{cite book}}: CS1 maint: ref duplicates default (link)

[1]

[2]

[nb 1]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[nb 2]

[22]

[23]

[24]

[25]

[nb 3]

[26]

[27]

[28]

[29]

@@ Line 1: / Line 1: @@
-{{short description|Study of computable functions and Turing degrees}}
+संगणनीयता सिद्धांत, जिसे पुनरावर्तन सिद्धांत के रूप में भी जाना जाता है, [[गणितीय तर्क]], [[कंप्यूटर विज्ञान|विज्ञान]] और संगणन के सिद्धांत की शाखा है, जिसकी उत्पत्ति 1930 के दशक में संगणनीय कार्यों और ट्यूरिंग श्रेणी के अध्ययन के साथ हुई थी। सामान्यीकृत संगणनीयता और [[निश्चित सेट|निश्चित श्रेणी]] के अध्ययन को सम्मिलित करने के लिए इस क्षेत्र का विस्तार हुआ है। इन क्षेत्रों में, संगणनीयता सिद्धांत, प्रमाण सिद्धांत और [[प्रभावी वर्णनात्मक सेट सिद्धांत|प्रभावी वर्णनात्मक समुच्चय सिद्धांत]] अधिव्यापित होता है।
-{{for|संगणनीयता का सिद्धांत के लिए |संगणनीयता}}
-संगणनीयता सिद्धांत, जिसे पुनरावर्तन सिद्धांत के रूप में भी जाना जाता है, [[गणितीय तर्क]], [[कंप्यूटर विज्ञान]] और संगणन के सिद्धांत की एक शाखा है, जिसकी उत्पत्ति 1930 के दशक में संगणनीय कार्यों और ट्यूरिंग डिग्री के अध्ययन के साथ हुई थी। सामान्यीकृत संगणनीयता और [[निश्चित सेट|निश्चित श्रेणी]] के अध्ययन को शामिल करने के लिए इस क्षेत्र का विस्तार हुआ है। इन क्षेत्रों में, संगणनीयता सिद्धांत प्रमाण सिद्धांत और [[प्रभावी वर्णनात्मक सेट सिद्धांत]] के साथ अधिव्यापित होता है।
+[[कम्प्यूटेबिलिटी|संगणनीयता]] सिद्धांत द्वारा संबोधित आधारभूत प्रश्नों में निम्नलिखित प्रश्न सम्मिलित हैं:
+* [[प्राकृतिक संख्या]]ओं के फलन का गणनीय  होने का क्या अर्थ है?
-[[कम्प्यूटेबिलिटी|संगणनीयता]] सिद्धांत द्वारा संबोधित बुनियादी प्रश्नों में निम्नलिखित प्रश्न सम्मिलित हैं:
-* [[प्राकृतिक संख्या]]ओं के फलन का गणना योग्य होने का क्या अर्थ है?
 * गैर-संगणनीय फलनों  को उनके गैर-संगणनीयता के स्तर के आधार पर पदानुक्रम में कैसे वर्गीकृत किया जा सकता है?
-यद्यपि ज्ञान और विधियों के संदर्भ में काफी अधिव्यापन है, गणितीय संगणनीयता सिद्धांतवादी सापेक्ष संगणनीयता, न्यूनीकरण धारणाओं और डिग्री संरचनाओं के सिद्धांत का अध्ययन करते हैं; कंप्यूटर विज्ञान क्षेत्र के लोग [[कम्प्यूटेशनल जटिलता सिद्धांत|संगंणकताल जटिलता सिद्धांत]], औपचारिक तरीकों और [[औपचारिक भाषा]]ओं के सिद्धांत पर ध्यान केंद्रित करते हैं।
+यद्यपि ज्ञान और विधियों के संदर्भ में पर्याप्त अधिव्यापन है, गणितीय संगणक सिद्धांतवादी सापेक्ष संगणनीयता, न्यूनीकरण धारणाओं और श्रेणी संरचनाओं के सिद्धांत का अध्ययन करते हैं;  संगणक विज्ञान क्षेत्र के लोग [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]], औपचारिक विधि और [[औपचारिक भाषा]]ओं के सिद्धांत पर ध्यान केंद्रित करते हैं।
 == परिचय ==
-{{use list-defined references|date=August 2022}}
 {| class="wikitable floatright"
 |-
@@ Line 33: / Line 30: @@
 |-
 | colspan="8" {{COther}}व्यस्त बीवर कार्य किसी भी संगणनीय कार्य की तुलना में तेज़ी से बढ़ता है।इसलिए, यह गणना योग्य नहीं है;केवल कुछ ही मान ज्ञात हैं।
-|}
+|}<ref name="Rado_1962"/>
-अनुकूलता सिद्धांत की उत्पत्ति 1930 के दशक में कर्ट गोडेल, [[अलोंजो चर्च]], रोजसा पेटर, [[एलन ट्यूरिंग]], [[स्टीफन क्लेन]] और [[एमिल पोस्ट]] के काम से हुई थी।<ref name="Soare_2011"/><ref group="nb" name="NB_Davis_1965"/>
+संगणनीयता सिद्धांत की उत्पत्ति 1930 के दशक में कर्ट गोडेल, [[अलोंजो चर्च]], रोजसा पेटर, [[एलन ट्यूरिंग]], [[स्टीफन क्लेन]] और [[एमिल पोस्ट]] के कार्य से हुई थी।<ref name="Soare_2011"/><ref group="nb" name="NB_Davis_1965"/>
-शोधकर्ताओं ने मूलभूत परिणामों को प्रभावी गणना के अनौपचारिक विचार के सही औपचारिकता के रूप में स्थापित गणना योग्य कार्य के रूप में प्राप्त किया। 1952 में, इन परिणामों ने क्लेन को चर्च की थीसिस के दो नामों को रचने के लिए प्रेरित किया<ref name="Kleene_1952"/>{{rp|page=300}} और ट्यूरिंग की थीसिस।<ref name="Kleene_1952"/>{{rp|page=376}} आजकल इन्हें अक्सर एकल परिकल्पना, चर्च-ट्यूरिंग थीसिस के रूप में माना जाता है, जिसमें कहा गया है कि कोई भी कार्य जो [[कलन विधि]] द्वारा गणना योग्य है। यद्यपि आरम्भ में संदेह था,परन्तु 1946 तक गोडेल ने इस थीसिस के पक्ष में तर्क दिया:<!-- <ref name="Gödel_1946"/> --><ref name="Davis_1965"/>{{rp|page=84}}
+शोधकर्ताओं ने आधारभूत परिणामों को प्रभावी गणना के अनौपचारिक विचार को औपचारिक रूप में गणनीय कार्य के रूप में प्राप्त किया। 1952 में, इन परिणामों ने क्लेन को दो नामों का सृजन करने के लिए प्रेरित किया पहला 'चर्च की अभिधारणा' <ref name="Kleene_1952"/> और दूसरा 'ट्यूरिंग की अभिधारणा'।<ref name="Kleene_1952"/> प्रायः एकल परिकल्पना को चर्च-ट्यूरिंग अभिधारणा के रूप में जाना जाता है, जिसमें कहा गया है कि कोई भी फलन जो [[कलन विधि|कलनविधि]] द्वारा गणनीय है,संगणनीय फलन होगा। यद्यपि आरम्भ में संदेह था,परन्तु 1946 तक गोडेल ने संगणनीयता की अभिधारणा के पक्ष में तर्क दिया:<ref name="Davis_1965"/>
-{{blockquote|अल्फ्रेड टार्स्की ने अपने व्याख्यान में सामान्य पुनरावर्तीता (या ट्यूरिंग की कम्प्यूटेबिलिटी) की अवधारणा के महान महत्व पर जोर दिया है और मुझे लगता है कि यह उचित है। मुझे ऐसा लगता है कि यह महत्व काफी हद तक इस तथ्य के कारण है कि इस अवधारणा के साथ पहली बार एक दिलचस्प ज्ञानशास्त्रीय धारणा को एक पूर्ण धारणा देने में सफलता मिली है, यानी, जो औपचारिकता पर निर्भर नहीं है।}}
+{{blockquote|अल्फ्रेड टार्सकी ने अपने व्याख्यान में सामान्य पुनरावर्ती की अवधारणा के महान महत्व पर जोर दिया है और मुझे लगता है कि यह उचित है। मुझे ऐसा लगता है कि यह महत्व अत्यधिक सीमा तक इस तथ्य के कारण है की अवधारणा के साथ पहली बार एक रोचक  ज्ञानशास्त्रीय धारणा को एक पूर्ण धारणा देने में सफलता मिली है जो औपचारिकता पर निर्भर नहीं है।}}
-प्रभावी गणना की परिभाषा के साथ पहला प्रमाण आया कि गणित में ऐसी समस्याएं हैं जिन्हें [[पुनरावर्ती सेट]] नहीं किया जा सकता है। 1936 में, चर्च<ref name="Church_1936a"/><ref name="Church_1936b"/>और ट्यूरिंग<ref name="Turing_1936"/>गोडेल द्वारा अपनी अपूर्णता प्रमेयों को साबित करने के लिए उपयोग की जाने वाली तकनीकों से प्रेरित थे - 1931 में, गोडेल ने स्वतंत्र रूप से प्रदर्शित किया कि {{lang|de|एंट्सचिडंगस्प्रोब्लेम}} प्रभावी ढंग से निर्णय लेने योग्य नहीं है। इस परिणाम ने दिखाया कि कोई एल्गोरिथम प्रक्रिया नहीं है जो सही ढंग से तय कर सके कि मनमाने गणितीय प्रस्ताव सही हैं या गलत।
+प्रभावी गणना की परिभाषा के साथ पहला प्रमाण आया कि गणित में ऐसी समस्याएं हैं जिन्हें [[पुनरावर्ती सेट|पुनरावर्ती समुच्चय]] द्वारा हल नहीं किया जा सकता है। 1936 में, चर्च<ref name="Church_1936a"/><ref name="Church_1936b"/>और ट्यूरिंग<ref name="Turing_1936"/>गोडेल द्वारा अपनी अपूर्णता प्रमेयों को प्रमाणित करने के लिए उपयोग की जाने वाली तकनीकों से प्रेरित थे - 1931 में, गोडेल ने स्वतंत्र रूप से प्रदर्शित किया कि {{lang|de|एंट्सचिडंगस्प्रोब्लेम}} प्रभावी ढंग से निर्णय लेने योग्य नहीं है। इस परिणाम ने प्रदर्शित कि कोई कलन विधि प्रक्रिया नहीं है जो सही ढंग से तय कर सके कि यादृच्छिक गणितीय प्रस्ताव सही हैं या गलत।<!-- <ref name="Gödel_1946"/> --><ref name="Davis_1965"/>{{rp|page=84}}<ref name="Feferman_1990"/>}}
-इन प्रारंभिक उदाहरणों को स्थापित करने के पश्चात गणित में अनेको समस्याओं को अनिर्णीत दिखाया गया है। 1947 में, एंड्री मार्कोव जूनियर और पोस्ट ने स्वतंत्र पत्र प्रकाशित किए, जिसमें दिखाया गया कि सेमीग्रुप के लिए शब्द समस्या प्रभावी ढंग से तय नहीं की जा सकती। इस परिणाम का विस्तार करते हुए, [[पीटर नोविकोव]] और विलियम बून (गणितज्ञ) ने 1950 के दशक में स्वतंत्र रूप से दिखाया कि समूहों के लिए शब्द समस्या प्रभावी रूप से हल करने योग्य नहीं है और न ही कोई प्रभावी प्रक्रिया है, जो एक अंतिम रूप से प्रस्तुत [[समूह (गणित)|समूह]] में एक शब्द दिया गया हो, यह तय करेगा कि क्या शब्द द्वारा दर्शाया गया तत्व समूह का [[पहचान तत्व]] है। 1970 में, यूरी मटियासेविच ने [[जूलिया रॉबिन्सन]] के परिणामों का उपयोग करके मटियासेविच के प्रमेय को साबित किया, जिसका अर्थ है कि हिल्बर्ट की दसवीं समस्या का कोई प्रभावी समाधान नहीं है; इस समस्या के पश्चात उन्होंने पूछा कि क्या यह तय करने के लिए एक प्रभावी प्रक्रिया है कि क्या पूर्णांकों पर एक [[डायोफैंटाइन समीकरण]] का पूर्णांकों में समाधान है। [[अनिर्णीत समस्याओं की सूची]] समस्याओं के अतिरिक्त उदाहरण देती है जिनका कोई संगणनीय समाधान नहीं है।
+इन प्रारंभिक उदाहरणों को स्थापित करने के पश्चात गणित में अनेको समस्याओं को अनिर्णीत प्रदर्शित किया गया है। 1947 में, एंड्री मार्कोव जूनियर और पोस्ट ने स्वतंत्र पत्र प्रकाशित किए, जिसमें प्रदर्शित किया कि उपसमूह के लिए शब्द समस्या प्रभावी ढंग से तय नहीं की जा सकती। इस परिणाम का विस्तार करते हुए, [[पीटर नोविकोव]] और विलियम बून ने 1950 के दशक में स्वतंत्र रूप से प्रदर्शित कि समूहों के लिए शब्द समस्या प्रभावी रूप से हल करने योग्य नहीं है और न ही कोई प्रभावी प्रक्रिया है जो अंतिम रूप से प्रस्तुत [[समूह (गणित)|समूह]] में एक शब्द दिया हो, यह तय करे कि क्या शब्द द्वारा दर्शाया गया तत्व समूह का [[पहचान तत्व]] है। 1970 में, यूरी मटियासेविच ने [[जूलिया रॉबिन्सन]] के परिणामों का उपयोग करके मटियासेविच के प्रमेय को प्रमाणित किया, जिसका अर्थ है कि हिल्बर्ट की दसवीं समस्या का कोई प्रभावी समाधान नहीं है; इस समस्या के पश्चात उन्होंने पूछा कि क्या यह तय करने के लिए कोई प्रभावी प्रक्रिया है। [[अनिर्णीत समस्याओं की सूची]] अतिरिक्त उदाहरण देती है जिनका कोई संगणनीय समाधान नहीं है।
-जिन गणितीय रचनाओं का अध्ययन प्रभावी ढंग से किया जा सकता है, उन्हें कभी-कभी पुनरावर्ती गणित कहा जाता है; ''पुनरावर्ती गणित की पुस्तिका''<ref name="Ershov-Goncharov-Nerode-Remmel-1998"/>इस क्षेत्र में कई ज्ञात परिणामों को शामिल करता है।
+जिन गणितीय रचनाओं का अध्ययन प्रभावी ढंग से किया जा सकता है, उन्हें कभी-कभी पुनरावर्ती गणित कहा जाता है;<ref name="Ershov-Goncharov-Nerode-Remmel-1998"/>इस क्षेत्र में कई ज्ञात परिणामों को सम्मिलित किया गया है।
 == ट्यूरिंग संगंणनीयता ==
-संगंणनीयता सिद्धांत में अध्ययन की गई संगंणनीयता का मुख्य रूप 1936 ई. में ट्यूरिंग द्वारा प्रस्तुत किया गया था।<ref name="Turing_1936"/>प्राकृतिक संख्याओं के एक सेट को संगणनीय सेट कहा जाता है, जिसे एक निर्णायक पुनरावर्ती, या ट्यूरिंग [[गणना योग्य सेट]] भी कहा जाता है। यदि कोई ट्यूरिंग मशीन है, जिसे संख्या n दी गई है, आउटपुट 1 के साथ रुकता है यदि n सेट में है और रुकता है एवं आउटपुट 0 के साथ यदि n सेट में नहीं है। प्राकृतिक संख्याओं से प्राकृतिक संख्याओं तक एक कार्य f एक संगंणनीय कार्य या रिकर्सिव कार्य है यदि कोई ट्यूरिंग मशीन है, जो इनपुट n पर रुकती है और आउटपुट f (n) लौटाती है। यहाँ ट्यूरिंग मशीनों का उपयोग आवश्यक नहीं है; संगंणकता के कई अन्य मॉडल हैं जिनकी संगंणन शक्ति ट्यूरिंग मशीनों के समान है; उदाहरण के लिए प्रारंभिक रिकर्सन और μ ऑपरेटर से प्राप्त μ-पुनरावर्ती कार्य।
+संगंणनीयता सिद्धांत में अध्ययन की गई संगंणनीयता का मुख्य रूप 1936 ई. में ट्यूरिंग द्वारा प्रस्तुत किया गया था।<ref name="Turing_1936"/>प्राकृतिक संख्याओं के एक समुच्चय को संगणनीय समुच्चय कहा जाता है, जिसे एक निर्णायक पुनरावर्ती, या ट्यूरिंग [[गणना योग्य सेट|गणनीय समुच्चय]] भी कहा जाता है। यदि कोई ट्यूरिंग यंत्र है, जिसे संख्या n दी गई है, निर्गत 1 के साथ रुकता है यदि n समुच्चय में है और रुकता है एवं निर्गत 0 के साथ यदि n समुच्चय में नहीं है। प्राकृतिक संख्याओं तक कार्य f एक संगंणनीय कार्य या पुनरावर्ती कार्य है यदि कोई ट्यूरिंग यंत्र है, जो निविष्ट n पर रुकती है और निर्गत f (n) लौटाती है। यहाँ ट्यूरिंग यंत्रों का उपयोग आवश्यक नहीं है; संगंणकता के कई अन्य प्रारूप हैं जिनकी संगंणन शक्ति ट्यूरिंग यंत्रों के समान है; उदाहरण के लिए प्रारंभिक पुनरावर्तन और μ संकार्य से प्राप्त μ-पुनरावर्ती कार्य।
-संगणनीय कार्यों और सेटों के लिए शब्दावली पूरी तरह से मानकीकृत नहीं है।
+संगणनीय कार्यों और समुच्चयों के लिए शब्दावली पूरी तरह से मानकीकृत नहीं है।
-μ-पुनरावर्ती कार्यों के साथ-साथ एक अलग परिभाषा के संदर्भ में परिभाषा {{lang|de|रिकर्सिव}} गोडेल द्वारा किए गए कार्यों ने ट्यूरिंग मशीन द्वारा गणना योग्य सेट और कार्यों के लिए पारंपरिक नाम पुनरावर्ती का नेतृत्व किया। निर्णायक शब्द जर्मन शब्द से उपजा है, जिसका उपयोग ट्यूरिंग और अन्य के मूल पत्रों में किया गया था। समकालीन उपयोग में, संगंणनीय कार्य शब्द की विभिन्न परिभाषाएँ हैं: निगेल जे. कटलैंड के अनुसार,<ref name="Cutland_1980"/>यह एक आंशिक पुनरावर्ती कार्य है जो कुछ इनपुट के लिए अपरिभाषित हो सकता है, जबकि रॉबर्ट आई सोरे के अनुसार<ref name="Soare_1987"/>यह कुल पुनरावर्ती समतुल्य एवं सामान्य पुनरावर्ती कार्य है। यह लेख इन सम्मेलनों में से दूसरे का अनुसरण करता है। 1996 में, सोरे ने <ref name="Soare_1996"/>शब्दावली के बारे में अतिरिक्त टिप्पणियाँ दी।
+μ-पुनरावर्ती कार्यों के साथ-साथ एक अलग परिभाषा के संदर्भ में पुनरावर्ती परिभाषा गोडेल द्वारा किए गए कार्यों ने ट्यूरिंग यंत्र द्वारा गणनीय समुच्चय और कार्यों के लिए पारंपरिक नाम पुनरावर्ती का नेतृत्व किया। निर्णायक शब्द की उत्पत्ति जर्मन शब्द से हुई है, जिसका उपयोग ट्यूरिंग और अन्य के मूल पत्रों में किया गया था। समकालीन उपयोग में, संगंणनीय कार्य शब्द की विभिन्न परिभाषाएँ हैं: निगेल जे. कटलैंड के अनुसार,<ref name="Cutland_1980"/>यह एक आंशिक पुनरावर्ती कार्य है जो कुछ निविष्ट के लिए अपरिभाषित हो सकता है, जबकि रॉबर्ट आई सोरे के अनुसार<ref name="Soare_1987"/>यह कुल पुनरावर्ती समतुल्य एवं सामान्य पुनरावर्ती कार्य है। यह लेख इन सम्मेलनों में से दूसरे का अनुसरण करता है। 1996 में, सोरे ने <ref name="Soare_1996"/>शब्दावली के बारे में अतिरिक्त टिप्पणियाँ दी।
-प्राकृतिक संख्याओं का प्रत्येक सेट गणना योग्य नहीं है। [[रुकने की समस्या]], जो इनपुट 0 पर रुकने वाली ट्यूरिंग मशीनों के विवरण का सेट है, एक गैर-गणना योग्य सेट का एक प्रसिद्ध उदाहरण है। कई गैर-गणना योग्य सेटों का अस्तित्व इस तथ्य से अनुसरण करता है कि केवल [[गणनीय सेट]] ट्यूरिंग मशीन हैं, और इस प्रकार केवल गणना करने योग्य कई सेट हैं, लेकिन कैंटर के प्रमेय के अनुसार, प्राकृतिक संख्याओं के सर्वाधिक सेट हैं।
+प्राकृतिक संख्याओं का प्रत्येक समुच्चय गणनीय नहीं है। [[रुकने की समस्या]], जो निविष्ट 0 पर रुकने वाली ट्यूरिंग यंत्रों के विवरण का समुच्चय है, एक गैर-गणनीय समुच्चय का एक प्रसिद्ध उदाहरण है। कई गैर-गणनीय समुच्चयों का अस्तित्व इस तथ्य से अनुसरण करता है कि केवल [[गणनीय सेट|गणनीय समुच्चय]] ट्यूरिंग यंत्र हैं, और इस प्रकार केवल गणना करने योग्य कई समुच्चय हैं, लेकिन कैंटर के प्रमेय के अनुसार, प्राकृतिक संख्याओं के सर्वाधिक समुच्चय हैं।
-यद्यपि लड़खड़ाते हुए समस्या की गणना नहीं की जा सकती है, परन्तु प्रोग्राम के निष्पादन का अनुकरण करना और रुकने वाले प्रोग्रामों की एक अनंत सूची तैयार करना संभव है। इस प्रकार लड़खड़ाते हुए समस्या की  संगंणनीयी इन्युमरेबल सेट संगंणकताली इन्युमरेबल (सी.ई.) सेट का एक उदाहरण है, जो एक सेट है जिसे ट्यूरिंग मशीन द्वारा एन्यूमरेट किया जा सकता है संगंणकताल इन्युमरेबल के लिए अन्य शर्तें रिकर्सिवली इन्युमरेबल और सेमीडिसिडेबल शामिल हैं। समतुल्य रूप से, एक सेट सी.इ है, यदि यह केवल कुछ संगंणकताल कार्य की सीमा है। सी.ई. सेट, यद्यपि सामान्य रूप से निर्णायक नहीं हैं, इसे संगंणनीयता सिद्धांत में विस्तार से अध्ययन किया गया है।
+यद्यपि समस्या की गणना नहीं की जा सकती है, परन्तु कार्य के निष्पादन का अनुकरण करना और रुकने वाले कार्यो की एक अनंत सूची तैयार करना संभव है। इस प्रकार विरामतः समस्या का गणनीय समुच्चय का उदाहरण है, जो एक समुच्चय है जिसे ट्यूरिंग यंत्र द्वारा गिना जा सकता है गणना करने के लिए अन्य शर्तें पुनरावर्ती गणनीयता और अर्धनिर्धारणीय  सम्मिलित हैं। समतुल्य रूप से, एक समुच्चय सी.इ है, यदि यह केवल कुछ गणनीय कार्य की सीमा है।  यद्यपि सामान्य रूप से निर्णायक नहीं हैं परन्तु इसे संगंणनीयता सिद्धांत में विस्तार से अध्ययन किया गया है।
 ==अनुसंधान के क्षेत्र==
-ऊपर वर्णित संगणनीय सेटों और कार्यों के सिद्धांत के साथ आरम्भ करते हुए, संगणनीयता सिद्धांत के क्षेत्र में कई निकट संबंधी विषयों के अध्ययन को शामिल किया गया है। ये अनुसंधान के स्वतंत्र क्षेत्र नहीं हैं: इनमें से प्रत्येक क्षेत्र दूसरों से विचार और परिणाम प्राप्त करता है, और अधिकांश संगंणनीयता सिद्धांतकार उनमें से अधिकांश से परिचित हैं।
+ऊपर वर्णित संगणनीय समुच्चयों और कार्यों के सिद्धांत के साथ आरम्भ करते हुए, संगणनीयता सिद्धांत के क्षेत्र में कई निकट संबंधी विषयों के अध्ययन को सम्मिलित किया गया है। ये अनुसंधान के स्वतंत्र क्षेत्र नहीं हैं: इनमें से प्रत्येक क्षेत्र दूसरों से विचार और परिणाम प्राप्त करता है, और अधिकांश संगंणनीयता सिद्धांतकार उनमें से अधिकांश परिचित हैं।
-=== सापेक्ष संगणनीयता और ट्यूरिंग डिग्री ===
+=== सापेक्ष संगणनीयता और ट्यूरिंग श्रेणी ===
-{{Main|Turing reduction|Turing degree}}
+{{Main|ट्यूरिंग परिवर्तन |ट्यूरिंग श्रेणी}}
-गणितीय तर्क में संगणनीयता सिद्धांत परंपरागत रूप से सापेक्ष संगणनीयता पर केंद्रित रहा है, 1939 में ट्यूरिंग द्वारा शुरू की गई [[ओरेकल ट्यूरिंग मशीन]]ों का उपयोग करके परिभाषित ट्यूरिंग संगणना का एक सामान्यीकरण।<ref name="Turing_1939"/>एक ऑरेकल ट्यूरिंग मशीन एक काल्पनिक उपकरण है, जो एक नियमित ट्यूरिंग मशीन के कार्यों को करने के अलावा, एक ऑरेकल के प्रश्न पूछने में सक्षम है, जो कि प्राकृतिक संख्याओं का एक विशेष सेट है। ऑरैकल मशीन केवल फॉर्म के प्रश्न पूछ सकती है क्या एन ऑरैकल सेट में है? . प्रत्येक प्रश्न का तुरंत सही उत्तर दिया जाएगा, भले ही ऑरेकल सेट गणना योग्य न हो। इस प्रकार एक गैर-कम्प्यूटेबल ऑरेकल के साथ एक ऑरेकल मशीन सेट की गणना करने में सक्षम होगी जो एक ऑरेकल के बिना ट्यूरिंग मशीन नहीं कर सकती।
+गणितीय तर्क में संगणनीयता सिद्धांत परंपरागत रूप से सापेक्ष संगणनीयता पर केंद्रित रहा है, 1939 में ट्यूरिंग द्वारा प्रारम्भ की गई [[ओरेकल ट्यूरिंग मशीन|ओरेकल ट्यूरिंग यंत्रो]] का उपयोग करके परिभाषित ट्यूरिंग संगणना का सामान्यीकरण भी किया गया।<ref name="Turing_1939"/> ऑरेकल ट्यूरिंग यंत्र एक काल्पनिक उपकरण है, जो एक नियमित ट्यूरिंग यंत्र के कार्यों को करने के अतिरिक्त, एक ऑरेकल के प्रश्न पूछने में सक्षम है, जो कि प्राकृतिक संख्याओं का एक विशेष समुच्चय है। ऑरैकल यंत्र केवल फॉर्म के प्रश्न पूछ सकती है क्या एन ऑरैकल समुच्चय में है? . प्रत्येक प्रश्न का तुरंत सही उत्तर दिया जाएगा, भले ही ऑरेकल समुच्चय गणनीय न हो। इस प्रकार एक गैर-संगणनीय ऑरेकल के साथ ऑरेकल यंत्र समुच्चय की गणना करने में सक्षम होगी जो ऑरेकल के बिना ट्यूरिंग यंत्र नहीं कर सकती।
-अनौपचारिक रूप से, प्राकृतिक संख्या ए का एक सेट एक सेट बी के लिए ट्यूरिंग रिड्यूसिबल है यदि कोई ऑरैकल मशीन है जो सही ढंग से बताती है कि बी के साथ ऑरेकल सेट के रूप में चलाए जाने पर संख्याएं ए में हैं या नहीं (इस मामले में, सेट ए को भी कहा जाता है) (अपेक्षाकृत) बी से गणना योग्य और बी में पुनरावर्ती)। यदि एक सेट A, एक सेट B के लिए ट्यूरिंग रिड्यूसिबल है और B, A के लिए ट्यूरिंग रिड्यूसिबल है, तो कहा जाता है कि सेट में समान ट्यूरिंग डिग्री होती है (जिसे अनसॉल्वेबिलिटी की डिग्री भी कहा जाता है)। एक सेट की ट्यूरिंग डिग्री एक सटीक माप देती है कि सेट कितना अगणनीय है।
+अनौपचारिक रूप से, प्राकृतिक संख्या ए का एक समुच्चय एक समुच्चय बी के लिए ट्यूरिंग रिड्यूसिबल है यदि कोई ऑरैकल यंत्र है जो सही ढंग से बताती है कि बी के साथ ऑरेकल समुच्चय के रूप में चलाए जाने पर संख्याएं ए में हैं या नहीं, इस मामले में, समुच्चय ए को भी कहा जाता है अपेक्षाकृत बी से गणनीय और बी में पुनरावर्ती। यदि एक समुच्चय A, एक समुच्चय B के लिए ट्यूरिंग कम करने योग्य है और B, A के लिए ट्यूरिंग कम करने योग्य है, तो कहा जाता है कि समुच्चय में समान ट्यूरिंग श्रेणी होती है जिसे अघुलनशीलता की श्रेणी भी कहा जाता है। विरामतः समुच्चय की ट्यूरिंग श्रेणी सटीक माप देती है कि समुच्चय कितना अगणनीय है।
-सेट के प्राकृतिक उदाहरण जो गणना योग्य नहीं हैं, जिसमें कई अलग-अलग सेट शामिल हैं जो हॉल्टिंग समस्या के वेरिएंट को एनकोड करते हैं, उनमें दो गुण समान हैं:
+समुच्चय के प्राकृतिक उदाहरण जो गणनीय नहीं हैं, जिसमें कई अलग-अलग समुच्चय सम्मिलित हैं जो विरामतः समस्या के प्रकार को एनकोड करते हैं, उनमें दो गुण समान हैं:
-# वे पुनरावर्ती रूप से गणना योग्य हैं, और
+# वे पुनरावर्ती रूप से गणनीय हैं,और
-#प्रत्येक को [[अनेक-एक कमी]] के माध्यम से किसी अन्य में अनुवादित किया जा सकता है। अर्थात्, ऐसे समुच्चय A और B दिए गए हैं, कुल संगणनीय फलन f ऐसा है कि A = {x : f(x) ∈ B}। इन सेटों को कई-एक समकक्ष (या एम-समतुल्य) कहा जाता है।
+#प्रत्येक को [[अनेक-एक कमी|अनेक-एक अपचयन]] के माध्यम से किसी अन्य में अनुवादित किया जा सकता है। अर्थात्, ऐसे समुच्चय A और B दिए गए हैं, कुल संगणनीय फलन f ऐसा है कि A = {x : f(x) ∈ B}। इन समुच्चयों को एका-एक समकक्ष या एम-समतुल्य कहा जाता है।
-ट्यूरिंग रिडक्शन की तुलना में कई-एक कटौती अधिक मजबूत होती है: यदि एक सेट ए एक सेट बी के लिए कई-एक रिड्यूसिबल है, तो ए बी के लिए ट्यूरिंग रिड्यूसिबल है, लेकिन बातचीत हमेशा पकड़ में नहीं आती है। यद्यपि गैर-कम्प्यूटेबल सेट के प्राकृतिक उदाहरण सभी एक-एक समतुल्य हैं, लेकिन संगंणकताल रूप से गणना योग्य सेट ए और बी का निर्माण करना संभव है, जैसे कि ए बी के लिए ट्यूरिंग रिड्यूसिबल है, लेकिन कई-एक बी के लिए रिड्यूसिबल नहीं है। यह दिखाया जा सकता है कि प्रत्येक संगंणकताल गणना योग्य सेट हॉल्टिंग प्रॉब्लम के लिए मल्टी-वन रिड्यूसिबल है, और इस प्रकार हॉल्टिंग प्रॉब्लम मल्टी-वन रिड्यूसबिलिटी और ट्यूरिंग रिड्यूसिबिलिटी के संबंध में सबसे जटिल संगंणकताल गणना योग्य सेट है। 1944 में, पोस्ट<ref name="Post_1944"/>पूछा गया कि क्या प्रत्येक संगणनीय गणना योग्य सेट या तो संगणनीय है या ट्यूरिंग डिग्री # हाल्टिंग समस्या के लिए ट्यूरिंग समतुल्य है, अर्थात, क्या उन दोनों के बीच ट्यूरिंग डिग्री मध्यवर्ती के साथ कोई संगणनीय गणना योग्य सेट नहीं है।
+ट्यूरिंग अपचयन की तुलना में एका-एक कटौती अधिक प्रबल होती है: यदि समुच्चय ए समुच्चय बी के लिए एका-एक कम करने योग्य है, तो ए बी के लिए ट्यूरिंग कम करने योग्य है, परन्तु बातचीत सदैव पकड़ में नहीं आती है। यद्यपि गैर-संगणनीय समुच्चय के प्राकृतिक उदाहरण सभी कई -एक समतुल्य हैं, लेकिन संगंणकताल रूप से गणनीय समुच्चय ए और बी का निर्माण करना संभव है, जैसे कि ए बी के लिए ट्यूरिंग कम करने योग्य है, परन्तु एका-एक बी के लिए संगणनीय नहीं है। यह प्रदर्शित जा सकता है कि प्रत्येक संगंणकताल गणनीय समुच्चय विरामतः समस्या के लिए विविध अपचयन है, और इस प्रकार विरामतः समस्या विविध अपचायिक और ट्यूरिंग अपचायिक के संबंध में सबसे जटिल संगंणकताल गणनीय समुच्चय है। 1944 में, पोस्ट द्वारा पूछा गया कि क्या प्रत्येक संगणनीय गणनीय समुच्चय या तो संगणनीय है या ट्यूरिंग श्रेणी विरामतः समस्या के लिए ट्यूरिंग समतुल्य है, अर्थात, क्या उन दोनों के मध्य ट्यूरिंग श्रेणी  मध्यवर्ती के साथ कोई संगणनीय गणनीय समुच्चय नहीं है।
-मध्यवर्ती परिणामों के रूप में, [[सरल सेट]], [[अतिसरल सेट]] और हाइपरहाइपरसिंपल सेट जैसे कंप्यूटेशनल रूप से गणना योग्य सेटों के प्राकृतिक प्रकारों को परिभाषित करें। पोस्ट ने दिखाया कि ये सेट संगंणकताल सेट और कई-एक रिड्यूसबिलिटी के संबंध में हॉल्टिंग समस्या के बीच सख्ती से हैं। पोस्ट ने यह भी दिखाया कि उनमें से कुछ ट्यूरिंग रिड्यूसबिलिटी की तुलना में अन्य रिड्यूसबिलिटी धारणाओं के तहत सख्ती से मध्यवर्ती हैं। लेकिन पोस्ट ने इंटरमीडिएट ट्यूरिंग डिग्री के गणनात्मक रूप से गणना योग्य सेटों के अस्तित्व की मुख्य समस्या को खुला छोड़ दिया; इस समस्या को पोस्ट की समस्या के रूप में जाना जाने लगा। दस वर्षों के बाद, क्लेन और पोस्ट ने 1954 में दिखाया कि गणना योग्य सेट और हॉल्टिंग समस्या के बीच मध्यवर्ती ट्यूरिंग डिग्री हैं, लेकिन वे यह दिखाने में विफल रहे कि इनमें से किसी भी डिग्री में गणना योग्य गणना योग्य सेट शामिल है। इसके तुरंत बाद, फ्रेडबर्ग और मुचनिक ने स्वतंत्र रूप से इंटरमीडिएट डिग्री के गणना योग्य सेटों के अस्तित्व को स्थापित करके पोस्ट की समस्या को हल किया। इस अभूतपूर्व परिणाम ने संगंणकताल गणना योग्य सेटों की ट्यूरिंग डिग्री का एक विस्तृत अध्ययन खोला जो एक बहुत ही जटिल और गैर-तुच्छ संरचना के अधिकारी थे।
+मध्यवर्ती परिणामों के रूप में, [[सरल सेट|सरल]], [[अतिसरल सेट|अतिसरल]] और अतिअतिसरल समुच्चय जैसे संगणनात्मक रूप से गणनीय समुच्चयों के प्राकृतिक प्रकारों को परिभाषित करें। पोस्ट ने प्रदर्शित कि ये समुच्चय संगंणकताल समुच्चय और एका-एक अपचेयता के संबंध में विरामतः समस्या के मध्य सख्ती से हैं। पोस्ट ने यह भी प्रदर्शित कि उनमें से कुछ ट्यूरिंग अपचेयता की तुलना में अन्य अपचयन  धारणाओं के तहत सख्ती से मध्यवर्ती हैं। लेकिन पोस्ट ने इंटरमीडिएट ट्यूरिंग श्रेणी के गणनात्मक रूप से गणनीय समुच्चयों के अस्तित्व की मुख्य समस्या को खुला छोड़ दिया; इस समस्या को पोस्ट की समस्या के रूप में जाना जाने लगा। दस वर्षों के बाद, क्लेन और पोस्ट ने 1954 में प्रदर्शित कि गणनीय समुच्चय और विरामतः समस्या के मध्य मध्यवर्ती ट्यूरिंग श्रेणी हैं, लेकिन वे यह दिखाने में विफल रहे कि इनमें से किसी भी श्रेणी में गणनीय समुच्चय सम्मिलित है। इसके तुरंत बाद, फ्रेडबर्ग और मुचनिक ने स्वतंत्र रूप से इंटरमीडिएट श्रेणी के गणनीय समुच्चयों के अस्तित्व को स्थापित करके पोस्ट की समस्या को हल किया। इस अभूतपूर्व परिणाम ने संगंणकताल गणनीय समुच्चयों की ट्यूरिंग श्रणी का एक विस्तृत अध्ययन खोला जो एक बहुत ही जटिल और गैर-तुच्छ संरचना के अधिकारी थे।
-ऐसे कई सेट हैं जो संगणनीय रूप से गणना योग्य नहीं हैं, और सभी सेटों की ट्यूरिंग डिग्री की जांच संगंणनीयता सिद्धांत में उतनी ही केंद्रीय है जितनी कि गणना योग्य ट्यूरिंग डिग्री की जांच। विशेष गुणों के साथ कई डिग्रियों का निर्माण किया गया: हाइपरइम्यून-मुक्त डिग्रियां जहां उस डिग्री के सापेक्ष प्रत्येक कार्य की गणना एक (असंबद्ध) संगणनीय कार्य द्वारा की जाती है; उच्च डिग्री जिसके सापेक्ष कोई एक कार्य f की गणना कर सकता है जो प्रत्येक गणना योग्य कार्य g पर हावी है, इस अर्थ में कि g के आधार पर एक स्थिर c है जैसे कि g(x) <f(x) for all x > c; [[एल्गोरिथम यादृच्छिक सेट]] युक्त यादृच्छिक डिग्री; 1-जेनेरिक सेट की 1-जेनेरिक डिग्री; और सीमित रिकर्सिव|लिमिट-संगंणनीय सेट की हॉल्टिंग प्रॉब्लम से नीचे की डिग्री।
+ऐसे कई समुच्चय हैं जो संगणनीय रूप से गणनीय नहीं हैं, और सभी समुच्चयों की ट्यूरिंग श्रेणी की जांच संगंणनीयता सिद्धांत में उतनी ही केंद्रीय है जितनी कि गणनीय ट्यूरिंग श्रेणी की जांच। विशेष गुणों के साथ कई श्रेणियों का निर्माण किया गया: अतिप्रतिरक्षा -मुक्त श्रेणिया जहां उस श्रेणी के सापेक्ष प्रत्येक कार्य की गणना एक असंबद्ध संगणनीय कार्य द्वारा की जाती है; उच्च श्रेणी जिसके सापेक्ष कोई एक कार्य f की गणना कर सकता है जो प्रत्येक गणनीय कार्य g पर हावी है, इस अर्थ में कि g के आधार पर एक स्थिर c है जैसे कि g(x) <f(x) for all x > c; [[एल्गोरिथम यादृच्छिक सेट|अभिकलन यादृच्छिक समुच्चय]] युक्त यादृच्छिक श्रेणी; प्रजातिगत समुच्चय की एक प्रजातिगत श्रेणी; और सीमित पुनरावर्त सीमा-संगंणनीय समुच्चय की विरामतः समस्या से नीचे की श्रेणी।
-मनमाना (जरूरी नहीं कि संगणनीय रूप से गणना योग्य) ट्यूरिंग डिग्रियों के अध्ययन में ट्यूरिंग जंप का अध्ययन शामिल है। एक सेट ए दिया गया है, ए का ट्यूरिंग जंप प्राकृतिक संख्याओं का एक सेट है जो ऑरेकल ए के साथ चलने वाली ऑरेकल ट्यूरिंग मशीनों के लिए हाल्टिंग समस्या के समाधान को एन्कोडिंग करता है। किसी भी सेट का ट्यूरिंग जंप हमेशा मूल सेट की तुलना में उच्च ट्यूरिंग डिग्री का होता है, और फ्रीडबर्ग के एक प्रमेय से पता चलता है कि हॉल्टिंग समस्या की गणना करने वाले किसी भी सेट को दूसरे सेट के ट्यूरिंग जंप के रूप में प्राप्त किया जा सकता है। पोस्ट का प्रमेय ट्यूरिंग जंप ऑपरेशन और [[अंकगणितीय पदानुक्रम]] के बीच घनिष्ठ संबंध स्थापित करता है, जो अंकगणित में उनकी निश्चितता के आधार पर प्राकृतिक संख्याओं के कुछ सबसेट का वर्गीकरण है।
+यद्रिक्षिक जरूरी नहीं कि संगणनीय रूप से गणनीय ट्यूरिंग श्रेणियों के अध्ययन में ट्यूरिंग विषयांतर का अध्ययन सम्मिलित है। एक समुच्चय ए दिया गया है, ए का ट्यूरिंग विषयांतर प्राकृतिक संख्याओं का एक समुच्चय है जो ऑरेकल ए के साथ चलने वाली ऑरेकल ट्यूरिंग यंत्रों के लिए विरामतः समस्या के समाधान को संकेतन करता है। किसी भी समुच्चय का ट्यूरिंग विषयांतर हमेशा मूल समुच्चय की तुलना में उच्च ट्यूरिंग श्रेणी का होता है, और फ्रीडबर्ग के एक प्रमेय से पता चलता है कि विरामतः समस्या की गणना करने वाले किसी भी समुच्चय को दूसरे समुच्चय के ट्यूरिंग विषयांतर के रूप में प्राप्त किया जा सकता है। पोस्ट का प्रमेय ट्यूरिंग विषयांतर संक्रिया और [[अंकगणितीय पदानुक्रम]] के मध्य घनिष्ठ संबंध स्थापित करता है, जो अंकगणित में उनकी निश्चितता के आधार पर प्राकृतिक संख्याओं के कुछ उप-समुच्चय का वर्गीकरण है।
-ट्यूरिंग डिग्रियों पर हाल के शोध ने ट्यूरिंग डिग्रियों के सेट की समग्र संरचना पर ध्यान केंद्रित किया है और ट्यूरिंग डिग्रियों के सेट पर संगंणकताल रूप से गणना करने योग्य सेट हैं। शोर और स्लैमन का एक गहरा प्रमेय<ref name="Shore-Slaman_1999"/>बताता है कि ट्यूरिंग डिग्री के आंशिक क्रम में इसकी ट्यूरिंग जंप की डिग्री के लिए एक डिग्री x मैपिंग कार्य निश्चित है। Ambos-Spies और Fejer द्वारा एक सर्वेक्षण<ref name="Ambos-Spies-Fejer_2006"/>इस शोध और इसकी ऐतिहासिक प्रगति का अवलोकन देता है।
+ट्यूरिंग श्रेणियों पर हाल के शोध ने ट्यूरिंग श्रेणियों के समुच्चय की समग्र संरचना पर ध्यान केंद्रित किया है और ट्यूरिंग श्रेणियों के समुच्चय पर संगंणकताल रूप से गणना करने योग्य समुच्चय हैं। शोर और स्लैमन का एक गहरा प्रमेय<ref name="Shore-Slaman_1999"/>बताता है कि ट्यूरिंग श्रेणी के आंशिक क्रम में इसकी ट्यूरिंग विषयांतर की श्रेणी  के लिए एक श्रेणी  x आरेखण कार्य निश्चित है। अम्बोस-स्पीज और फेजर द्वारा एक सर्वेक्षण किया गया,<ref name="Ambos-Spies-Fejer_2006"/>इस शोध को इसकी ऐतिहासिक प्रगति का अवलोकन देता है।
 === अन्य कमी ===
-{{Main|Reduction (recursion theory)}}
+संगंणनीयता सिद्धांत में अनुसंधान का एक सतत क्षेत्र ट्यूरिंग अपचेयक के अतिरिक्त अपचेयक सम्बन्ध का अध्ययन करता है। डाक ने <ref name="Post_1944"/>कई प्रबल अपचेयक पेश की, इसलिए नाम दिया गया क्योंकि वे ट्रुथ-टेबल अपचेयक का संकेत देते हैं। एक प्रबल न्यूनीकरण को लागू करने वाली एक ट्यूरिंग यंत्र कुल कार्य की गणना करेगी चाहे वह किसी भी ऑरेकल के साथ प्रस्तुत किया गया हो। कमजोर अपचेयक वे हैं जहां कमी की प्रक्रिया सभी ऑरेकल के लिए समाप्त नहीं हो सकती है; ट्यूरिंग अपचेयक एक उदाहरण है।
-संगंणनीयता थ्योरी में अनुसंधान का एक सतत क्षेत्र ट्यूरिंग रिड्यूसबिलिटी के अलावा रिड्यूसबिलिटी रिलेशंस का अध्ययन करता है। डाक<ref name="Post_1944"/>कई मजबूत रिड्यूसिबिलिटी पेश की, इसलिए नाम दिया गया क्योंकि वे ट्रुथ-टेबल रिड्यूसिबिलिटी का संकेत देते हैं। एक मजबूत न्यूनीकरण को लागू करने वाली एक ट्यूरिंग मशीन कुल कार्य की गणना करेगी चाहे वह किसी भी ऑरेकल के साथ प्रस्तुत किया गया हो। कमजोर रिड्यूसिबिलिटी वे हैं जहां कमी की प्रक्रिया सभी ऑरेकल के लिए समाप्त नहीं हो सकती है; ट्यूरिंग रिड्यूसबिलिटी एक उदाहरण है।
-मजबूत कटौती में शामिल हैं:
+प्रबल कटौती में सम्मिलित हैं:
-: कई-एक कमी | एक-एक कमी: A, B के लिए एक-एक कम करने योग्य (या 1-कम करने योग्य) है यदि कुल संगणनीय अंतःक्षेपण फलन f ऐसा है कि प्रत्येक n A में है यदि और केवल यदि f(n) है बी में।
+: एक-एक कमी: A, B के लिए एक-एक कम करने योग्य (या 1-कम करने योग्य) है यदि कुल संगणनीय अंतःक्षेपण फलन f ऐसा है कि प्रत्येक n A में है यदि और केवल यदि f(n) है बी में।
-: अनेक-एक न्यूनीकरण|अनेक-एक न्यूनीकरण: यह अनिवार्य रूप से एक-एक न्यूनीकरणीयता है, बिना इस बाधा के कि f अंतःक्षेपी हो। ए बी के लिए कई-एक कम करने योग्य (या एम-कम करने योग्य) है यदि कुल गणना योग्य कार्य एफ है जैसे कि प्रत्येक एन ए में है और केवल अगर एफ (एन) बी में है।
+: कई -एक न्यूनीकरण: यह अनिवार्य रूप से एक-एक न्यूनीकरणीयता है, बिना इस बाधा के कि f अंतःक्षेपी हो। ए बी के लिए एका-एक कम करने योग्य (या एम-कम करने योग्य) है यदि कुल गणनीय कार्य एफ है जैसे कि प्रत्येक एन ए में है और केवल यदि एफ (एन) बी में है।
-: ट्रुथ टेबल रिडक्शन | ट्रुथ-टेबल रिड्यूसिबिलिटी: ए ट्रुथ-टेबल रिड्यूसिबल टू बी है अगर ए एक ऑरेकल ट्यूरिंग मशीन के माध्यम से बी के लिए ट्यूरिंग रिड्यूसिबल है जो दिए गए ऑरेकल की परवाह किए बिना कुल कार्य की गणना करता है। [[कैंटर स्पेस]] की कॉम्पैक्टनेस के कारण, यह कहने के बराबर है कि रिडक्शन प्रश्नों की एक सूची (केवल इनपुट पर निर्भर करता है) को एक साथ ऑरैकल में प्रस्तुत करता है, और फिर उनके उत्तरों को देखने के बाद अतिरिक्त प्रश्न पूछे बिना आउटपुट उत्पन्न करने में सक्षम होता है। प्रारंभिक प्रश्नों के लिए ऑरेकल के उत्तर के बारे में। ट्रुथ-टेबल रिड्यूसबिलिटी के कई रूपों का भी अध्ययन किया गया है।
+: ट्रुथ टेबल रिडक्शन | ट्रुथ-टेबल अपचेयक: ए ट्रुथ-टेबल अपचेयक टू बी है अगर ए एक ऑरेकल ट्यूरिंग यंत्र के माध्यम से बी के लिए ट्यूरिंग अपचेयक है जो दिए गए ऑरेकल की ध्यान दिए बिना कुल कार्य की गणना करता है। [[कैंटर स्पेस]] की दृढ़ता के कारण, यह कहने के बराबर है कि अपचयन प्रश्नों की एक सूची को एक साथ ऑरैकल में प्रस्तुत करता है, और फिर उनके उत्तरों को देखने के बाद अतिरिक्त प्रश्न पूछे बिना निर्गत उत्पन्न करने में सक्षम होता है। प्रारंभिक प्रश्नों के लिए ऑरेकल के उत्तर के बारे में। ट्रुथ-टेबल अपचेयक के कई रूपों का भी अध्ययन किया गया है।
-लेख में आगे की कमी (सकारात्मक, वियोगात्मक, संयोजन, रैखिक और उनके कमजोर और बंधे हुए संस्करण) पर चर्चा की गई है।
+लेख में आगे की कमी और सकारात्मक, वियोगात्मक, संयोजन, रैखिक और उनके कमजोर और बंधे हुए संस्करण पर चर्चा की गई है।
-मजबूत न्यूनीकरण पर प्रमुख शोध उनके सिद्धांतों की तुलना करने के लिए किया गया है, दोनों संगणन योग्य गणना योग्य सेटों के वर्ग के साथ-साथ प्राकृतिक संख्याओं के सभी उपसमूहों के वर्ग के लिए। इसके अलावा, कमियों के बीच संबंधों का अध्ययन किया गया है। उदाहरण के लिए, यह ज्ञात है कि प्रत्येक ट्यूरिंग डिग्री या तो एक ट्रुथ-टेबल डिग्री है या असीम रूप से कई ट्रुथ-टेबल डिग्री का संघ है।
+दृढ़ न्यूनीकरण पर प्रमुख शोध उनके सिद्धांतों की तुलना करने के लिए किया गया है, दोनों संगणन गणनीय समुच्चयों के वर्ग के साथ-साथ प्राकृतिक संख्याओं के सभी उपसमूहों के वर्ग के लिए है, इसके अतिरिक्त कमियों के मध्य संबंधों का अध्ययन किया गया है। उदाहरण के लिए, यह ज्ञात है कि प्रत्येक ट्यूरिंग श्रेणी या तो एक ट्रुथ-टेबल श्रेणी है या असीम रूप से कई ट्रुथ-टेबल श्रेणी  का संघ है।
-ट्यूरिंग रिड्यूसिबिलिटी (यानी, रिड्यूसिबिलिटी जो ट्यूरिंग रिड्यूसिबिलिटी द्वारा निहित है) की तुलना में कमजोर रिड्यूसिबिलिटी का भी अध्ययन किया गया है। सबसे प्रसिद्ध अंकगणितीय रिड्यूसबिलिटी और [[[[अंकगणितीय कमी]]]] हैं। ये रिड्यूसिबिलिटी अंकगणित के मानक मॉडल पर निश्चितता से निकटता से जुड़ी हुई हैं।
+ट्यूरिंग अपचेयक की तुलना में दुर्बल अपचेयक का भी अध्ययन किया गया है। सबसे प्रसिद्ध अंकगणितीय अपचेयक और [[अंकगणितीय कमी]] हैं। ये अपचेयक अंकगणित के मानक प्रारूप पर निश्चितता एवं निकटता से जुड़ी हुई हैं।
-===चावल का प्रमेय और अंकगणितीय पदानुक्रम===
+===राइस का प्रमेय और अंकगणितीय पदानुक्रम===
-[[हेनरी गॉर्डन राइस]] ने दिखाया कि प्रत्येक गैर-तुच्छ वर्ग C के लिए (जिसमें कुछ लेकिन सभी c.e. सेट नहीं हैं) सूचकांक सेट E = {e: eth c.e. सेट डब्ल्यू<sub>e</sub>is in C} में यह गुण है कि या तो हॉल्टिंग प्रॉब्लम या इसका कॉम्प्लिमेंट मल्टी-वन रिड्यूसिबल है E के लिए, यानी, E के लिए मल्टी-वन रिडक्शन का उपयोग करके मैप किया जा सकता है (अधिक विवरण के लिए राइस का प्रमेय देखें)। लेकिन, इनमें से कई इंडेक्स सेट हॉल्टिंग प्रॉब्लम से भी ज्यादा जटिल हैं। इस प्रकार के सेटों को अंकगणितीय पदानुक्रम का उपयोग करके वर्गीकृत किया जा सकता है। उदाहरण के लिए, सभी परिमित सेटों के वर्ग का सूचकांक सेट FIN स्तर Σ पर है<sub>2</sub>, सभी पुनरावर्ती सेटों के वर्ग का सूचकांक सेट REC स्तर Σ पर है<sub>3</sub>, सभी कॉफिनिट सेटों का इंडेक्स सेट COFIN भी Σ के स्तर पर है<sub>3</sub> और सभी ट्यूरिंग-पूर्ण सेटों के वर्ग का सूचकांक सेट COMP<sub>4</sub>. इन पदानुक्रम स्तरों को आगमनात्मक रूप से परिभाषित किया गया है, Σ<sub>''n''+1</sub> केवल सभी सेट शामिल हैं जो Σ के सापेक्ष गणना योग्य हैं<sub>''n''</sub>; एस<sub>1</sub> संगणनीय रूप से गणना करने योग्य सेट शामिल हैं। यहां दिए गए इंडेक्स सेट अपने स्तरों के लिए भी पूर्ण हैं, यानी इन स्तरों के सभी सेट दिए गए इंडेक्स सेटों में कई-एक घटाए जा सकते हैं।
+[[हेनरी गॉर्डन राइस]] ने प्रदर्शित कि प्रत्येक असतहीय वर्ग C के लिए सूचकांक समुच्चय E = {e: eth c.e. समुच्चय डब्ल्यू<sub>e</sub>is in C} में यह गुण है कि या तो विरामतः समस्या या इसकी प्रशंसा एका-बहुल अपचेयक E के लिए है, अर्थात, E के लिए एकाबहुल अपचयन का उपयोग करके दोष रहित किया जा सकता है। लेकिन, इनमें से कई अच्छे समुच्चय विरामतः समस्या से भी अधिक जटिल हैं। इस प्रकार के समुच्चयों को अंकगणितीय पदानुक्रम का उपयोग करके वर्गीकृत किया जा सकता है। उदाहरण के लिए, सभी अनंत समुच्चयों के वर्ग का सूचकांक समुच्चय FIN स्तर Σ पर है<sub>2</sub>, सभी पुनरावर्ती समुच्चयों के वर्ग का सूचकांक समुच्चय REC स्तर Σ पर है<sub>3</sub>, सभी कॉफिनिट समुच्चयों का अच्छे समुच्चय COFIN भी Σ के स्तर पर है<sub>3</sub> और सभी ट्यूरिंग-पूर्ण समुच्चयों के वर्ग का सूचकांक समुच्चय COMP<sub>4</sub>. इन पदानुक्रम स्तरों को आगमनात्मक रूप से परिभाषित किया गया है, Σ<sub>''n''+1</sub> केवल सभी समुच्चय सम्मिलित हैं जो Σ के सापेक्ष गणनीय हैं<sub>''n''</sub>; एस<sub>1</sub> संगणनीय रूप से गणना करने योग्य समुच्चय सम्मिलित हैं। यहां दिए गए अच्छे समुच्चय अपने स्तरों के लिए भी पूर्ण हैं, यानी इन स्तरों के सभी समुच्चय दिए गए अच्छे समुच्चयों में एका-एक घटाए जा सकते हैं।
-=== उल्टा गणित ===
+=== प्रतिलोम गणित ===
-{{Main|Reverse mathematics}}
+[[उलटा गणित|प्रतिलोम गणित]] का क्रमानुदेश पूछता है कि कौन से समुच्चय-अस्तित्व स्वयंसिद्ध गणित के विशेष प्रमेय को दूसरे क्रम के अंकगणित के उप-प्रणालियों में प्रमाणित करने के लिए आवश्यक हैं। यह अध्ययन [[हार्वे फ्रीडमैन]] द्वारा प्रारम्भ किया गया था और [[स्टीव सिम्पसन (गणितज्ञ)|स्टीव सिम्पसन]] और अन्य लोगों द्वारा विस्तार से अध्ययन किया गया था; 1999 में, सिम्पसन<ref name="Simpson_1999"/>कार्यक्रम की विस्तृत चर्चा भी की। प्रश्न में समुच्चय-अस्तित्व के स्वयंसिद्ध अनौपचारिक रूप से स्वयंसिद्धों के अनुरूप होते हैं, जो कहते हैं कि प्राकृतिक संख्याओं की शक्तियाँ विभिन्न न्यूनीकरण धारणाओं के अनुसार बंद हैं। प्रतिलोम गणित में अध्ययन किया गया सबसे दुर्बल स्वयंसिद्ध पुनरावर्त समझौता है, जो बताता है कि ट्यूरिंग अपचेयक के तहत प्राकृतिक [[सत्ता स्थापित]] को बंद कर दिया गया है।
-[[उलटा गणित]] का प्रोग्राम पूछता है कि कौन से सेट-अस्तित्व स्वयंसिद्ध गणित के विशेष प्रमेय को दूसरे क्रम के अंकगणित के उप-प्रणालियों में साबित करने के लिए आवश्यक हैं। यह अध्ययन [[हार्वे फ्रीडमैन]] द्वारा शुरू किया गया था और [[स्टीव सिम्पसन (गणितज्ञ)]] और अन्य लोगों द्वारा विस्तार से अध्ययन किया गया था; 1999 में, सिम्पसन<ref name="Simpson_1999"/>कार्यक्रम की विस्तृत चर्चा की। प्रश्न में सेट-अस्तित्व के स्वयंसिद्ध अनौपचारिक रूप से स्वयंसिद्धों के अनुरूप होते हैं, जो कहते हैं कि प्राकृतिक संख्याओं की शक्तियाँ विभिन्न न्यूनीकरण धारणाओं के तहत बंद हैं। रिवर्स गणित में अध्ययन किया गया सबसे कमजोर स्वयंसिद्ध रिकर्सिव कॉम्प्रिहेंशन है, जो बताता है कि ट्यूरिंग रिड्यूसिबिलिटी के तहत नैचुरल के [[सत्ता स्थापित]] को बंद कर दिया गया है।
-=== नंबरिंग ===
+=== संख्यांकन ===
-संख्यांकन कार्यों की गणना है; इसके दो पैरामीटर हैं, ई और एक्स और इनपुट एक्स पर नंबरिंग में ई-वें कार्य के मान को आउटपुट करता है। नंबरिंग आंशिक-गणना योग्य हो सकती है, हालांकि इसके कुछ सदस्य कुल गणना योग्य कार्य हैं। स्वीकार्य संख्याएँ वे हैं जिनमें अन्य सभी का अनुवाद किया जा सकता है। एक [[फ्राइडबर्ग नंबरिंग]] (इसके खोजकर्ता के नाम पर) सभी आंशिक-गणना योग्य कार्यों की एक-एक नंबरिंग है; यह अनिवार्य रूप से स्वीकार्य नंबरिंग नहीं है। बाद के अनुसंधान ने अन्य वर्गों की संख्या के साथ भी निपटाया जैसे कि संगणनीय रूप से गणना योग्य सेट की कक्षाएं। गोंचारोव ने उदाहरण के लिए संगणनीय रूप से गणना योग्य सेटों के एक वर्ग की खोज की, जिसके लिए गणनाएँ संगणनीय समरूपता के संबंध में ठीक दो वर्गों में आती हैं।
+संख्यांकन कार्यों की गणना है; इसके दो पैरामीटर हैं, ई और एक्स और निविष्ट एक्स पर संख्यांकन में ई- वें कार्य के मान को निर्गत करता है। संख्यांकन आंशिक-गणनीय हो सकती है, यद्यपि इसके कुछ सदस्य कुल गणनीय कार्य हैं। स्वीकार्य संख्याएँ वे हैं जिनमें अन्य सभी का अनुवाद किया जा सकता है। एक [[फ्राइडबर्ग नंबरिंग]] सभी आंशिक-गणनीय कार्यों की संख्यांकन है; यह अनिवार्य रूप से स्वीकार्य संखायांकन नहीं है। बाद के अनुसंधान ने अन्य वर्गों की संख्या के साथ भी निपटाया जैसे कि संगणनीय रूप से गणनीय समुच्चय की कक्षाएं। गोंचारोव ने उदाहरण के लिए संगणनीय रूप से गणनीय समुच्चयों के एक वर्ग की खोज की, जिसके लिए गणनाएँ संगणनीय समरूपता के संबंध में ठीक दो वर्गों में आती हैं।
 === प्राथमिकता विधि ===
-{{further|Turing degree#Post's problem and the priority method}}
+पोस्ट की समस्या को एक विधि से हल किया गया जिसे प्राथमिकता विधि कहा जाता है; इस पद्धति का उपयोग करने वाले प्रमाण को प्राथमिकता तर्क कहा जाता है। इस पद्धति का मुख्य रूप से विशेष गुणों के साथ संगणनीय गणनीय समुच्चय बनाने के लिए उपयोग किया जाता है। इस पद्धति का उपयोग करने के लिए, निर्मित किए जाने वाले समुच्चय के वांछित गुणों को लक्ष्यों की एक अनंत सूची में विभाजित किया जाता है, जिसे आवश्यकताओं के रूप में जाना जाता है, ताकि सभी आवश्यकताओं को पूरा करने के कारण समुच्चय में वांछित गुण हों। प्रत्येक आवश्यकता को आवश्यकता की प्राथमिकता का प्रतिनिधित्व करने वाली प्राकृतिक संख्या को सौंपा गया है; इसलिए 0 को सबसे महत्वपूर्ण प्राथमिकता दी जाती है, 1 को दूसरी सबसे महत्वपूर्ण प्राथमिकता दी जाती है, और इसी तरह आगे भी। प्रायः समुच्चय का निर्माण चरणों में किया जाता है, प्रत्येक चरण समुच्चय में संख्याओं को जोड़कर या समुच्चय से संख्याओं को प्रतिबंधित करके एक से अधिक आवश्यकताओं को पूरा करने का प्रयास करता है ताकि अंतिम समुच्चय आवश्यकता को पूरा करे। ऐसा हो सकता है कि एक आवश्यकता को पूरा करने से दूसरी असंतुष्ट हो जाए; ऐसी घटना में क्या करना है, यह तय करने के लिए प्राथमिकता क्रम का उपयोग किया जाता है।
-पोस्ट की समस्या को एक विधि से हल किया गया जिसे प्राथमिकता विधि कहा जाता है; इस पद्धति का उपयोग करने वाले प्रमाण को प्राथमिकता तर्क कहा जाता है। इस पद्धति का मुख्य रूप से विशेष गुणों के साथ संगणनीय गणना योग्य सेट बनाने के लिए उपयोग किया जाता है। इस पद्धति का उपयोग करने के लिए, निर्मित किए जाने वाले सेट के वांछित गुणों को लक्ष्यों की एक अनंत सूची में विभाजित किया जाता है, जिसे आवश्यकताओं के रूप में जाना जाता है, ताकि सभी आवश्यकताओं को पूरा करने के कारण सेट में वांछित गुण हों। प्रत्येक आवश्यकता को आवश्यकता की प्राथमिकता का प्रतिनिधित्व करने वाली प्राकृतिक संख्या को सौंपा गया है; इसलिए 0 को सबसे महत्वपूर्ण प्राथमिकता दी जाती है, 1 को दूसरी सबसे महत्वपूर्ण प्राथमिकता दी जाती है, और इसी तरह आगे भी। फिर सेट का निर्माण चरणों में किया जाता है, प्रत्येक चरण सेट में संख्याओं को जोड़कर या सेट से संख्याओं को प्रतिबंधित करके एक से अधिक आवश्यकताओं को पूरा करने का प्रयास करता है ताकि अंतिम सेट आवश्यकता को पूरा करे। ऐसा हो सकता है कि एक आवश्यकता को पूरा करने से दूसरी असंतुष्ट हो जाए; ऐसी घटना में क्या करना है, यह तय करने के लिए प्राथमिकता क्रम का उपयोग किया जाता है।
-संगंणनीयता सिद्धांत में कई समस्याओं को हल करने के लिए प्राथमिकता तर्कों को नियोजित किया गया है, और उनकी जटिलता के आधार पर एक पदानुक्रम में वर्गीकृत किया गया है।<ref name="Soare_1987"/>क्योंकि जटिल प्राथमिकता वाले तर्क तकनीकी हो सकते हैं और उनका पालन करना कठिन हो सकता है, यह पारंपरिक रूप से प्राथमिकता वाले तर्कों के बिना परिणामों को साबित करने के लिए वांछनीय माना जाता है, या यह देखने के लिए कि क्या प्राथमिकता वाले तर्कों के साथ सिद्ध किए गए परिणाम भी उनके बिना सिद्ध किए जा सकते हैं।
+संगंणनीयता सिद्धांत में कई समस्याओं को हल करने के लिए प्राथमिकता तर्कों को नियोजित किया गया है, और उनकी जटिलता के आधार पर एक पदानुक्रम में वर्गीकृत किया गया है।<ref name="Soare_1987"/>क्योंकि जटिल प्राथमिकता वाले तर्क तकनीकी हो सकते हैं और उनका पालन करना कठिन हो सकता है, यह पारंपरिक रूप से प्राथमिकता वाले तर्कों के बिना परिणामों को प्रमाणित करने के लिए वांछनीय माना जाता है, या यह देखने के लिए कि क्या प्राथमिकता वाले तर्कों के साथ सिद्ध किए गए परिणाम भी उनके बिना सिद्ध किए जा सकते हैं।
 उदाहरण के लिए, कुमार ने प्राथमिकता पद्धति का उपयोग किए बिना फ्रीडबर्ग नंबरिंग के अस्तित्व के प्रमाण पर एक पेपर प्रकाशित किया।
-=== संगणनीय रूप से गणना योग्य सेटों की जाली ===
+=== संगणनीय रूप से गणनीय समुच्चयों का तंत्र ===
-जब पोस्ट ने एक साधारण सेट की धारणा को c.e के रूप में परिभाषित किया। एक अनंत पूरक के साथ सेट करें जिसमें कोई अनंत सी.ई. सेट, उन्होंने समावेशन के तहत संगणनीय रूप से गणना योग्य सेटों की संरचना का अध्ययन करना शुरू किया। यह जाली एक अच्छी तरह से अध्ययन की गई संरचना बन गई। इस संरचना में संगणनीय सेटों को मूल परिणाम द्वारा परिभाषित किया जा सकता है कि एक सेट संगणनीय है यदि और केवल यदि सेट और इसके पूरक दोनों संगणनीय रूप से गणना योग्य हैं। अनंत सी.ई. समुच्चय में हमेशा अनंत संगणनीय उपसमुच्चय होते हैं; लेकिन दूसरी ओर, सरल सेट मौजूद होते हैं लेकिन हमेशा एक सांकेतिक गणना योग्य सुपरसेट नहीं होता है। डाक<ref name="Post_1944"/>पहले से ही हाइपरसिंपल और हाइपरहाइपरसिंपल सेट पेश किए; बाद में अधिक से अधिक सेट का निर्माण किया गया जो c.e. ऐसे सेट करता है कि हर सी.ई. सुपरसेट या तो दिए गए अधिकतम सेट का परिमित संस्करण है या सह-परिमित है। इस जाली के अध्ययन में पोस्ट की मूल प्रेरणा एक संरचनात्मक धारणा को खोजने के लिए थी जैसे कि हर सेट जो इस संपत्ति को संतुष्ट करता है, न तो गणना योग्य सेटों की ट्यूरिंग डिग्री में है और न ही हॉल्टिंग समस्या की ट्यूरिंग डिग्री में। पोस्ट को ऐसी कोई संपत्ति नहीं मिली और उसकी समस्या के समाधान ने इसके बजाय प्राथमिकता के तरीकों को लागू किया; 1991 में, हैरिंगटन और सोरे<ref name="Harrington-Soare_1991"/>अंततः ऐसी संपत्ति मिली।
+जब पोस्ट ने एक साधारण समुच्चय की धारणा को c.e के रूप में परिभाषित किया। एक अनंत पूरक के साथ समुच्चय करें जिसमें कोई अनंत सी.ई. समुच्चय, उन्होंने समावेशन के तहत संगणनीय रूप से गणनीय समुच्चयों की संरचना का अध्ययन करना प्रारम्भ किया। यह तंत्र अच्छी तरह से अध्ययन की गई संरचना बन गई। इस संरचना में संगणनीय समुच्चयों को मूल परिणाम द्वारा परिभाषित किया जा सकता है कि एक समुच्चय संगणनीय है यदि और केवल यदि समुच्चय और इसके पूरक दोनों संगणनीय रूप से गणनीय हैं। अनंत सी.ई. समुच्चय में सदैव अनंत संगणनीय उपसमुच्चय होते हैं; लेकिन दूसरी ओर, सरल समुच्चय मौजूद होते हैं लेकिन सदैव एक सांकेतिक गणनीय सुपरसमुच्चय नहीं होता है। डाक<ref name="Post_1944"/>पहले से ही अतिसरल और अतिअतिसरल समुच्चय पेश किए; बाद में अधिक से अधिक समुच्चय का निर्माण किया गया जो c.e. ऐसे समुच्चय करता है कि हर सी.ई. सुपरसमुच्चय या तो दिए गए अधिकतम समुच्चय का अनंत संस्करण है या सह-अनंत है। इस तंत्र के अध्ययन में पोस्ट की मूल प्रेरणा एक संरचनात्मक धारणा को खोजने के लिए थी जैसे कि हर समुच्चय जो इस संपत्ति को संतुष्ट करता है, न तो गणनीय समुच्चयों की ट्यूरिंग श्रेणी में है और न ही विरामतः समस्या की ट्यूरिंग श्रेणी में। पोस्ट को ऐसी कोई संपत्ति नहीं मिली और न ही उसकी समस्या के समाधान हुआ अपितु इसके अतिरिक्त प्राथमिकता के तरीकों को लागू किया; 1991 में, हैरिंगटन और सोरे को <ref name="Harrington-Soare_1991"/>अंततः ऐसी संपत्ति मिली।
-=== ऑटोमोर्फिज्म समस्याएं ===
+=== स्वसमाकृतिकता समस्याएं ===
-एक अन्य महत्वपूर्ण प्रश्न संगंणनीयता-सैद्धांतिक संरचनाओं में ऑटोमोर्फिज़्म का अस्तित्व है। इन संरचनाओं में से एक यह है कि समावेशन मॉड्यूलो परिमित अंतर के तहत गणना योग्य गणना योग्य सेटों में से एक; इस संरचना में, A, B से नीचे है यदि और केवल यदि सेट अंतर B − A परिमित है। मैक्सिमल सेट (जैसा कि पिछले पैराग्राफ में परिभाषित किया गया है) में संपत्ति है कि वे गैर-मैक्सिमल सेट के लिए ऑटोमोर्फिक नहीं हो सकते हैं, अर्थात, यदि संरचना के तहत संगंणकताल रूप से गणना करने योग्य सेट का एक ऑटोमोर्फिज्म है, तो हर [[अधिकतम सेट]] को मैप किया जाता है एक और अधिकतम सेट। 1974 में, सोरे<ref name="Soare_1974"/>ने दिखाया कि इसका विलोम भी धारण करता है, अर्थात प्रत्येक दो अधिकतम समुच्चय स्वतःरूपी होते हैं। तो अधिकतम सेट एक कक्षा बनाते हैं, यानी, प्रत्येक ऑटोमोर्फिज्म अधिकतमता को बरकरार रखता है और किसी भी दो अधिकतम सेट एक दूसरे में कुछ ऑटोमोर्फिज्म द्वारा परिवर्तित हो जाते हैं। हैरिंगटन ने एक ऑटोमोर्फिक संपत्ति का एक और उदाहरण दिया: रचनात्मक सेटों का सेट, जो कई-एक हॉल्टिंग समस्या के बराबर हैं।
+एक अन्य महत्वपूर्ण प्रश्न संगंणनीयता-सैद्धांतिक संरचनाओं में स्वसमाकृतिकता का अस्तित्व है। इन संरचनाओं में से एक यह है कि समावेशन के सापेक्ष अनंत अंतर के अनुसार गणनीय समुच्चयों में से एक; इस संरचना में, A, B से नीचे है यदि और केवल यदि समुच्चय अंतर B − A अनंत है। मैक्सिमल समुच्चय में संपत्ति कि वे गैर-मैक्सिमल समुच्चय के लिए स्वसमाकृतिक नहीं हो सकते हैं, अर्थात, यदि संरचना के तहत संगंणकताल रूप से गणना करने योग्य समुच्चय का एक स्वसमाकृतिकता है, तो हर [[अधिकतम सेट|अधिकतम समुच्चय]] को आलेख्यपत्र किया जाता है। 1974 में, सोरे<ref name="Soare_1974"/>ने प्रदर्शित कि इसका विपरीत भी धारण करता है, अर्थात प्रत्येक दो अधिकतम समुच्चय स्वतः रूपी होते हैं। तो अधिकतम समुच्चय एक कक्षा बनाते हैं, अर्थात, प्रत्येक स्वसमाकृतिक अधिकतमता को बरकरार रखता है और किसी भी दो अधिकतम समुच्चय एक दूसरे में कुछ स्वसमाकृतिकता द्वारा परिवर्तित हो जाते हैं। हैरिंगटन ने एक स्वसमाकृतिक संपत्ति का एक और उदाहरण दिया: रचनात्मक समुच्चयों का समुच्चय, जो एका-एक विरामतः समस्या के बराबर हैं।
-संगणनीय रूप से गणना योग्य सेटों की जाली के अलावा, सभी सेटों की ट्यूरिंग डिग्री की संरचना के साथ-साथ सीई की ट्यूरिंग डिग्री की संरचना के लिए ऑटोमोर्फिज्म का भी अध्ययन किया जाता है। सेट। दोनों ही मामलों में, कूपर ने गैर-तुच्छ ऑटोमोर्फिज्म का निर्माण करने का दावा किया है जो कुछ डिग्री को अन्य डिग्री में मैप करता है; हालांकि, इस निर्माण को सत्यापित नहीं किया गया है और कुछ सहयोगियों का मानना है कि निर्माण में त्रुटियां हैं और यह सवाल कि क्या ट्यूरिंग डिग्री का एक गैर-तुच्छ ऑटोमोर्फिज्म है, अभी भी इस क्षेत्र में मुख्य अनसुलझे प्रश्नों में से एक है।<ref name="Slaman-Woodin_1986"/><ref name="Ambos-Spies-Fejer_2006"/>
+संगणनीय रूप से गणनीय समुच्चयों की तंत्र के अतिरिक्त, सभी समुच्चयों की ट्यूरिंग श्रेणी की संरचना के साथ-साथ सीई की ट्यूरिंग श्रेणी की संरचना के लिए स्वसमाकृतिकता का भी अध्ययन किया जाता है। समुच्चय। दोनों ही मामलों में, कूपर ने गैर-तुच्छ स्वसमाकृतिकता का निर्माण करने का दावा किया है जो कुछ श्रेणी को अन्य श्रेणी में आलेख्यपत्र करता है; यद्यपि, इस निर्माण को सत्यापित नहीं किया गया है और कुछ सहयोगियों का मानना है कि निर्माण में त्रुटियां हैं और यह सवाल कि क्या ट्यूरिंग श्रेणी का एक गैर-तुच्छ स्वसमाकृतिक है, अभी भी इस क्षेत्र में मुख्य अनसुलझे प्रश्नों में से एक है।<ref name="Slaman-Woodin_1986"/><ref name="Ambos-Spies-Fejer_2006"/>
 === कोलमोगोरोव जटिलता ===
-{{Main|Kolmogorov complexity}}
+कोल्मोगोरोव जटिलता और [[एल्गोरिथम यादृच्छिकता|अभिकलन यादृच्छिकता]] का क्षेत्र 1960 और 1970 के दशक के दौरान चैतिन, कोलमोगोरोव, लेविन, मार्टिन-लोफ और सोलोमनॉफ द्वारा विकसित किया गया था नाम वर्णानुक्रम में यहां दिए गए हैं; अधिकांश शोध स्वतंत्र थे, और अवधारणा की एकता यादृच्छिकता उस समय समझ में नहीं आई थी। मुख्य विचार एक सार्वभौमिक ट्यूरिंग यंत्र यू पर विचार करना है और एक संख्या एक्स की जटिलता को मापने के लिए सबसे कम निविष्ट पी की लंबाई के रूप में यू (पी) निर्गत एक्स। इस दृष्टिकोण ने अनंत वस्तुओं के लिए यादृच्छिकता की धारणा को लागू करके यह निर्धारित करने के पहले विधियों में क्रांति ला दी कि कब एक अनंत अनुक्रम समतुल्य रूप से, प्राकृतिक संख्याओं के एक सबसमुच्चय का विशिष्ट कार्य यादृच्छिक है या नहीं। [[कोलमोगोरोव जटिलता]] न केवल स्वतंत्र अध्ययन का विषय बन गई बल्कि प्रमाण प्राप्त करने के लिए एक उपकरण के रूप में अन्य विषयों पर भी लागू होती है।
-कोल्मोगोरोव जटिलता और [[एल्गोरिथम यादृच्छिकता]] का क्षेत्र 1960 और 1970 के दशक के दौरान चैतिन, कोलमोगोरोव, लेविन, मार्टिन-लोफ और सोलोमनॉफ द्वारा विकसित किया गया था (नाम वर्णानुक्रम में यहां दिए गए हैं; अधिकांश शोध स्वतंत्र थे, और अवधारणा की एकता यादृच्छिकता उस समय समझ में नहीं आई थी)। मुख्य विचार एक सार्वभौमिक ट्यूरिंग मशीन यू पर विचार करना है और एक संख्या (या स्ट्रिंग) एक्स की जटिलता को मापने के लिए सबसे कम इनपुट पी की लंबाई के रूप में यू (पी) आउटपुट एक्स। इस दृष्टिकोण ने परिमित वस्तुओं के लिए यादृच्छिकता की धारणा को लागू करके यह निर्धारित करने के पहले तरीकों में क्रांति ला दी कि कब एक अनंत अनुक्रम (समतुल्य रूप से, प्राकृतिक संख्याओं के एक सबसेट का विशिष्ट कार्य) यादृच्छिक है या नहीं। [[कोलमोगोरोव जटिलता]] न केवल स्वतंत्र अध्ययन का विषय बन गई बल्कि प्रमाण प्राप्त करने के लिए एक उपकरण के रूप में अन्य विषयों पर भी लागू होती है।
 इस क्षेत्र में अभी भी कई खुली समस्याएं हैं। इस कारण से, इस क्षेत्र में हाल ही में जनवरी 2007 में एक शोध सम्मेलन आयोजित किया गया था<ref name="Logic_2007"/>और खुली समस्याओं की एक सूची<ref group="nb" name="NB_Nies"/>जोसेफ मिलर और आंद्रे नीस द्वारा बनाए रखा जाता है।
 === आवृत्ति गणना ===
-संगणनीयता सिद्धांत की इस शाखा ने निम्नलिखित प्रश्न का विश्लेषण किया: नियत m और n के लिए 0 < m < n के साथ, किन कार्यों के लिए A किसी भिन्न n इनपुट x के लिए गणना करना संभव है<sub>1</sub>, एक्स<sub>2</sub>, ..., एक्स<sub>n</sub>n संख्या y का एक टपल<sub>1</sub>, वाई<sub>2</sub>, ..., और<sub>n</sub>ऐसा है कि कम से कम m समीकरणों की A(x<sub>k</sub>) = और<sub>k</sub>सच हैं। इस तरह के सेट को (एम, एन) -रिकर्सिव सेट के रूप में जाना जाता है। संगंणनीयता सिद्धांत की इस शाखा में पहला प्रमुख परिणाम ट्रेखटेनब्रॉट का परिणाम है कि एक सेट की गणना की जा सकती है यदि यह (एम, एन) है - कुछ एम के लिए पुनरावर्ती, 2 एम> एन के साथ एन। दूसरी ओर, जॉकश के [[semirecursive]] सेट (जो कि जॉकश द्वारा 1968 में पेश किए जाने से पहले से ही अनौपचारिक रूप से ज्ञात थे) एक सेट के उदाहरण हैं जो (m, n)-रिकर्सिव है अगर और केवल अगर 2m < n + 1। अनगिनत हैं इनमें से कई सेट और इस प्रकार के कुछ संगणनीय गणना योग्य लेकिन गैर-गणना योग्य सेट भी। बाद में, Degtev ने संगणनीय रूप से गणना करने योग्य सेटों का एक पदानुक्रम स्थापित किया जो (1, n + 1)-रिकर्सिव हैं लेकिन (1, n)-रिकर्सिव नहीं हैं। रूसी वैज्ञानिकों द्वारा शोध के एक लंबे चरण के बाद, यह विषय पश्चिम में बेगेल की थीसिस द्वारा बाध्य प्रश्नों पर फिर से लोकप्रिय हो गया, जिसने आवृत्ति संगणना को उपर्युक्त परिबद्ध न्यूनताओं और अन्य संबंधित धारणाओं से जोड़ा। प्रमुख परिणामों में से एक कुमेर की कार्डिनैलिटी थ्योरी थी जिसमें कहा गया है कि एक सेट ए की गणना की जा सकती है अगर और केवल अगर ऐसा एन है कि कुछ एल्गोरिदम इस सेट की कार्डिनैलिटी के कई संभावित विकल्पों तक एन अलग-अलग संख्याओं के प्रत्येक टपल के लिए गणना करता है। एन संख्या ए के साथ छेड़छाड़ की; इन विकल्पों में सही कार्डिनैलिटी होनी चाहिए लेकिन कम से कम एक गलत को छोड़ दें।
+संगणनीयता सिद्धांत की इस शाखा ने निम्नलिखित प्रश्न का विश्लेषण किया: नियत m और n के लिए 0 < m < n के साथ, किन कार्यों के लिए A किसी भिन्न n निविष्ट x के लिए गणना करना संभव है, x<sub>2</sub>, ..., x<sub>n</sub> संख्या y का, y<sub>2</sub>, कम से कम m समीकरणों की A(x<sub>k</sub>) = सत्य हैं। इस तरह के समुच्चय को (एम, एन) -पुनरावर्त समुच्चय के रूप में जाना जाता है। संगंणनीयता सिद्धांत की इस शाखा में पहला प्रमुख परिणाम ट्रेखटेनब्रॉट का परिणाम है कि एक समुच्चय की गणना की जा सकती है यदि यह एम, एन है - कुछ एम के लिए पुनरावर्ती, 2 एम> एन के साथ एन। दूसरी ओर, जॉकश के [[semirecursive|सेमीपुनरावर्त]] समुच्चय जो कि जॉकश द्वारा 1968 में पेश किए जाने से पहले से ही अनौपचारिक रूप से ज्ञात थे एक समुच्चय के उदाहरण हैं जो (m, n)-पुनरावर्त है यदि केवल  2m < n + 1। अनगिनत हैं तो इनमें से कई समुच्चय इस प्रकार के कुछ संगणनीय गणनीय परन्तु गैर-गणनीय समुच्चय भी है । बाद में, डेग्टेव ने संगणनीय रूप से गणना करने योग्य समुच्चयों का एक पदानुक्रम स्थापित किया जो (1, n + 1)-पुनरावर्त हैं लेकिन (1, n)-पुनरावर्त नहीं हैं। रूसी वैज्ञानिकों द्वारा शोध के एक लंबे चरण के बाद, यह विषय पश्चिम में बेगेल की अभिधारणा द्वारा बाध्य प्रश्नों पर फिर से लोकप्रिय हो गया, जिसने आवृत्ति संगणना को उपर्युक्त परिबद्ध न्यूनताओं और अन्य संबंधित धारणाओं से जोड़ा। प्रमुख परिणामों में से एक कुमेर की कार्डिनैलिटी थ्योरी थी जिसमें कहा गया है कि एक समुच्चय ए की गणना की जा सकती है अगर और केवल अगर ऐसा एन है कि कुछ एल्गोरिदम इस समुच्चय की प्रमुखता के कई संभावित विकल्पों तक एन अलग-अलग संख्याओं के प्रत्येक टपल के लिए गणना करता है। एन संख्या ए के साथ छेड़छाड़ की; इन विकल्पों में सही प्रमुखता से  होनी चाहिए लेकिन कम से कम एक गलत को छोड़ दें।
 === आगमनात्मक अनुमान ===
-यह सीखने के सिद्धांत की संगंणनीयता-सैद्धांतिक शाखा है। यह 1967 से ई. मार्क गोल्ड के सीखने के मॉडल पर आधारित है और तब से सीखने के अधिक से अधिक मॉडल विकसित हुए हैं। सामान्य परिदृश्य निम्नलिखित है: संगणनीय कार्यों के एक वर्ग एस को देखते हुए, क्या कोई शिक्षार्थी है (अर्थात, गणना योग्य कार्यात्मक) जो फॉर्म के किसी भी इनपुट के लिए आउटपुट करता है (f(0), f(1), ..., f (एन)) एक परिकल्पना। एक शिक्षार्थी एम एक कार्य एफ सीखता है यदि लगभग सभी परिकल्पनाएं सभी गणना योग्य कार्यों की स्वीकार्य संख्या पर पहले से सहमत होने के संबंध में एफ का एक ही सूचकांक ई हैं; एम एस सीखता है अगर एम एस में हर एफ सीखता है। मूल परिणाम यह है कि कार्यों के सभी गणना योग्य वर्ग सीखने योग्य हैं जबकि सभी गणना योग्य कार्यों का वर्ग आरईसी सीखने योग्य नहीं है। कई संबंधित मॉडलों पर विचार किया गया है और साथ ही सकारात्मक डेटा से संगणनीय रूप से गणना योग्य सेटों की कक्षाओं का अध्ययन 1967 में गोल्ड के अग्रणी पेपर से अध्ययन किया गया विषय है।
+यह सीखने के सिद्धांत की संगंणनीयता-सैद्धांतिक शाखा है। यह 1967 ई. से मार्क गोल्ड के सीखने के प्रारूप पर आधारित है और तब से सीखने के लिए अधिक से अधिक प्रारूप विकसित हुए हैं। सामान्य परिदृश्य निम्नलिखित है: संगणनीय कार्यों के एक वर्ग एस को देखते हुए, क्या कोई शिक्षार्थी है जो फॉर्म के किसी भी निविष्ट के लिए निर्गत करता है (f(0), f(1), ..., f (एन)) एक परिकल्पना। शिक्षार्थी एम एक कार्य एफ सीखता है यदि लगभग सभी परिकल्पनाएं सभी गणनीय कार्यों की स्वीकार्य संख्या पर पहले से सहमत होने के संबंध में एफ का एक ही सूचकांक ई हैं; एम एस सीखता है अगर एम एस में हर एफ सीखता है। मूल परिणाम यह है कि कार्यों के सभी गणनीय वर्ग सीखने योग्य हैं जबकि सभी गणनीय कार्यों का वर्ग आरईसी सीखने योग्य नहीं है। अनेकों संबंधित प्रारूपों पर विचार किया गया है और साथ ही सकारात्मक आंकड़े से संगणनीय रूप से गणनीय समुच्चयों की कक्षाओं का अध्ययन 1967 में गोल्ड के अग्रणी पेपर से अध्ययन किया गया विषय है।
 === ट्यूरिंग संगंणनीयता का सामान्यीकरण ===
-संगंणनीयता थ्योरी में इस क्षेत्र की सामान्यीकृत धारणाओं का अध्ययन शामिल है जैसे कि अंकगणित रिड्यूसबिलिटी, [[अंकगणितीय कमी]] और अल्फा रिकर्सन थ्योरी|α-रिकर्सन थ्योरी, जैसा कि 1990 में सैक्स द्वारा वर्णित है।<ref name="Sacks_1990"/>इन सामान्यीकृत धारणाओं में रिड्यूसिबिलिटी शामिल हैं जिन्हें ट्यूरिंग मशीनों द्वारा निष्पादित नहीं किया जा सकता है, लेकिन फिर भी ट्यूरिंग रिड्यूसिबिलिटी के प्राकृतिक सामान्यीकरण हैं। इन अध्ययनों में [[विश्लेषणात्मक पदानुक्रम]] की जांच करने के दृष्टिकोण शामिल हैं जो अलग-अलग संख्याओं पर परिमाणीकरण के अलावा प्राकृतिक संख्याओं के सेट पर परिमाणीकरण की अनुमति देकर अंकगणितीय पदानुक्रम से भिन्न होते हैं। ये क्षेत्र सुव्यवस्था और वृक्षों के सिद्धांतों से जुड़े हुए हैं; उदाहरण के लिए अनंत शाखाओं के बिना संगंणकताल (नॉनबाइनरी) पेड़ों के सभी सूचकांकों का सेट स्तर के लिए पूरा हो गया है <math>\Pi^1_1</math> विश्लेषणात्मक पदानुक्रम की। प्रभावी वर्णनात्मक सेट सिद्धांत के क्षेत्र में ट्यूरिंग रिड्यूसिबिलिटी और हाइपरअरिथमेटिकल रिड्यूसबिलिटी दोनों महत्वपूर्ण हैं। [[समुच्चय सिद्धान्त]] में [[निर्माण की डिग्री]] की और भी सामान्य धारणा का अध्ययन किया जाता है।
+संगंणनीयता सिद्धान्त में इस क्षेत्र की सामान्यीकृत धारणाओं का अध्ययन सम्मिलित है जैसे कि अंकगणित अपचेयता, [[अंकगणितीय कमी|अंकगणितीय अपचयन]] और अल्फा पुनरावर्तन सिद्धांत | α-पुनरावर्तन सिद्धांत, जैसा कि 1990 में सैक्स द्वारा वर्णित है।<ref name="Sacks_1990"/>इन सामान्यीकृत धारणाओं में अपचेयक सम्मिलित हैं जिन्हें ट्यूरिंग यंत्रों द्वारा निष्पादित नहीं किया जा सकता है, लेकिन फिर भी ट्यूरिंग अपचेयक  के प्राकृतिक सामान्यीकरण हैं। इन अध्ययनों में [[विश्लेषणात्मक पदानुक्रम]] की जांच करने के दृष्टिकोण सम्मिलित हैं जो अलग-अलग संख्याओं पर परिमाणीकरण के अतिरिक्त प्राकृतिक संख्याओं के समुच्चय पर परिमाणीकरण की अनुमति देकर अंकगणितीय पदानुक्रम से भिन्न होते हैं। ये क्षेत्र सुव्यवस्था और वृक्षों के सिद्धांतों से जुड़े हुए हैं; उदाहरण के लिए अनंत शाखाओं के बिना संगंणकताल पेड़ों के सभी सूचकांकों का समुच्चय स्तर के लिए पूरा हो गया है <math>\Pi^1_1</math> विश्लेषणात्मक पदानुक्रम की। प्रभावी वर्णनात्मक समुच्चय सिद्धांत के क्षेत्र में ट्यूरिंग अपचेयता और अत्यंत अंक-सम्बन्धी अपचेयक दोनों ही महत्वपूर्ण हैं। [[समुच्चय सिद्धान्त]] में [[निर्माण की डिग्री|निर्माण की श्रेणी]] की और भी सामान्य धारणा का अध्ययन किया जाता है।
 === सतत संगणनीयता सिद्धांत ===
-डिजिटल संगणना के लिए संगणनीयता सिद्धांत अच्छी तरह से विकसित है। [[एनालॉग गणना]] के लिए संगंणनीयता सिद्धांत कम विकसित है जो [[एनालॉग कंप्यूटर]], [[एनालॉग सिग्नल प्रोसेसिंग]], [[एनालॉग इलेक्ट्रॉनिक्स]], [[तंत्रिका नेटवर्क]] और निरंतर-समय [[नियंत्रण सिद्धांत]] में होता है, जो [[अंतर समीकरण]]ों और निरंतर गतिशील प्रणालियों द्वारा तैयार किया जाता है।<ref name="Orponen_1997"/><ref name="Moore_1996"/>उदाहरण के लिए, संगणना के मॉडल जैसे ब्लम-शब-स्माइल मशीन मॉडल ने वास्तविक पर औपचारिक संगणना की है।
+डिजिटल संगणना के लिए संगणनीयता सिद्धांत अच्छी तरह से विकसित है। [[एनालॉग गणना]] के लिए संगंणनीयता सिद्धांत कम विकसित है जो [[एनालॉग कंप्यूटर]], [[एनालॉग सिग्नल प्रोसेसिंग|एनालॉग संकेत प्रद्योगिकी]], [[एनालॉग इलेक्ट्रॉनिक्स|एनालॉग विद्युतीय]], [[तंत्रिका नेटवर्क|तंत्रिका]] और निरंतर-समय [[नियंत्रण सिद्धांत]] में होता है, जो [[अंतर समीकरण|अंतर समीकरणों]] और निरंतर गतिशील प्रणालियों द्वारा तैयार किया जाता है।<ref name="Orponen_1997"/><ref name="Moore_1996"/>उदाहरण के लिए, संगणना के प्रारूप जैसे ब्लम-शब-स्माइल यंत्र प्रारूप ने वास्तविक पर औपचारिक संगणना की है।
-== निश्चितता, प्रमाण और संगणनीयता के बीच संबंध ==
+== निश्चितता, प्रमाण और संगणनीयता के मध्य संबंध ==
-प्राकृतिक संख्याओं के एक सेट की ट्यूरिंग डिग्री और प्रथम-क्रम तर्क का उपयोग करके उस सेट को परिभाषित करने की कठिनाई (अंकगणितीय पदानुक्रम के संदर्भ में) के बीच घनिष्ठ संबंध हैं। प्रथम-क्रम सूत्र। ऐसा ही एक संबंध पोस्ट के प्रमेय द्वारा सटीक बनाया गया है। कर्ट गोडेल ने अपने गोडेल की पूर्णता प्रमेय और गोडेल की अपूर्णता प्रमेय के प्रमाण में एक कमजोर संबंध का प्रदर्शन किया। गोडेल के प्रमाणों से पता चलता है कि प्रभावी प्रथम-क्रम सिद्धांत के तार्किक परिणामों का सेट एक [[पुनरावर्ती गणना योग्य सेट]] है, और यदि सिद्धांत पर्याप्त मजबूत है तो यह सेट अगणनीय होगा। इसी तरह, तर्स्की की अपरिभाष्यता प्रमेय की व्याख्या निश्चितता और संगणनीयता दोनों के संदर्भ में की जा सकती है।
+प्राकृतिक संख्याओं के एक समुच्चय की ट्यूरिंग श्रेणी और प्रथम-क्रम तर्क का उपयोग करके उस समुच्चय को परिभाषित करने की कठिनाई अंकगणितीय पदानुक्रम के संदर्भ में के मध्य घनिष्ठ संबंध हैं। प्रथम-क्रम सूत्र, ऐसा ही एक संबंध पोस्ट के प्रमेय द्वारा सटीक बनाया गया है। कर्ट गोडेल ने अपने गोडेल की पूर्णता प्रमेय और गोडेल की अपूर्णता प्रमेय के प्रमाण में एक कमजोर संबंध का प्रदर्शन किया। गोडेल के प्रमाणों से पता चलता है कि प्रभावी प्रथम-क्रम सिद्धांत के तार्किक परिणामों का समुच्चय एक [[पुनरावर्ती गणना योग्य सेट|पुनरावर्ती गणनीय समुच्चय]] है, और यदि सिद्धांत पर्याप्त प्रबल है तो यह समुच्चय अगणनीय होगा। इसी तरह, तर्स्की की अपरिभाष्यता प्रमेय की व्याख्या निश्चितता और संगणनीयता दोनों के संदर्भ में की जा सकती है।
-संगंणनीयता सिद्धांत दूसरे क्रम अंकगणित से भी जुड़ा हुआ है, प्राकृतिक संख्याओं का औपचारिक सिद्धांत और प्राकृतिक संख्याओं का सेट। तथ्य यह है कि कुछ सेट संगणनीय या अपेक्षाकृत संगणनीय हैं, इसका अर्थ अक्सर यह होता है कि इन सेटों को दूसरे क्रम के अंकगणित के कमजोर उप-प्रणालियों में परिभाषित किया जा सकता है। रिवर्स मैथमेटिक्स का प्रोग्राम इन सबसिस्टम्स का उपयोग प्रसिद्ध गणितीय प्रमेयों में निहित गैर-संगंणनीयता को मापने के लिए करता है। 1999 में, सिम्पसन<ref name="Simpson_1999"/>दूसरे क्रम के अंकगणित और उलटे गणित के कई पहलुओं पर चर्चा की।
+संगंणनीयता सिद्धांत दूसरे क्रम अंकगणित से भी जुड़ा हुआ है, प्राकृतिक संख्याओं का औपचारिक सिद्धांत और प्राकृतिक संख्याओं का समुच्चय है। तथ्य यह है कि कुछ समुच्चय संगणनीय या अपेक्षाकृत संगणनीय हैं, इसका अर्थ प्रायः यह होता है कि इन समुच्चयों को दूसरे क्रम के अंकगणित के कमजोर उप-प्रणालियों में परिभाषित किया जा सकता है। प्रतिलोम गणितीय का कार्य इन उप-प्रणाली का उपयोग प्रसिद्ध गणितीय प्रमेयों में निहित गैर-संगंणनीयता को मापने के लिए करता है। 1999 में, सिम्पसन ने <ref name="Simpson_1999"/>दूसरे क्रम के अंकगणित और प्रतिलोम गणित के कई पहलुओं पर चर्चा की।
-प्रूफ थ्योरी के क्षेत्र में दूसरे क्रम के अंकगणित और पीनो अंकगणित के अध्ययन के साथ-साथ [[पियानो अंकगणित]] की तुलना में कमजोर प्राकृतिक संख्याओं के औपचारिक सिद्धांत शामिल हैं। इन कमजोर प्रणालियों की ताकत को वर्गीकृत करने का एक तरीका यह है कि कौन से संगणनीय कार्य प्रणाली को कुल कार्य साबित कर सकते हैं।<ref name="Fairtlough-Wainer_1998"/>उदाहरण के लिए, [[आदिम पुनरावर्ती अंकगणित]] में कोई भी संगणनीय फलन जो प्रमाणित रूप से कुल है, वास्तव में [[आदिम पुनरावर्ती कार्य]] है, जबकि पियानो अंकगणित यह साबित करता है कि [[एकरमैन समारोह]] जैसे कार्य, जो आदिम पुनरावर्ती नहीं हैं, कुल हैं। हालाँकि, पीनो अंकगणित में प्रत्येक कुल संगणनीय कार्य सिद्ध रूप से कुल नहीं है; ऐसे फलन का एक उदाहरण गुडस्टीन की प्रमेय द्वारा प्रदान किया गया है।
+सिद्ध प्रमेय के क्षेत्र में दूसरे क्रम के अंकगणित अध्ययन के साथ-साथ [[पियानो अंकगणित|पीनो अंकगणित]] की तुलना में दुर्बल प्राकृतिक संख्याओं के औपचारिक सिद्धांत सम्मिलित हैं। इन कमजोर प्रणालियों की शक्ति को वर्गीकृत करने का एक तरीका यह है कि कौन से संगणनीय कार्य प्रणाली को कुल कार्य सिद्ध कर सकते हैं।<ref name="Fairtlough-Wainer_1998"/>उदाहरण के लिए, [[आदिम पुनरावर्ती अंकगणित|प्राथमिक पुनरावर्ती अंकगणित]] में कोई भी संगणनीय फलन जो प्रमाणित रूप से पूर्ण है, वास्तव में [[आदिम पुनरावर्ती कार्य|प्राथमिक पुनरावर्ती कार्य]] है, जबकि पीनो अंकगणित यह प्रमाणित करता है कि [[एकरमैन समारोह|एकरमैन फलन]] जैसे कार्य, जो प्राथमिक पुनरावर्ती नहीं हैं। यद्यपि, पीनो अंकगणित में प्रत्येक कुल संगणनीय कार्य सिद्ध रूप से पूरा नहीं है; ऐसे फलन का एक उदाहरण गुडस्टीन की प्रमेय द्वारा प्रदान किया गया है।
 == नाम ==
-संगणनीयता और इसके सामान्यीकरण से संबंधित गणितीय तर्क के क्षेत्र को इसके शुरुआती दिनों से ही पुनरावर्तन सिद्धांत कहा जाता है। रॉबर्ट आई। सोरे, क्षेत्र के एक प्रमुख शोधकर्ता ने प्रस्तावित किया है<ref name="Soare_1996"/>इसके बजाय क्षेत्र को संगंणनीयता सिद्धांत कहा जाना चाहिए। उनका तर्क है कि संगंणनीय शब्द का उपयोग करने वाली ट्यूरिंग की शब्दावली क्लेन द्वारा पेश किए गए पुनरावर्ती शब्द का उपयोग करने वाली शब्दावली की तुलना में अधिक स्वाभाविक और अधिक व्यापक रूप से समझी जाती है। कई समकालीन शोधकर्ताओं ने इस वैकल्पिक शब्दावली का प्रयोग करना शुरू कर दिया है।<ref group="nb" name="NB_MathSciNet"/>ये शोधकर्ता आंशिक पुनरावर्ती कार्य और पुनरावर्ती गणना योग्य (re.e.) सेट के बजाय आंशिक गणना योग्य कार्य और गणना योग्य गणना योग्य (सी.ई.) सेट जैसी शब्दावली का भी उपयोग करते हैं। हालांकि, सभी शोधकर्ताओं को आश्वस्त नहीं किया गया है, जैसा कि फोर्टनाउ द्वारा समझाया गया है<ref name="Fortnow_2004"/>और सिम्पसन।<ref name="Simpson_1998"/>कुछ टिप्पणीकारों का तर्क है कि नाम पुनरावर्तन सिद्धांत और संगणनीयता सिद्धांत दोनों ही इस तथ्य को व्यक्त करने में विफल हैं कि संगणनीयता सिद्धांत में अध्ययन की जाने वाली अधिकांश वस्तुएँ संगणनीय नहीं हैं।<ref name="Friedman_1998"/>
+संगणनीयता और इसके सामान्यीकरण से संबंधित गणितीय तर्क के क्षेत्र को प्रारंभिक दिनों से ही इसे पुनरावर्तन सिद्धांत कहा जाता है। रॉबर्ट आई सोरे,को क्षेत्र के एक प्रमुख शोधकर्ता ने प्रस्तावित किया है<ref name="Soare_1996"/> की इसके अतिरिक्त क्षेत्र को संगंणनीयता सिद्धांत कहा जाना चाहिए। उनका तर्क है कि संगंणनीय शब्द का उपयोग करने वाली ट्यूरिंग की शब्दावली क्लेन द्वारा पेश किए गए पुनरावर्ती शब्द का उपयोग करने वाली शब्दावली की अपेक्षा अधिक स्वाभाविक और व्यापक रूप से समझी जाती है। कई समकालीन शोधकर्ताओं ने इस वैकल्पिक शब्दावली का प्रयोग करना प्रारम्भ कर दिया है।<ref group="nb" name="NB_MathSciNet"/>ये शोधकर्ता आंशिक पुनरावर्ती कार्य और पुनरावर्ती गणनीय समुच्चय के अतिरिक्त आंशिक गणनीय कार्य और गणनीय (सी.ई.) समुच्चय जैसी शब्दावली का भी प्रयोग करते हैं। यद्यपि, सभी शोधकर्ताओं को आश्वस्त नहीं किया गया है, जैसा कि फोर्टनाउ द्वारा समझाया गया है<ref name="Fortnow_2004"/>और सिम्पसन जैसे<ref name="Simpson_1998"/>कुछ टिप्पणीकारों का तर्क है कि नाम पुनरावर्तन सिद्धांत और संगणनीयता सिद्धांत दोनों ही इस तथ्य को व्यक्त करने में विफल हैं कि संगणनीयता सिद्धांत में अध्ययन की जाने वाली अधिकांश वस्तुएँ संगणनीय नहीं हैं।<ref name="Friedman_1998"/>
-में, रोजर्स<ref name="Rogers_1987"/>ने सुझाव दिया है कि संगणनीयता सिद्धांत की एक प्रमुख संपत्ति यह है कि इसके परिणाम और संरचनाएं प्राकृतिक संख्याओं पर संगणनीय आक्षेपों के तहत अपरिवर्तनीय होनी चाहिए (यह सुझाव ज्यामिति में [[एर्लांगेन कार्यक्रम]] के विचारों पर आधारित है)। विचार यह है कि एक गणनीय आक्षेप केवल सेट में किसी भी संरचना को इंगित करने के बजाय सेट में संख्याओं का नाम बदलता है, जितना कि यूक्लिडियन विमान के घूर्णन से उस पर खींची गई रेखाओं के किसी भी ज्यामितीय पहलू को नहीं बदलता है। चूंकि किसी भी दो अनंत संगणनीय सेट एक संगणनीय आक्षेप से जुड़े हुए हैं, यह प्रस्ताव सभी अनंत संगणनीय सेटों की पहचान करता है (परिमित संगणनीय सेटों को तुच्छ के रूप में देखा जाता है)। रोजर्स के अनुसार, संगणनीयता सिद्धांत में रुचि के सेट गैर-गणना योग्य सेट हैं, जो प्राकृतिक संख्याओं के संगणनीय आक्षेपों द्वारा तुल्यता वर्गों में विभाजित हैं।
+में, रोजर्स<ref name="Rogers_1987"/>ने सुझाव दिया है कि संगणनीयता सिद्धांत की एक प्रमुख संपत्ति यह है कि इसके परिणाम और संरचनाएं प्राकृतिक संख्याओं पर संगणनीय आक्षेपों के तहत अपरिवर्तनीय होनी चाहिए एवं यह सुझाव ज्यामिति में [[एर्लांगेन कार्यक्रम|एर्लांगेन सभा]] के विचारों पर आधारित है। विचार यह है कि एक गणनीय आक्षेप केवल समुच्चय में किसी भी संरचना को इंगित करने के अतिरिक्त समुच्चय में संख्याओं का नाम परिवर्तन करता है, जितना कि यूक्लिडियन समतल के घूर्णन से उस पर खींची गई रेखाओं के किसी भी ज्यामितीय दृष्टिकोण को नहीं बदलता है। यद्यपि किसी दो अनंत संगणनीय समुच्चय एक संगणनीय आक्षेप से जुड़े हुए हैं, यह प्रस्ताव सभी अनंत संगणनीय समुच्चयों की पहचान करता है तथा अनंत संगणनीय समुच्चयों को नगण्य रूप में देखा जाता है। रोजर्स के अनुसार, संगणनीयता सिद्धांत में रुचि अन्य-गणना के समुच्चय योग्य हैं, जो प्राकृतिक संख्याओं के संगणनीय आक्षेपों द्वारा तुल्यता वर्गों में विभाजित हैं।
-== पेशेवर संगठन ==
+== व्यावसायिक संगठन ==
-संगंणनीयता सिद्धांत के लिए मुख्य पेशेवर संगठन [[प्रतीकात्मक तर्क के लिए एसोसिएशन]] है, जो हर साल कई शोध सम्मेलन आयोजित करता है। इंटरडिसिप्लिनरी रिसर्च एसोसिएशन [[यूरोप में संगणनीयता]] (सीआईई) भी वार्षिक सम्मेलनों की एक श्रृंखला आयोजित करता है।
+संगंणनीयता सिद्धांत के लिए एशोसिएशन फॉर सिंबॉलिक लॉजिक एक मुख्य अनुभवी संगठन है, जो प्रत्येक वर्ष अनेक शोध सम्मेलनो का आयोजन करता है,एवं अंतःविषय अनुसंधान संघ [[यूरोप में संगणनीयता|कम्प्युटेबिलिटी इन यूरोप]] (सीआईइ) भी वार्षिक सम्मेलनों की एक श्रृंखला आयोजित करता है।
 == यह भी देखें ==
 {{Portal|Philosophy}}
-* [[रिकर्सन (कंप्यूटर विज्ञान)]]
+* [[रिकर्सन (कंप्यूटर विज्ञान)|पुनरावर्तन (कंप्यूटर विज्ञान)]]
 * [[संगणनीयता तर्क]]
 * ट्रांसकंप्यूटेशनल समस्या
@@ Line 232: / Line 225: @@
 {{Computer science}}
 {{Mathematical logic}}
-[[Category: कम्प्यूटेबिलिटी सिद्धांत | कम्प्यूटेबिलिटी सिद्धांत ]] [[Category: गणितीय तर्क | सी]]
-[[Category: Machine Translated Page]]
+[[Category:Articles containing German-language text]]
+[[Category:Articles with hatnote templates targeting a nonexistent page]]
+[[Category:CS1]]
+[[Category:CS1 maint]]
+[[Category:Collapse templates]]
+[[Category:Commons category link from Wikidata]]
+[[Category:Commons category link is the pagename]]
 [[Category:Created On 03/02/2023]]
+[[Category:Machine Translated Page]]
+[[Category:Mathematics navigational boxes]]
+[[Category:Navbox orphans]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists]]
+[[Category:Pages with empty portal template]]
+[[Category:Pages with reference errors]]
+[[Category:Pages with script errors]]
+[[Category:Philosophy and thinking navigational boxes]]
+[[Category:Portal-inline template with redlinked portals]]
+[[Category:Portal templates with redlinked portals]]
+[[Category:Sidebars with styles needing conversion]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Translated in Hindi]]
+[[Category:Templates Vigyan Ready]]
+[[Category:Templates generating microformats]]
+[[Category:Templates that are not mobile friendly]]
+[[Category:Templates using TemplateData]]
+[[Category:Wikipedia metatemplates]]
+[[Category:कम्प्यूटेबिलिटी सिद्धांत| कम्प्यूटेबिलिटी सिद्धांत ]]
+[[Category:गणितीय तर्क| सी]]

v t e कंप्यूटर विज्ञान
Note: This template roughly follows the 2012 ACM Computing Classification System.
हार्डवेयर	मुद्रित सर्किट बोर्ड परिधीय एकीकृत परिपथ बड़े पैमाने पर एकीकरण चिप पर सिस्टम (एसओसी) ऊर्जा की खपत (ग्रीन कंप्यूटिंग) इलेक्ट्रॉनिक डिजाइन स्वचालन हार्डवेयर एक्सिलरेशन
कंप्यूटर सिस्टम संगठन	कंप्यूटर आर्किटेक्चर अंतः स्थापित प्रणाली रीयल-टाइम कंप्यूटिंग निर्भरता
नेटवर्क	नेटवर्क आर्किटेक्चर नेटवर्क प्रोटोकॉल नेटवर्क घटक नेटवर्क अनुसूचक नेटवर्क प्रदर्शन मूल्यांकन नेटवर्क सेवा
सॉफ्टवेयर संगठन	दुभाषिया मध्यस्थ आभासी मशीन ऑपरेटिंग सिस्टम सॉफ्टवेयर गुणवत्ता
सॉफ्टवेयर नोटेशन और टूल्स	प्रोग्रामिंग प्रतिमान प्रोग्रामिंग भाषा संकलक डोमेन-विशिष्ट भाषा मॉडलिंग भाषा सॉफ्टवेयर फ्रेमवर्क समन्वित विकास पर्यावरण सॉफ्टवेयर विन्यास प्रबंधन सॉफ्टवेयर लाइब्रेरी सॉफ्टवेयर रिपोजिटरी
सॉफ्टवेयर डेवलपमेंट	नियंत्रण चर सॉफ्टवेयर विकास प्रक्रिया आवश्यकताओं के विश्लेषण सॉफ्टवेर डिज़ाइन सॉफ्टवेयर निर्माण सॉफ्टवेयर परिनियोजन सॉफ्टवेयर इंजीनियरिंग सॉफ्टवेयर की रखरखाव प्रोग्रामिंग टीम ओपन-सोर्स मॉडल
गणना का सिद्धांत	गणना का मॉडल औपचारिक भाषा ऑटोमेटा सिद्धांत कम्प्यूटेबिलिटी सिद्धांत कम्प्यूटेशनल जटिलता सिद्धांत तर्क शब्दार्थ
कलन विधि	एल्गोरिदम डिजाइन एल्गोरिदम का विश्लेषण एल्गोरिदमिक दक्षता यादृच्छिक एल्गोरिदम कम्प्यूटेशनल ज्यामिति
कंप्यूटिंग का गणित	गणित पृथक करें संभावना सांख्यिकी गणितीय सॉफ्टवेयर सूचना सिद्धांत गणितीय विश्लेषण संख्यात्मक विश्लेषण सैद्धांतिक कंप्यूटर विज्ञान
सूचना प्रणाली	डेटाबेस प्रबंधन प्रणाली सूचना भंडारण प्रणाली उद्यम सूचना प्रणाली सामाजिक सूचना प्रणाली भौगोलिक सूचना प्रणाली निर्णय समर्थन प्रणाली प्रक्रिया नियंत्रण प्रणाली मल्टीमीडिया सूचना प्रणाली डेटा माइनिंग डिजिटल लाइब्रेरी कंप्यूटिंग प्लेटफॉर्म डिजिटल विपणन वर्ल्ड वाइड वेब सूचना की पुनर्प्राप्ति
सुरक्षा	क्रिप्टोग्राफी औपचारिक तरीके सुरक्षा सेवाएं अतिक्रमण संसूचन प्रणाली हार्डवेयर सुरक्षा नेटवर्क सुरक्षा सूचना सुरक्षा आवेदन सुरक्षा
मानव-कंप्यूटर संपर्क	पारस्परिक प्रभाव वाली डिज़ाइन सामाजिक कंप्यूटिंग सर्वव्यापक कंप्यूटिंग विज़ुअलाइज़ेशन एक्सेसिबिलिटी
Concurrency	समवर्ती कंप्यूटिंग समानांतर कंप्यूटिंग वितरित अभिकलन मल्टीथ्रेडिंग मल्टीप्रोसेसिंग
कृत्रिम बुद्धि	प्राकृतिक भाषा प्रसंस्करण ज्ञान प्रतिनिधित्व और तर्क कंप्यूटर दृष्टी स्वचालित योजना और समय-निर्धारण खोज पद्धति नियंत्रण विधि कृत्रिम बुद्धि का दर्शन डिस्ट्रिब्यूटेड आर्टिफिशियल इंटेलिजेंस
मशीन लर्निंग	पर्यवेक्षित अध्ययन अनपर्यवेक्षित लर्निंग सुदृढीकरण सीखना बहु-कार्य सीखने क्रॉस-सत्यापन
ग्राफिक्स	एनिमेशन रेंडरिंग छवि हेरफेर ग्राफ़िक्स प्रोसेसिंग युनिट मिश्रित वास्तविकता आभासी वास्तविकता छवि संपीड़न सॉलिड मॉडलिंग
एप्लाइड कंप्यूटिंग	ई-कॉमर्स उपक्रम सॉफ्टवेयर कम्प्यूटेशनल गणित कम्प्यूटेशनल भौतिकी कम्प्यूटेशनल केमिस्ट्री कम्प्यूटेशनल बायोलॉजी कम्प्यूटेशनल सामाजिक विज्ञान कम्प्यूटेशनल इंजीनियरिंग कम्प्यूटेशनल हेल्थकेयर डिजिटल कला इलेक्ट्रॉनिक प्रकाशन सायबर युद्ध इलेक्ट्रॉनिक वोटिंग वीडियो गेम वर्ड प्रोसेसिंग संचालन अनुसंधान शैक्षिक प्रौद्योगिकी दस्तावेज़ प्रबंधन
Category Outline WikiProject Commons

Anonymous

Search

संगणनीयता सिद्धांत: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 11:29, 15 September 2023

Contents

परिचय

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

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

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

अन्य कमी

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

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

संख्यांकन

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

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

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

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

आवृत्ति गणना

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

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

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

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

नाम

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

संगणनीयता सिद्धांत: Difference between revisions

Latest revision as of 11:29, 15 September 2023

परिचय

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

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

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

अन्य कमी

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

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

संख्यांकन

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

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

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

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

आवृत्ति गणना

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

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

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

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

नाम

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

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories