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

From Vigyanwiki

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

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

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

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

परिचय

n 2 3 4 5 6 7 ...
Σ(n) 4 6 13 4098 ? > 3.5×1018267 > 1010101018705353 ?
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 पर रुकने वाली ट्यूरिंग यंत्रों के विवरण का समुच्चय है, एक गैर-गणनीय समुच्चय का एक प्रसिद्ध उदाहरण है। कई गैर-गणनीय समुच्चयों का अस्तित्व इस तथ्य से अनुसरण करता है कि केवल गणनीय समुच्चय ट्यूरिंग यंत्र हैं, और इस प्रकार केवल गणना करने योग्य कई समुच्चय हैं, लेकिन कैंटर के प्रमेय के अनुसार, प्राकृतिक संख्याओं के सर्वाधिक समुच्चय हैं।

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

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

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

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

Main articles: ट्यूरिंग परिवर्तन and ट्यूरिंग श्रेणी

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

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

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

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

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

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

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

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

ट्यूरिंग श्रेणियों पर हाल के शोध ने ट्यूरिंग श्रेणियों के समुच्चय की समग्र संरचना पर ध्यान केंद्रित किया है और ट्यूरिंग श्रेणियों के समुच्चय पर संगंणकताल रूप से गणना करने योग्य समुच्चय हैं। शोर और स्लैमन का एक गहरा प्रमेय[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 स्तर Σ पर है2, सभी पुनरावर्ती समुच्चयों के वर्ग का सूचकांक समुच्चय REC स्तर Σ पर है3, सभी कॉफिनिट समुच्चयों का अच्छे समुच्चय COFIN भी Σ के स्तर पर है3 और सभी ट्यूरिंग-पूर्ण समुच्चयों के वर्ग का सूचकांक समुच्चय COMP4. इन पदानुक्रम स्तरों को आगमनात्मक रूप से परिभाषित किया गया है, Σn+1 केवल सभी समुच्चय सम्मिलित हैं जो Σ के सापेक्ष गणनीय हैंn; एस1 संगणनीय रूप से गणना करने योग्य समुच्चय सम्मिलित हैं। यहां दिए गए अच्छे समुच्चय अपने स्तरों के लिए भी पूर्ण हैं, यानी इन स्तरों के सभी समुच्चय दिए गए अच्छे समुच्चयों में एका-एक घटाए जा सकते हैं।

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

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

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

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

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

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

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

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

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

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

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

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

नाम

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

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

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

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

यह भी देखें

टिप्पणियाँ

  1. ↑ Many of these foundational papers are collected in The Undecidable (1965) edited by Martin Davis.
  2. ↑ The homepage of André Nies has a list of open problems in Kolmogorov complexity.
  3. ↑ 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.


संदर्भ

  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.
  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.
  3. ↑ 3.0 3.1 Kleene, Stephen Cole (1952). Introduction to Metamathematics. North-Holland. pp. 300, 376. ISBN 0-7204-2103-9.
  4. ↑ 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.
  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.
  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.
  7. ↑ 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.
  8. ↑ 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).)
  9. ↑ 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.
  10. ↑ Cutland, Nigel J. (1980). Computability, An introduction to recursive function theory. Cambridge University Press. ISBN 0-521-29465-7.
  11. ↑ 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. ↑ 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.
  13. ↑ 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.
  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.
  15. ↑ 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. ↑ 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. ↑ 17.0 17.1 Simpson, Steven George (1999). Subsystems of Second Order Arithmetic. Springer-Verlag. ISBN 3-540-64882-8.
  18. ↑ 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.
  19. ↑ 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.
  20. ↑ 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.
  21. ↑ Conference on Logic, Computability and Randomness, 2007-01-13 [2007-01-11], archived from the original on 2007-12-26
  22. ↑ Sacks, Gerald Enoch (1990). Higher Recursion Theory. Springer-Verlag. ISBN 3-540-19305-7.
  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.
  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.
  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.
  26. ↑ Fortnow, Lance Jeremy (2004-02-15). "Is it Recursive, Computable or Decidable?". Archived from the original on 2022-08-07. Retrieved 2018-03-22.
  27. ↑ 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.
  28. ↑ Friedman, Harvey (1998-08-28). "Renaming recursion theory". FOM email list. Archived from the original on 2022-03-01. Retrieved 2006-01-09.
  29. ↑ 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
Advanced texts
Survey papers and collections
Research papers and collections


बाहरी संबंध

Wikimedia Commons has media related to [[commons:Category:संगणनीयता सिद्धांत|संगणनीयता सिद्धांत]].
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=संगणनीयता_सिद्धांत&oldid=258135’