अनिर्णीत समस्या
 | This article needs additional citations for verification. (July 2019) (Learn how and when to remove this template message) |
कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल जटिलता सिद्धांत में, एक अनिर्णीत समस्या एक निर्णय समस्या है जिसके लिए एक कलन विधि का निर्माण करना असंभव साबित होता है जो हमेशा सही हां या ना में उत्तर देता है।[1] रुकने की समस्या एक उदाहरण है: यह सिद्ध किया जा सकता है कि ऐसा कोई एल्गोरिद्म नहीं है जो सही ढंग से यह निर्धारित करता है कि मनमाने प्रोग्राम चलते समय रुकते हैं या नहीं।[2]
पृष्ठभूमि
एक निर्णय समस्या इनपुट के अनंत सेट पर कोई मनमाना हाँ या नहीं प्रश्न है।[3] इस वजह से, निर्णय समस्या को समान रूप से इनपुट के सेट के रूप में परिभाषित करना पारंपरिक है जिसके लिए समस्या हाँ लौटाती है। ये इनपुट प्राकृतिक संख्याएं हो सकती हैं, लेकिन औपचारिक भाषा के स्ट्रिंग (कंप्यूटर विज्ञान) जैसे किसी अन्य प्रकार के अन्य मान भी हो सकते हैं। कुछ एन्कोडिंग का उपयोग करना, जैसे गोडेल नंबरिंग, स्ट्रिंग्स को प्राकृतिक संख्याओं के रूप में एन्कोड किया जा सकता है। इस प्रकार, एक औपचारिक भाषा के संदर्भ में अनौपचारिक रूप से तैयार की गई एक निर्णय समस्या भी प्राकृतिक संख्याओं के एक सेट के बराबर होती है। औपचारिक परिभाषा को सरल रखने के लिए, इसे प्राकृतिक संख्याओं के सबसेट के रूप में व्यक्त किया जाता है।
औपचारिक रूप से, एक निर्णय समस्या प्राकृतिक संख्याओं का एक उपसमुच्चय है। संबंधित अनौपचारिक समस्या यह तय करने की है कि दी गई संख्या सेट में है या नहीं। एक निर्णय समस्या A को निर्णायक या प्रभावी रूप से हल करने योग्य कहा जाता है यदि A एक पुनरावर्ती सेट है और अन्यथा अनिर्णीत है। एक समस्या को आंशिक रूप से निर्णायक, अर्ध-निर्णायक, हल करने योग्य या सिद्ध करने योग्य कहा जाता है यदि A एक पुनरावर्ती गणना योग्य सेट है।[nb 1]
उदाहरण: कम्प्यूटेबिलिटी थ्योरी में हॉल्टिंग प्रॉब्लम
संगणनीयता सिद्धांत में, रुकने की समस्या एक निर्णय समस्या है जिसे निम्नानुसार कहा जा सकता है:
- एक मनमाना कंप्यूटर प्रोग्राम और एक परिमित इनपुट के विवरण को देखते हुए, तय करें कि क्या प्रोग्राम चलना समाप्त करता है या हमेशा के लिए चलेगा।
एलन ट्यूरिंग ने 1936 में साबित किया कि ट्यूरिंग मशीन पर चलने वाला एक सामान्य एल्गोरिदम जो सभी संभावित प्रोग्राम-इनपुट जोड़े के लिए हॉल्टिंग समस्या को हल करता है, आवश्यक रूप से मौजूद नहीं हो सकता है। इसलिए, ट्यूरिंग मशीनों के लिए रुकने की समस्या अनिर्णीत है।
गोडेल की अपूर्णता प्रमेय के साथ संबंध
| This section needs additional citations for verification. (August 2019) (Learn how and when to remove this template message) |
गोडेल के अपूर्णता प्रमेयों द्वारा उठाई गई अवधारणाएँ हाल्टिंग समस्या द्वारा उठाई गई अवधारणाओं के समान हैं, और प्रमाण काफी समान हैं। वास्तव में, प्रथम अपूर्णता प्रमेय का एक कमजोर रूप हॉल्टिंग समस्या की अनिश्चितता का एक आसान परिणाम है। यह कमजोर रूप अपूर्णता प्रमेय के मानक कथन से भिन्न है, जिसमें यह दावा किया गया है कि पूर्ण और सुदृढ़ता दोनों वाली प्राकृतिक संख्याओं का स्वयंसिद्ध होना असंभव है। ध्वनि भाग कमजोर है: इसका मतलब है कि हमें प्राकृतिक संख्याओं के बारे में केवल सही बयानों को साबित करने के लिए स्वयंसिद्ध प्रणाली की आवश्यकता है। चूँकि सुदृढ़ता का तात्पर्य संगति प्रमाण से है, इस कमजोर रूप को प्रबल रूप के परिणाम के रूप में देखा जा सकता है। यह देखना महत्वपूर्ण है कि गोडेल की पहली अपूर्णता प्रमेय के मानक रूप का कथन किसी कथन के सत्य मान से पूरी तरह से संबंधित नहीं है, लेकिन केवल इस मुद्दे से संबंधित है कि क्या गणितीय प्रमाण के माध्यम से इसे खोजना संभव है।
हॉल्टिंग समस्या की अनिश्चयता से प्रमेय का कमजोर रूप इस प्रकार सिद्ध किया जा सकता है।[4] मान लें कि हमारे पास प्राकृतिक संख्याओं के बारे में सभी सत्य प्रथम-क्रम तर्क कथनों का एक ध्वनि (और इसलिए सुसंगत) और पूर्ण स्वयंसिद्ध है। फिर हम एक एल्गोरिदम बना सकते हैं जो इन सभी बयानों की गणना करता है। इसका मतलब यह है कि एक एल्गोरिथ्म एन (एन) है, जो एक प्राकृतिक संख्या एन दिया गया है, प्राकृतिक संख्याओं के बारे में एक वास्तविक प्रथम-क्रम तर्क कथन की गणना करता है, और यह कि सभी सच्चे बयानों के लिए, कम से कम एक एन ऐसा है कि एन (एन) उस कथन को उत्पन्न करता है। अब मान लीजिए कि हम यह तय करना चाहते हैं कि क्या प्रतिनिधित्व वाला एल्गोरिथ्म इनपुट i पर रुकता है। हम जानते हैं कि इस कथन को प्रथम कोटि के तार्किक कथन, मान लीजिए H(a, i) द्वारा व्यक्त किया जा सकता है। चूँकि अभिगृहीतीकरण पूरा हो गया है, यह इस प्रकार है कि या तो एक n ऐसा है कि N(n) = H(a, i) या एक n' ऐसा है कि N(n') = ¬ H(a, i)। इसलिए यदि हम सभी n पर पुनरावृति करते हैं जब तक कि हम या तो H(a, i) या इसका निषेध नहीं पाते हैं, हम हमेशा रुकेंगे, और इसके अलावा, यह हमें जो उत्तर देगा वह सत्य होगा (ध्वनि द्वारा)। इसका मतलब है कि यह हमें हॉल्टिंग प्रॉब्लम को तय करने के लिए एक एल्गोरिद्म देता है। चूंकि हम जानते हैं कि ऐसा कोई एल्गोरिथम नहीं हो सकता है, यह इस धारणा का अनुसरण करता है कि प्राकृतिक संख्याओं के बारे में सभी सत्य प्रथम-क्रम तर्क कथनों का एक सुसंगत और पूर्ण स्वयंसिद्ध होना गलत होना चाहिए।
अनिर्णीत समस्याओं के उदाहरण
अनिर्णनीय समस्याएं विभिन्न विषयों से संबंधित हो सकती हैं, जैसे तर्कशास्त्र, अमूर्त मशीन या टोपोलॉजी। चूंकि अनगिनत सेट कई अनिर्णनीय समस्याएं हैं,[nb 2] कोई भी सूची, यहां तक कि अनंत संख्या में से एक भी, अनिवार्य रूप से अपूर्ण है।
अनिर्णायक कथनों के उदाहरण
समकालीन उपयोग में अनिर्णीत शब्द की दो अलग-अलग भावनाएँ हैं। इनमें से पहला अर्थ गोडेल के प्रमेय के संबंध में उपयोग किया जाता है, जो कि एक कथन का एक निर्दिष्ट निगमनात्मक प्रणाली में न तो साबित किया जा सकता है और न ही खंडन किया जा सकता है। दूसरे अर्थ का उपयोग कम्प्यूटेबिलिटी सिद्धांत के संबंध में किया जाता है और यह बयानों पर नहीं बल्कि समस्याओं को हल करने के लिए लागू होता है, जो प्रश्नों के अनंत सेट होते हैं जिनमें से प्रत्येक को हां या ना में उत्तर की आवश्यकता होती है। इस तरह की समस्या को अनिर्णीत कहा जाता है यदि कोई संगणनीय कार्य नहीं है जो समस्या सेट में प्रत्येक प्रश्न का सही उत्तर देता है। इन दोनों के बीच संबंध यह है कि यदि कोई निर्णय समस्या अनिर्णीत है (पुनरावृत्ति सैद्धांतिक अर्थ में) तो कोई सुसंगत, प्रभावी औपचारिक प्रणाली नहीं है जो समस्या में प्रत्येक प्रश्न A के लिए सिद्ध करती है या तो A का उत्तर हाँ है या A का उत्तर है कोई नहीं है ।
अनिर्णीत शब्द के दो अर्थों के कारण, स्वतंत्रता (गणितीय तर्क) शब्द का प्रयोग कभी-कभी न तो सिद्ध करने योग्य और न ही खंडन योग्य अर्थों के लिए अनिर्णीत के बजाय किया जाता है। हालाँकि, स्वतंत्र का उपयोग भी अस्पष्ट है। इसका मतलब सिर्फ साबित करने योग्य नहीं हो सकता है, खुला छोड़ना कि क्या एक स्वतंत्र बयान का खंडन किया जा सकता है।
किसी विशेष निगमनात्मक प्रणाली में किसी कथन की अनिश्चयता अपने आप में इस प्रश्न का समाधान नहीं करती है कि क्या कथन का सत्य मूल्य अच्छी तरह से परिभाषित है, या यह अन्य तरीकों से निर्धारित किया जा सकता है या नहीं। अनिश्चितता का अर्थ केवल यह है कि विचार की जा रही विशेष निगमनात्मक प्रणाली कथन की सत्यता या असत्यता को प्रमाणित नहीं करती है। क्या ऐसे तथाकथित बिल्कुल अनिर्णायक कथन मौजूद हैं, जिनका सत्य मूल्य कभी ज्ञात नहीं हो सकता है या गलत निर्दिष्ट है, यह गणित के विभिन्न दर्शन के बीच एक विवादास्पद बिंदु है।
शब्द के दूसरे अर्थ में, संदेहास्पद होने वाली पहली समस्याओं में से एक, समूहों के लिए शब्द समस्या थी, जिसे पहली बार 1911 में मैक्स डेहन द्वारा प्रस्तुत किया गया था, जो पूछता है कि क्या कोई अंतिम रूप से प्रस्तुत समूह (गणित) है जिसके लिए कोई एल्गोरिदम मौजूद नहीं है। यह निर्धारित करने के लिए कि क्या दो शब्द समकक्ष हैं। यह 1952 में मामला दिखाया गया था।
गोडेल और पॉल कोहेन (गणितज्ञ) के संयुक्त कार्य ने अनिर्णीत कथनों के दो ठोस उदाहरण दिए हैं (शब्द के पहले अर्थ में): सातत्य परिकल्पना को ZFC में न तो सिद्ध किया जा सकता है और न ही उसका खंडन किया जा सकता है (सेट सिद्धांत का मानक स्वयंसिद्धीकरण), और ज़र्मेलो-फ्रेंकेल समुच्चय सिद्धान्त (जो पसंद के स्वयंसिद्ध को छोड़कर सभी ZFC स्वयंसिद्ध हैं) में पसंद के स्वयंसिद्ध को न तो सिद्ध किया जा सकता है और न ही खंडन किया जा सकता है। इन परिणामों के लिए अपूर्णता प्रमेय की आवश्यकता नहीं है। गोडेल ने 1940 में साबित किया कि इनमें से किसी भी कथन को ZF या ZFC सेट थ्योरी में अप्रमाणित नहीं किया जा सकता है। 1960 के दशक में, कोहेन ने साबित किया कि न तो ZF से सिद्ध किया जा सकता है, और ZFC से सातत्य परिकल्पना को सिद्ध नहीं किया जा सकता है।
1970 में, रूसी गणितज्ञ यूरी मटियासेविच ने दिखाया कि हिल्बर्ट की दसवीं समस्या | हिल्बर्ट की दसवीं समस्या, जिसे 1900 में गणितज्ञों की अगली सदी के लिए एक चुनौती के रूप में प्रस्तुत किया गया था, को हल नहीं किया जा सकता है। हिल्बर्ट की चुनौती ने एक एल्गोरिथ्म की मांग की जो एक डायोफैंटाइन समीकरण के सभी समाधान खोजता है। डायोफैंटाइन समीकरण फ़र्मेट के अंतिम प्रमेय का एक अधिक सामान्य मामला है; हम पूर्णांक गुणांक वाले किसी भी चर में बहुपद की पूर्णांक संख्या की तलाश करते हैं। चूँकि हमारे पास केवल एक समीकरण है लेकिन n चर हैं, जटिल तल में असीम रूप से कई समाधान मौजूद हैं (और खोजने में आसान हैं); हालाँकि, समस्या असंभव हो जाती है यदि समाधान केवल पूर्णांक मानों तक ही सीमित हो। मटियासेविच ने डायोफैंटाइन समीकरण को पुनरावर्ती रूप से गणना योग्य सेट पर मैप करके और गोडेल की अपूर्णता प्रमेय को लागू करके इस समस्या को अघुलनशील दिखाया।[5] 1936 में, एलन ट्यूरिंग ने साबित किया कि हॉल्टिंग प्रॉब्लम - किसी दिए गए प्रोग्राम पर ट्यूरिंग मशीन के रुकने या न होने का सवाल - शब्द के दूसरे अर्थ में अनिर्णीत है। इस परिणाम को बाद में राइस के प्रमेय द्वारा सामान्यीकृत किया गया।
1973 में, सहारों शेलाह ने दिखाया कि समूह सिद्धांत में व्हाइटहेड समस्या शब्द के पहले अर्थ में, मानक सेट सिद्धांत में अनिर्णीत है।[6] 1977 में, पेरिस और हैरिंगटन ने साबित कर दिया कि पेरिस-हैरिंगटन प्रमेय | पेरिस-हैरिंगटन सिद्धांत, रैमसे प्रमेय का एक संस्करण है, जो पीनो अभिगृहीतों द्वारा दिए गए अंकगणित के स्वयंसिद्ध में अनिर्णायक है, लेकिन बड़े सिस्टम में सच साबित हो सकता है दूसरे क्रम का अंकगणित।
क्रस्कल के वृक्ष प्रमेय, जिसका कंप्यूटर विज्ञान में अनुप्रयोग है, पियानों के स्वयंसिद्धों से भी अनिर्णीत है लेकिन समुच्चय सिद्धांत में सिद्ध है। वास्तव में कृस्कल का पेड़ प्रमेय (या इसका परिमित रूप) गणित के एक दर्शन के आधार पर स्वीकार्य सिद्धांतों को संहिताबद्ध करने वाली एक अधिक मजबूत प्रणाली में अपरिहार्य है जिसे विधेयवाद कहा जाता है।
गुडस्टीन की प्रमेय प्राकृतिक संख्याओं के रैमसे सिद्धांत के बारे में एक बयान है जो कि किर्बी और पेरिस ने दिखाया है जो पियानो अंकगणित में अनिर्णनीय है।
ग्रेगरी चैतिन ने एल्गोरिथम सूचना सिद्धांत में अनिर्णायक बयान दिए और उस सेटिंग में एक और अपूर्णता प्रमेय साबित किया। चैतिन के प्रमेय में कहा गया है कि किसी भी सिद्धांत के लिए जो पर्याप्त अंकगणित का प्रतिनिधित्व कर सकता है, एक ऊपरी सीमा सी है जैसे कि उस सिद्धांत में कोलमोगोरोव जटिलता को सी से अधिक होने के लिए कोई विशिष्ट संख्या सिद्ध नहीं की जा सकती। जबकि गोडेल का प्रमेय झूठा विरोधाभास से संबंधित है, चैतिन का परिणाम बेरी के विरोधाभास से संबंधित है।
2007 में, शोधकर्ता कर्ट्ज़ और साइमन, जॉन हॉर्टन कॉनवे द्वारा पहले के काम पर निर्माण कर रहे थे। जे.एच. 1970 के दशक में कॉनवे ने साबित किया कि Collatz समस्या का एक प्राकृतिक सामान्यीकरण अनिर्णीत है।[7] 2019 में, बेन-डेविड और उनके सहयोगियों ने एक लर्निंग मॉडल (ईएमएक्स नाम दिया) का एक उदाहरण बनाया, और कार्यों का एक परिवार दिखाया, जिनकी ईएमएक्स में सीखने की क्षमता मानक सेट सिद्धांत में अनिर्णीत है।[8][9]
यह भी देखें
टिप्पणियाँ
- ↑ This means that there exists an algorithm that halts eventually when the answer is yes but may run forever if the answer is no.
- ↑ There are uncountably many subsets of , only countably many of which can be decided by algorithms. However, also only countably many decision problems can be stated in any language.
संदर्भ
- ↑ "Decidable and Undecidable problems in Theory of Computation". GeeksforGeeks (in English). 2018-01-08. Retrieved 2022-06-12.
- ↑ "Formal Computational Models and Computability". www.cs.rochester.edu. Retrieved 2022-06-12.
- ↑ "decision problem". Oxford Reference (in English). Retrieved 2022-06-12.
- ↑ Aaronson, Scott (21 July 2011). "Rosser's Theorem via Turing machines". Shtetl-Optimized. Retrieved 2 November 2022.
- ↑ Matiyasevich, Yuri (1970). Диофантовость перечислимых множеств [Enumerable sets are Diophantine]. Doklady Akademii Nauk SSSR (in русский). 191: 279–282.
- ↑ Shelah, Saharon (1974). "Infinite Abelian groups, Whitehead problem and some constructions". Israel Journal of Mathematics. 18 (3): 243–256. doi:10.1007/BF02757281. MR 0357114.
- ↑ Kurtz, Stuart A.; Simon, Janos, "The Undecidability of the Generalized Collatz Problem", in Proceedings of the 4th International Conference on Theory and Applications of Models of Computation, TAMC 2007, held in Shanghai, China in May 2007. ISBN 3-540-72503-2. doi:10.1007/978-3-540-72504-6_49
- ↑ Ben-David, Shai; Hrubeš, Pavel; Moran, Shay; Shpilka, Amir; Yehudayoff, Amir (2019-01-07). "Learnability can be undecidable". Nature Machine Intelligence (in English). 1 (1): 44–48. doi:10.1038/s42256-018-0002-3. ISSN 2522-5839.
- ↑ Reyzin, Lev (2019). "Unprovability comes to machine learning". Nature (in English). 565 (7738): 166–167. doi:10.1038/d41586-019-00012-4. ISSN 0028-0836.
