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

Revision as of 23:47, 9 February 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व्यस्त बीवर कार्य किसी भी संगणनीय कार्य की तुलना में तेज़ी से बढ़ता है।इसलिए, यह गणना योग्य नहीं है;केवल कुछ ही मान ज्ञात हैं।

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

अन्य कमी

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

मजबूत कटौती में शामिल हैं:

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

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

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

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

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

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

चावल का प्रमेय और अंकगणितीय पदानुक्रम

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

उल्टा गणित

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

नंबरिंग

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

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

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

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

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

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

ऑटोमोर्फिज्म समस्याएं

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

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

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

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

आवृत्ति गणना

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

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

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

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

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

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

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

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

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

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

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

नाम

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

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

पेशेवर संगठन

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

यह भी देखें

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

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

संदर्भ

↑ 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.
↑ ^2.0 ^2.1 Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. pp. 300, 376. ISBN 0-7204-2103-9.
↑ 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.
↑ ^6.0 ^6.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.
↑ 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.
↑ ^9.0 ^9.1 Soare, Robert Irving (1987). Recursively Enumerable Sets and Degrees. Perspectives in Mathematical Logic. Springer-Verlag. ISBN 0-387-15299-7.
↑ ^10.0 ^10.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.
↑ ^12.0 ^12.1 ^12.2 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.
↑ 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.
↑ ^14.0 ^14.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.
↑ ^15.0 ^15.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)

Cite error: <ref> tag with name "Feferman_1990" defined in <references> is not used in prior text.

Cite error: <ref> tag with name "Rado_1962" defined in <references> is not used in prior text.

अग्रिम पठन

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-2] Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.

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

[NB_MathSciNet-26] 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.

[Soare_2011-1] 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-3] 2.0 ^2.1 Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. pp. 300, 376. ISBN 0-7204-2103-9.

[Davis_1965-4] 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-5] 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-6] 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-7] 6.0 ^6.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.

[Ershov-Goncharov-Nerode-Remmel-1998-8] 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-9] Cutland, Nigel J. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 0-521-29465-7.

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

[Soare_1996-11] 10.0 ^10.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-12] 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.

[Post_1944-13] 12.0 ^12.1 ^12.2 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.

[Shore-Slaman_1999-14] 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-15] 14.0 ^14.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.

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

[Harrington-Soare_1991-17] 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-18] 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-19] 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-20] Conference on Logic, Computability and Randomness, 2007-01-13 [2007-01-11], archived from the original on 2007-12-26

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

[Orponen_1997-23] 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-24] 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-25] 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-27] 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-28] 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-29] 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-30] 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]

