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

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Study of computable functions and Turing degrees}}
{{short description|Study of computable functions and Turing degrees}}
{{for|the concept of computability|Computability}}
{{for|संगणनीयता का सिद्धांत के लिए |संगणनीयता}}
{{use dmy dates|date=August 2022|cs1-dates=y}}
संगणनीयता सिद्धांत, जिसे पुनरावर्तन सिद्धांत के रूप में भी जाना जाता है, [[गणितीय तर्क]], [[कंप्यूटर विज्ञान]] और संगणना के सिद्धांत की एक शाखा है, जिसकी उत्पत्ति 1930 के दशक में संगणनीय कार्यों और ट्यूरिंग डिग्री के अध्ययन के साथ हुई थी। सामान्यीकृत संगणनीयता और [[निश्चित सेट]] के अध्ययन को शामिल करने के लिए क्षेत्र का विस्तार हुआ है। इन क्षेत्रों में, संगणनीयता सिद्धांत प्रमाण सिद्धांत और [[प्रभावी वर्णनात्मक सेट सिद्धांत]] के साथ ओवरलैप होता है।


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


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


== परिचय ==
== परिचय ==
Line 34: Line 34:
| colspan="8" {{COther}} The [[Busy Beaver#The busy beaver function Σ|Busy Beaver]] function Σ(''n'') grows faster than any computable function.<br>Hence, it is not computable;<ref name="Rado_1962"/> only a few values are known.
| colspan="8" {{COther}} The [[Busy Beaver#The busy beaver function Σ|Busy Beaver]] function Σ(''n'') grows faster than any computable function.<br>Hence, it is not computable;<ref name="Rado_1962"/> only a few values are known.
|}
|}
कम्प्यूटेबिलिटी सिद्धांत की उत्पत्ति 1930 ई० के दशक में कर्ट गोडेल, [[अलोंजो चर्च]], रोजसा पेटर, [[एलन ट्यूरिंग]], [[स्टीफन क्लेन]] और [[एमिल पोस्ट]] के काम से हुई थी।<ref name="Soare_2011"/><ref group="nb" name="NB_Davis_1965"/>
कम्प्यूटेबिलिटी सिद्धांत की उत्पत्ति 1930 के दशक में कर्ट गोडेल, [[अलोंजो चर्च]], रोजसा पेटर, [[एलन ट्यूरिंग]], [[स्टीफन क्लेन]] और [[एमिल पोस्ट]] के काम से हुई थी।<ref name="Soare_2011"/><ref group="nb" name="NB_Davis_1965"/>


शोधकर्ताओं ने मूलभूत परिणामों को प्रभावी गणना के अनौपचारिक विचार के सही औपचारिकता के रूप में स्थापित गणना योग्य कार्य के रूप में प्राप्त किया। 1952 में, इन परिणामों ने क्लेन को चर्च की थीसिस के दो नामों को गढ़ने के लिए प्रेरित किया<ref name="Kleene_1952"/>{{rp|page=300}} और ट्यूरिंग का शोध प्रबंध <ref name="Kleene_1952"/>{{rp|page=376}} एक एकल परिकल्पना, चर्च-ट्यूरिंग शोध प्रबंध के रूप में माना जाता है, जिसमें कहा गया है कि कोई भी फलन जो [[कलन विधि]] द्वारा गणना योग्य है, एक गणना योग्य फलन है। यद्यपि प्रारम्भ में संदेह था, 1946 ई० तक गोडेल ने इस शोध प्रबंध के पक्ष में तर्क दिया:<!-- <ref name="Gödel_1946"/> --><ref name="Davis_1965"/>{{rp|page=84}}
शोधकर्ताओं ने मूलभूत परिणामों को प्रभावी गणना के अनौपचारिक विचार के सही औपचारिकता के रूप में स्थापित गणना योग्य कार्य के रूप में प्राप्त किया। 1952 में, इन परिणामों ने क्लेन को चर्च की थीसिस के दो नामों को गढ़ने के लिए प्रेरित किया<ref name="Kleene_1952"/>{{rp|page=300}} और ट्यूरिंग की थीसिस।<ref name="Kleene_1952"/>{{rp|page=376}} आजकल इन्हें अक्सर एक एकल परिकल्पना, चर्च-ट्यूरिंग थीसिस के रूप में माना जाता है, जिसमें कहा गया है कि कोई भी फ़ंक्शन जो [[कलन विधि]] द्वारा गणना योग्य है, एक गणना योग्य फ़ंक्शन है। हालाँकि शुरुआत में संदेह था, 1946 तक गोडेल ने इस थीसिस के पक्ष में तर्क दिया:<!-- <ref name="Gödel_1946"/> --><ref name="Davis_1965"/>{{rp|page=84}}


{{blockquote|"[[Alfred Tarski|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."<!-- <ref name="Gödel_1946"/> --><ref name="Davis_1965"/>{{rp|page=84}}<ref name="Feferman_1990"/>}}
{{blockquote|"[[Alfred Tarski|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."<!-- <ref name="Gödel_1946"/> --><ref name="Davis_1965"/>{{rp|page=84}}<ref name="Feferman_1990"/>}}

Revision as of 00:26, 8 February 2023

For संगणनीयता का सिद्धांत के लिए, see संगणनीयता.

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

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

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

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

परिचय

n 2 3 4 5 6 7 ...
Σ(n) 4 6 13 4098 ? > 3.5×1018267 > 1010101018705353 ?
Does not appear The Busy Beaver function Σ(n) grows faster than any computable function.
Hence, it is not computable;[1] only a few values are known.

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

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

"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."[4]: 84 [5]

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

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

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

ट्यूरिंग कम्प्यूटेबिलिटी

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

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

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

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

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

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

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

Main articles: Turing reduction and Turing degree

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

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

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

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

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

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

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

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

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

अन्य कमी

Main article: Reduction (recursion theory)

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

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

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

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

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

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

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

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

उल्टा गणित

Main article: Reverse mathematics

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

नंबरिंग

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

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

Further information: Turing degree § Post's problem and the priority method

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

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

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

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

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

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

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


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

Main article: Kolmogorov complexity

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

आवृत्ति गणना

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

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

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

ट्यूरिंग कम्प्यूटेबिलिटी का सामान्यीकरण

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

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

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

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

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

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

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

नाम

संगणनीयता और इसके सामान्यीकरण से संबंधित गणितीय तर्क के क्षेत्र को इसके शुरुआती दिनों से ही पुनरावर्तन सिद्धांत कहा जाता है। रॉबर्ट आई। सोरे, क्षेत्र के एक प्रमुख शोधकर्ता ने प्रस्तावित किया है[12]इसके बजाय क्षेत्र को कम्प्यूटेबिलिटी सिद्धांत कहा जाना चाहिए। उनका तर्क है कि कंप्यूटेबल शब्द का उपयोग करने वाली ट्यूरिंग की शब्दावली क्लेन द्वारा पेश किए गए पुनरावर्ती शब्द का उपयोग करने वाली शब्दावली की तुलना में अधिक स्वाभाविक और अधिक व्यापक रूप से समझी जाती है। कई समकालीन शोधकर्ताओं ने इस वैकल्पिक शब्दावली का प्रयोग करना शुरू कर दिया है।[nb 3]ये शोधकर्ता आंशिक पुनरावर्ती फ़ंक्शन और पुनरावर्ती गणना योग्य (re.e.) सेट के बजाय आंशिक गणना योग्य फ़ंक्शन और गणना योग्य गणना योग्य (सी.ई.) सेट जैसी शब्दावली का भी उपयोग करते हैं। हालांकि, सभी शोधकर्ताओं को आश्वस्त नहीं किया गया है, जैसा कि फोर्टनाउ द्वारा समझाया गया है[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. ↑ 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).)
  6. ↑ Church, Alonzo (1936a). "An unsolvable problem of elementary number theory". American Journal of Mathematics. 58 (2): 345–363. doi:10.2307/2371045. JSTOR 2371045. Reprinted in Davis 1965.
  7. ↑ Church, Alonzo (1936b). "A note on the Entscheidungsproblem". Journal of Symbolic Logic. 1 (1): 40–41. doi:10.2307/2269326. JSTOR 2269326. S2CID 42323521. Reprinted in Davis 1965.
  8. ↑ 8.0 8.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.
  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. ↑ 14.0 14.1 14.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.
  15. ↑ Shore, Richard Arnold; Slaman, Theodore Allen (1999). "Defining the Turing Jump". Mathematical Research Letters. 6 (6): 711–722. doi:10.4310/mrl.1999.v6.n6.a10. ISSN 1073-2780. MR 1739227.
  16. ↑ 16.0 16.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.
  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=96133’