[nb 1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[nb 2]

[20]

[21]

[22]

[23]

[nb 3]

[24]

[25]

[26]

[27]

@@ Line 46: / Line 46: @@
 == ट्यूरिंग संगंणनीयता ==
-संगंणनीयता सिद्धांत में अध्ययन की गई संगंणनीयता का मुख्य रूप 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"/>शब्दावली के बारे में अतिरिक्त टिप्पणियाँ दी।
+μ-पुनरावर्ती कार्यों के साथ-साथ एक अलग परिभाषा के संदर्भ में परिभाषा {{lang|de|रिकर्सिव}} गोडेल द्वारा किए गए कार्यों ने ट्यूरिंग यंत्र द्वारा गणना योग्य सेट और कार्यों के लिए पारंपरिक नाम पुनरावर्ती का नेतृत्व किया। निर्णायक शब्द जर्मन शब्द से उपजा है, जिसका उपयोग ट्यूरिंग और अन्य के मूल पत्रों में किया गया था। समकालीन उपयोग में, संगंणनीय कार्य शब्द की विभिन्न परिभाषाएँ हैं: निगेल जे. कटलैंड के अनुसार,<ref name="Cutland_1980"/>यह एक आंशिक पुनरावर्ती कार्य है जो कुछ इनपुट के लिए अपरिभाषित हो सकता है, जबकि रॉबर्ट आई सोरे के अनुसार<ref name="Soare_1987"/>यह कुल पुनरावर्ती समतुल्य एवं सामान्य पुनरावर्ती कार्य है। यह लेख इन सम्मेलनों में से दूसरे का अनुसरण करता है। 1996 में, सोरे ने <ref name="Soare_1996"/>शब्दावली के बारे में अतिरिक्त टिप्पणियाँ दी।
-प्राकृतिक संख्याओं का प्रत्येक सेट गणना योग्य नहीं है। [[रुकने की समस्या]], जो इनपुट 0 पर रुकने वाली ट्यूरिंग मशीनों के विवरण का सेट है, एक गैर-गणना योग्य सेट का एक प्रसिद्ध उदाहरण है। कई गैर-गणना योग्य सेटों का अस्तित्व इस तथ्य से अनुसरण करता है कि केवल [[गणनीय सेट]] ट्यूरिंग मशीन हैं, और इस प्रकार केवल गणना करने योग्य कई सेट हैं, लेकिन कैंटर के प्रमेय के अनुसार, प्राकृतिक संख्याओं के सर्वाधिक सेट हैं।
+प्राकृतिक संख्याओं का प्रत्येक सेट गणना योग्य नहीं है। [[रुकने की समस्या]], जो इनपुट 0 पर रुकने वाली ट्यूरिंग यंत्रों के विवरण का सेट है, एक गैर-गणना योग्य सेट का एक प्रसिद्ध उदाहरण है। कई गैर-गणना योग्य सेटों का अस्तित्व इस तथ्य से अनुसरण करता है कि केवल [[गणनीय सेट]] ट्यूरिंग यंत्र हैं, और इस प्रकार केवल गणना करने योग्य कई सेट हैं, लेकिन कैंटर के प्रमेय के अनुसार, प्राकृतिक संख्याओं के सर्वाधिक सेट हैं।
-यद्यपि लड़खड़ाते हुए समस्या की गणना नहीं की जा सकती है, परन्तु प्रोग्राम के निष्पादन का अनुकरण करना और रुकने वाले प्रोग्रामों की एक अनंत सूची तैयार करना संभव है। इस प्रकार लड़खड़ाते हुए समस्या की  संगंणनीयी इन्युमरेबल सेट संगंणकताली इन्युमरेबल (सी.ई.) सेट का एक उदाहरण है, जो एक सेट है जिसे ट्यूरिंग मशीन द्वारा एन्यूमरेट किया जा सकता है संगंणकताल इन्युमरेबल के लिए अन्य शर्तें रिकर्सिवली इन्युमरेबल और सेमीडिसिडेबल शामिल हैं। समतुल्य रूप से, एक सेट सी.इ है, यदि यह केवल कुछ संगंणकताल कार्य की सीमा है। सी.ई. सेट, यद्यपि सामान्य रूप से निर्णायक नहीं हैं, इसे संगंणनीयता सिद्धांत में विस्तार से अध्ययन किया गया है।
+यद्यपि लड़खड़ाते हुए समस्या की गणना नहीं की जा सकती है, परन्तु प्रोग्राम के निष्पादन का अनुकरण करना और रुकने वाले प्रोग्रामों की एक अनंत सूची तैयार करना संभव है। इस प्रकार लड़खड़ाते हुए समस्या की  संगंणनीयी इन्युमरेबल सेट संगंणकताली इन्युमरेबल (सी.ई.) सेट का एक उदाहरण है, जो एक सेट है जिसे ट्यूरिंग यंत्र द्वारा एन्यूमरेट किया जा सकता है संगंणकताल इन्युमरेबल के लिए अन्य शर्तें रिकर्सिवली इन्युमरेबल और सेमीडिसिडेबल शामिल हैं। समतुल्य रूप से, एक सेट सी.इ है, यदि यह केवल कुछ संगंणकताल कार्य की सीमा है। सी.ई. सेट, यद्यपि सामान्य रूप से निर्णायक नहीं हैं, इसे संगंणनीयता सिद्धांत में विस्तार से अध्ययन किया गया है।
 ==अनुसंधान के क्षेत्र==
-ऊपर वर्णित संगणनीय सेटों और कार्यों के सिद्धांत के साथ आरम्भ करते हुए, संगणनीयता सिद्धांत के क्षेत्र में कई निकट संबंधी विषयों के अध्ययन को शामिल किया गया है। ये अनुसंधान के स्वतंत्र क्षेत्र नहीं हैं: इनमें से प्रत्येक क्षेत्र दूसरों से विचार और परिणाम प्राप्त करता है, और अधिकांश संगंणनीयता सिद्धांतकार उनमें से अधिकांश से परिचित हैं।
+ऊपर वर्णित संगणनीय सेटों और कार्यों के सिद्धांत के साथ आरम्भ करते हुए, संगणनीयता सिद्धांत के क्षेत्र में कई निकट संबंधी विषयों के अध्ययन को शामिल किया गया है। ये अनुसंधान के स्वतंत्र क्षेत्र नहीं हैं: इनमें से प्रत्येक क्षेत्र दूसरों से विचार और परिणाम प्राप्त करता है, और अधिकांश संगंणनीयता सिद्धांतकार उनमें से अधिकांश परिचित हैं।
-=== सापेक्ष संगणनीयता और ट्यूरिंग डिग्री ===
+=== सापेक्ष संगणनीयता और ट्यूरिंग श्रेणी ===
 {{Main|Turing reduction|Turing degree}}
-गणितीय तर्क में संगणनीयता सिद्धांत परंपरागत रूप से सापेक्ष संगणनीयता पर केंद्रित रहा है, 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 में, पोस्ट<ref name="Post_1944"/>पूछा गया कि क्या प्रत्येक संगणनीय गणना योग्य सेट या तो संगणनीय है या ट्यूरिंग डिग्री # हाल्टिंग समस्या के लिए ट्यूरिंग समतुल्य है, अर्थात, क्या उन दोनों के बीच ट्यूरिंग डिग्री मध्यवर्ती के साथ कोई संगणनीय गणना योग्य सेट नहीं है।
 मध्यवर्ती परिणामों के रूप में, [[सरल सेट]], [[अतिसरल सेट]] और हाइपरहाइपरसिंपल सेट जैसे कंप्यूटेशनल रूप से गणना योग्य सेटों के प्राकृतिक प्रकारों को परिभाषित करें। पोस्ट ने दिखाया कि ये सेट संगंणकताल सेट और कई-एक रिड्यूसबिलिटी के संबंध में हॉल्टिंग समस्या के बीच सख्ती से हैं। पोस्ट ने यह भी दिखाया कि उनमें से कुछ ट्यूरिंग रिड्यूसबिलिटी की तुलना में अन्य रिड्यूसबिलिटी धारणाओं के तहत सख्ती से मध्यवर्ती हैं। लेकिन पोस्ट ने इंटरमीडिएट ट्यूरिंग डिग्री के गणनात्मक रूप से गणना योग्य सेटों के अस्तित्व की मुख्य समस्या को खुला छोड़ दिया; इस समस्या को पोस्ट की समस्या के रूप में जाना जाने लगा। दस वर्षों के बाद, क्लेन और पोस्ट ने 1954 में दिखाया कि गणना योग्य सेट और हॉल्टिंग समस्या के बीच मध्यवर्ती ट्यूरिंग डिग्री हैं, लेकिन वे यह दिखाने में विफल रहे कि इनमें से किसी भी डिग्री में गणना योग्य गणना योग्य सेट शामिल है। इसके तुरंत बाद, फ्रेडबर्ग और मुचनिक ने स्वतंत्र रूप से इंटरमीडिएट डिग्री के गणना योग्य सेटों के अस्तित्व को स्थापित करके पोस्ट की समस्या को हल किया। इस अभूतपूर्व परिणाम ने संगंणकताल गणना योग्य सेटों की ट्यूरिंग डिग्री का एक विस्तृत अध्ययन खोला जो एक बहुत ही जटिल और गैर-तुच्छ संरचना के अधिकारी थे।
@@ Line 74: / Line 74: @@
 ऐसे कई सेट हैं जो संगणनीय रूप से गणना योग्य नहीं हैं, और सभी सेटों की ट्यूरिंग डिग्री की जांच संगंणनीयता सिद्धांत में उतनी ही केंद्रीय है जितनी कि गणना योग्य ट्यूरिंग डिग्री की जांच। विशेष गुणों के साथ कई डिग्रियों का निर्माण किया गया: हाइपरइम्यून-मुक्त डिग्रियां जहां उस डिग्री के सापेक्ष प्रत्येक कार्य की गणना एक (असंबद्ध) संगणनीय कार्य द्वारा की जाती है; उच्च डिग्री जिसके सापेक्ष कोई एक कार्य f की गणना कर सकता है जो प्रत्येक गणना योग्य कार्य g पर हावी है, इस अर्थ में कि g के आधार पर एक स्थिर c है जैसे कि g(x) <f(x) for all x > c; [[एल्गोरिथम यादृच्छिक सेट]] युक्त यादृच्छिक डिग्री; 1-जेनेरिक सेट की 1-जेनेरिक डिग्री; और सीमित रिकर्सिव|लिमिट-संगंणनीय सेट की हॉल्टिंग प्रॉब्लम से नीचे की डिग्री।
-मनमाना (जरूरी नहीं कि संगणनीय रूप से गणना योग्य) ट्यूरिंग डिग्रियों के अध्ययन में ट्यूरिंग जंप का अध्ययन शामिल है। एक सेट ए दिया गया है, ए का ट्यूरिंग जंप प्राकृतिक संख्याओं का एक सेट है जो ऑरेकल ए के साथ चलने वाली ऑरेकल ट्यूरिंग मशीनों के लिए हाल्टिंग समस्या के समाधान को एन्कोडिंग करता है। किसी भी सेट का ट्यूरिंग जंप हमेशा मूल सेट की तुलना में उच्च ट्यूरिंग डिग्री का होता है, और फ्रीडबर्ग के एक प्रमेय से पता चलता है कि हॉल्टिंग समस्या की गणना करने वाले किसी भी सेट को दूसरे सेट के ट्यूरिंग जंप के रूप में प्राप्त किया जा सकता है। पोस्ट का प्रमेय ट्यूरिंग जंप ऑपरेशन और [[अंकगणितीय पदानुक्रम]] के बीच घनिष्ठ संबंध स्थापित करता है, जो अंकगणित में उनकी निश्चितता के आधार पर प्राकृतिक संख्याओं के कुछ सबसेट का वर्गीकरण है।
+मनमाना (जरूरी नहीं कि संगणनीय रूप से गणना योग्य) ट्यूरिंग डिग्रियों के अध्ययन में ट्यूरिंग जंप का अध्ययन शामिल है। एक सेट ए दिया गया है, ए का ट्यूरिंग जंप प्राकृतिक संख्याओं का एक सेट है जो ऑरेकल ए के साथ चलने वाली ऑरेकल ट्यूरिंग यंत्रों के लिए हाल्टिंग समस्या के समाधान को एन्कोडिंग करता है। किसी भी सेट का ट्यूरिंग जंप हमेशा मूल सेट की तुलना में उच्च ट्यूरिंग डिग्री का होता है, और फ्रीडबर्ग के एक प्रमेय से पता चलता है कि हॉल्टिंग समस्या की गणना करने वाले किसी भी सेट को दूसरे सेट के ट्यूरिंग जंप के रूप में प्राप्त किया जा सकता है। पोस्ट का प्रमेय ट्यूरिंग जंप ऑपरेशन और [[अंकगणितीय पदानुक्रम]] के बीच घनिष्ठ संबंध स्थापित करता है, जो अंकगणित में उनकी निश्चितता के आधार पर प्राकृतिक संख्याओं के कुछ सबसेट का वर्गीकरण है।
 ट्यूरिंग डिग्रियों पर हाल के शोध ने ट्यूरिंग डिग्रियों के सेट की समग्र संरचना पर ध्यान केंद्रित किया है और ट्यूरिंग डिग्रियों के सेट पर संगंणकताल रूप से गणना करने योग्य सेट हैं। शोर और स्लैमन का एक गहरा प्रमेय<ref name="Shore-Slaman_1999"/>बताता है कि ट्यूरिंग डिग्री के आंशिक क्रम में इसकी ट्यूरिंग जंप की डिग्री के लिए एक डिग्री x मैपिंग कार्य निश्चित है। Ambos-Spies और Fejer द्वारा एक सर्वेक्षण<ref name="Ambos-Spies-Fejer_2006"/>इस शोध और इसकी ऐतिहासिक प्रगति का अवलोकन देता है।
@@ Line 80: / Line 80: @@
 === अन्य कमी ===
 {{Main|Reduction (recursion theory)}}
-संगंणनीयता थ्योरी में अनुसंधान का एक सतत क्षेत्र ट्यूरिंग रिड्यूसबिलिटी के अलावा रिड्यूसबिलिटी रिलेशंस का अध्ययन करता है। डाक<ref name="Post_1944"/>कई मजबूत रिड्यूसिबिलिटी पेश की, इसलिए नाम दिया गया क्योंकि वे ट्रुथ-टेबल रिड्यूसिबिलिटी का संकेत देते हैं। एक मजबूत न्यूनीकरण को लागू करने वाली एक ट्यूरिंग मशीन कुल कार्य की गणना करेगी चाहे वह किसी भी ऑरेकल के साथ प्रस्तुत किया गया हो। कमजोर रिड्यूसिबिलिटी वे हैं जहां कमी की प्रक्रिया सभी ऑरेकल के लिए समाप्त नहीं हो सकती है; ट्यूरिंग रिड्यूसबिलिटी एक उदाहरण है।
+संगंणनीयता थ्योरी में अनुसंधान का एक सतत क्षेत्र ट्यूरिंग रिड्यूसबिलिटी के अलावा रिड्यूसबिलिटी रिलेशंस का अध्ययन करता है। डाक<ref name="Post_1944"/>कई मजबूत रिड्यूसिबिलिटी पेश की, इसलिए नाम दिया गया क्योंकि वे ट्रुथ-टेबल रिड्यूसिबिलिटी का संकेत देते हैं। एक मजबूत न्यूनीकरण को लागू करने वाली एक ट्यूरिंग यंत्र कुल कार्य की गणना करेगी चाहे वह किसी भी ऑरेकल के साथ प्रस्तुत किया गया हो। कमजोर रिड्यूसिबिलिटी वे हैं जहां कमी की प्रक्रिया सभी ऑरेकल के लिए समाप्त नहीं हो सकती है; ट्यूरिंग रिड्यूसबिलिटी एक उदाहरण है।
 मजबूत कटौती में शामिल हैं:
 : कई-एक कमी | एक-एक कमी: A, B के लिए एक-एक कम करने योग्य (या 1-कम करने योग्य) है यदि कुल संगणनीय अंतःक्षेपण फलन f ऐसा है कि प्रत्येक n A में है यदि और केवल यदि f(n) है बी में।
 : अनेक-एक न्यूनीकरण|अनेक-एक न्यूनीकरण: यह अनिवार्य रूप से एक-एक न्यूनीकरणीयता है, बिना इस बाधा के कि f अंतःक्षेपी हो। ए बी के लिए कई-एक कम करने योग्य (या एम-कम करने योग्य) है यदि कुल गणना योग्य कार्य एफ है जैसे कि प्रत्येक एन ए में है और केवल अगर एफ (एन) बी में है।
-: ट्रुथ टेबल रिडक्शन | ट्रुथ-टेबल रिड्यूसिबिलिटी: ए ट्रुथ-टेबल रिड्यूसिबल टू बी है अगर ए एक ऑरेकल ट्यूरिंग मशीन के माध्यम से बी के लिए ट्यूरिंग रिड्यूसिबल है जो दिए गए ऑरेकल की परवाह किए बिना कुल कार्य की गणना करता है। [[कैंटर स्पेस]] की कॉम्पैक्टनेस के कारण, यह कहने के बराबर है कि रिडक्शन प्रश्नों की एक सूची (केवल इनपुट पर निर्भर करता है) को एक साथ ऑरैकल में प्रस्तुत करता है, और फिर उनके उत्तरों को देखने के बाद अतिरिक्त प्रश्न पूछे बिना आउटपुट उत्पन्न करने में सक्षम होता है। प्रारंभिक प्रश्नों के लिए ऑरेकल के उत्तर के बारे में। ट्रुथ-टेबल रिड्यूसबिलिटी के कई रूपों का भी अध्ययन किया गया है।
+: ट्रुथ टेबल रिडक्शन | ट्रुथ-टेबल रिड्यूसिबिलिटी: ए ट्रुथ-टेबल रिड्यूसिबल टू बी है अगर ए एक ऑरेकल ट्यूरिंग यंत्र के माध्यम से बी के लिए ट्यूरिंग रिड्यूसिबल है जो दिए गए ऑरेकल की परवाह किए बिना कुल कार्य की गणना करता है। [[कैंटर स्पेस]] की कॉम्पैक्टनेस के कारण, यह कहने के बराबर है कि रिडक्शन प्रश्नों की एक सूची (केवल इनपुट पर निर्भर करता है) को एक साथ ऑरैकल में प्रस्तुत करता है, और फिर उनके उत्तरों को देखने के बाद अतिरिक्त प्रश्न पूछे बिना आउटपुट उत्पन्न करने में सक्षम होता है। प्रारंभिक प्रश्नों के लिए ऑरेकल के उत्तर के बारे में। ट्रुथ-टेबल रिड्यूसबिलिटी के कई रूपों का भी अध्ययन किया गया है।
 लेख में आगे की कमी (सकारात्मक, वियोगात्मक, संयोजन, रैखिक और उनके कमजोर और बंधे हुए संस्करण) पर चर्चा की गई है।
@@ Line 120: / Line 120: @@
 === कोलमोगोरोव जटिलता ===
 {{Main|Kolmogorov complexity}}
-कोल्मोगोरोव जटिलता और [[एल्गोरिथम यादृच्छिकता]] का क्षेत्र 1960 और 1970 के दशक के दौरान चैतिन, कोलमोगोरोव, लेविन, मार्टिन-लोफ और सोलोमनॉफ द्वारा विकसित किया गया था (नाम वर्णानुक्रम में यहां दिए गए हैं; अधिकांश शोध स्वतंत्र थे, और अवधारणा की एकता यादृच्छिकता उस समय समझ में नहीं आई थी)। मुख्य विचार एक सार्वभौमिक ट्यूरिंग मशीन यू पर विचार करना है और एक संख्या (या स्ट्रिंग) एक्स की जटिलता को मापने के लिए सबसे कम इनपुट पी की लंबाई के रूप में यू (पी) आउटपुट एक्स। इस दृष्टिकोण ने परिमित वस्तुओं के लिए यादृच्छिकता की धारणा को लागू करके यह निर्धारित करने के पहले तरीकों में क्रांति ला दी कि कब एक अनंत अनुक्रम (समतुल्य रूप से, प्राकृतिक संख्याओं के एक सबसेट का विशिष्ट कार्य) यादृच्छिक है या नहीं। [[कोलमोगोरोव जटिलता]] न केवल स्वतंत्र अध्ययन का विषय बन गई बल्कि प्रमाण प्राप्त करने के लिए एक उपकरण के रूप में अन्य विषयों पर भी लागू होती है।
+कोल्मोगोरोव जटिलता और [[एल्गोरिथम यादृच्छिकता]] का क्षेत्र 1960 और 1970 के दशक के दौरान चैतिन, कोलमोगोरोव, लेविन, मार्टिन-लोफ और सोलोमनॉफ द्वारा विकसित किया गया था (नाम वर्णानुक्रम में यहां दिए गए हैं; अधिकांश शोध स्वतंत्र थे, और अवधारणा की एकता यादृच्छिकता उस समय समझ में नहीं आई थी)। मुख्य विचार एक सार्वभौमिक ट्यूरिंग यंत्र यू पर विचार करना है और एक संख्या (या स्ट्रिंग) एक्स की जटिलता को मापने के लिए सबसे कम इनपुट पी की लंबाई के रूप में यू (पी) आउटपुट एक्स। इस दृष्टिकोण ने परिमित वस्तुओं के लिए यादृच्छिकता की धारणा को लागू करके यह निर्धारित करने के पहले तरीकों में क्रांति ला दी कि कब एक अनंत अनुक्रम (समतुल्य रूप से, प्राकृतिक संख्याओं के एक सबसेट का विशिष्ट कार्य) यादृच्छिक है या नहीं। [[कोलमोगोरोव जटिलता]] न केवल स्वतंत्र अध्ययन का विषय बन गई बल्कि प्रमाण प्राप्त करने के लिए एक उपकरण के रूप में अन्य विषयों पर भी लागू होती है।
 इस क्षेत्र में अभी भी कई खुली समस्याएं हैं। इस कारण से, इस क्षेत्र में हाल ही में जनवरी 2007 में एक शोध सम्मेलन आयोजित किया गया था<ref name="Logic_2007"/>और खुली समस्याओं की एक सूची<ref group="nb" name="NB_Nies"/>जोसेफ मिलर और आंद्रे नीस द्वारा बनाए रखा जाता है।
@@ Line 130: / Line 130: @@
 === ट्यूरिंग संगंणनीयता का सामान्यीकरण ===
-संगंणनीयता थ्योरी में इस क्षेत्र की सामान्यीकृत धारणाओं का अध्ययन शामिल है जैसे कि अंकगणित रिड्यूसबिलिटी, [[अंकगणितीय कमी]] और अल्फा रिकर्सन थ्योरी|α-रिकर्सन थ्योरी, जैसा कि 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"/>उदाहरण के लिए, संगणना के मॉडल जैसे ब्लम-शब-स्माइल यंत्र मॉडल ने वास्तविक पर औपचारिक संगणना की है।
 == निश्चितता, प्रमाण और संगणनीयता के बीच संबंध ==

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

Revision as of 23:47, 9 February 2023

Contents

परिचय

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

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

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

अन्य कमी

चावल का प्रमेय और अंकगणितीय पदानुक्रम

उल्टा गणित

नंबरिंग

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

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

ऑटोमोर्फिज्म समस्याएं

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

आवृत्ति गणना

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

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

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

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

नाम

पेशेवर संगठन

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 23:47, 9 February 2023

परिचय

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

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

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

अन्य कमी

चावल का प्रमेय और अंकगणितीय पदानुक्रम

उल्टा गणित

नंबरिंग

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

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

ऑटोमोर्फिज्म समस्याएं

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

आवृत्ति गणना

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

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

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

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

नाम

पेशेवर संगठन

यह भी देखें

टिप्पणियाँ

संदर्भ

अग्रिम पठन

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories