अनिर्णीत समस्या
कम्प्यूटेबिलिटी सिद्धांत और कम्प्यूटेशनल समष्टिता सिद्धांत में, अनिर्णीत समस्या निर्णय समस्या है जिसके लिए एल्गोरिथ्म का निर्माण करना असंभव सिद्ध होता है जो सदैव सही हां या ना में उत्तर देता है।[1] हाल्टिंग समस्या उदाहरण है: यह सिद्ध किया जा सकता है कि ऐसा कोई एल्गोरिद्म नहीं है जो सही विधि से यह निर्धारित करता है कि इच्छानुसार प्रोग्राम चलते समय रुकते हैं ।[2]
पृष्ठभूमि
एक निर्णय समस्या इनपुट के अनंत समुच्चय पर कोई इच्छानुसार हाँ या नहीं प्रश्न है।[3] इस कारण से, निर्णय समस्या को समान रूप से इनपुट के समुच्चय के रूप में परिभाषित करना पारंपरिक है जिसके लिए समस्या हाँ लौटाती है। ये इनपुट प्राकृतिक संख्याएं हो सकती हैं, किन्तु औपचारिक भाषा के स्ट्रिंग (कंप्यूटर विज्ञान) जैसे किसी अन्य प्रकार के अन्य मान भी हो सकते हैं। कुछ n्कोडिंग का उपयोग करना, जैसे गोडेल नंबरिंग, स्ट्रिंग्स को प्राकृतिक संख्याओं के रूप में n्कोड किया जा सकता है। इस प्रकार, औपचारिक भाषा के संदर्भ में अनौपचारिक रूप से तैयार की गई निर्णय समस्या भी प्राकृतिक संख्याओं के समुच्चय के बराबर होती है। औपचारिक परिभाषा को सरल रखने के लिए, इसे प्राकृतिक संख्याओं के उपसमुच्चय के रूप में व्यक्त किया जाता है।
औपचारिक रूप से, निर्णय समस्या प्राकृतिक संख्याओं का उपसमुच्चय है। संबंधित अनौपचारिक समस्या यह तय करने की है कि दी गई संख्या समुच्चय में है या नहीं है। निर्णय समस्या A को निर्णायक या प्रभावी रूप से हल करने योग्य कहा जाता है यदि A पुनरावर्ती समुच्चय है और अन्यथा अनिर्णीत है। समस्या को आंशिक रूप से निर्णायक, अर्ध-निर्णायक, हल करने योग्य या सिद्ध करने योग्य कहा जाता है यदि A पुनरावर्ती गणना योग्य समुच्चय है।[nb 1]
उदाहरण: कम्प्यूटेबिलिटी सिद्धांत में हॉल्टिंग प्रॉब्लम
संगणनीयता सिद्धांत में, हाल्टिंग समस्या निर्णय समस्या है जिसे निम्नानुसार कहा जा सकता है:
- एक इच्छानुसार कंप्यूटर प्रोग्राम और परिमित इनपुट के विवरण को देखते हुए, तय करें कि क्या प्रोग्राम चलना समाप्त करता है या सदैव के लिए चलता है।
एलन ट्यूरिंग ने 1936 में सिद्ध किया कि ट्यूरिंग मशीन पर चलने वाला सामान्य एल्गोरिदम जो सभी संभावित प्रोग्राम-इनपुट जोड़े के लिए हॉल्टिंग समस्या को हल करता है, आवश्यक रूप से उपस्थित नहीं हो सकता है। इसलिए, ट्यूरिंग मशीनों के लिए हाल्टिंग समस्या अनिर्णीत है।
गोडेल की अपूर्णता प्रमेय के साथ संबंध
गोडेल के अपूर्णता प्रमेयों द्वारा उठाई गई अवधारणाएँ हाल्टिंग समस्या द्वारा उठाई गई अवधारणाओं के समान हैं, और प्रमाण अधिक समान हैं। वास्तव में, प्रथम अपूर्णता प्रमेय का अशक्त रूप हॉल्टिंग समस्या की अनिश्चितता का सरल परिणाम है। यह अशक्त रूप अपूर्णता प्रमेय के मानक कथन से भिन्न है, जिसमें यह प्रमाण किया गया है कि पूर्ण और सुदृढ़ता दोनों वाली प्राकृतिक संख्याओं का स्वयंसिद्ध होना असंभव है। ध्वनि भाग अशक्त है: इसका कारण है कि हमें प्राकृतिक संख्याओं के बारे में केवल सही कथनों को सिद्ध करने के लिए स्वयंसिद्ध प्रणाली की आवश्यकता है। चूँकि सुदृढ़ता का तात्पर्य संगति प्रमाण से है, इस अशक्त रूप को प्रबल रूप के परिणाम के रूप में देखा जा सकता है। यह देखना महत्वपूर्ण है कि गोडेल की पहली अपूर्णता प्रमेय के मानक रूप का कथन किसी कथन के सत्य मान से पूरी तरह से संबंधित नहीं है, किन्तु केवल इस उद्देश्य से संबंधित है कि क्या गणितीय प्रमाण के माध्यम से इसे खोजना संभव है।
हॉल्टिंग समस्या की अनिश्चयता से प्रमेय का अशक्त रूप इस प्रकार सिद्ध किया जा सकता है।[4] मान लें कि हमारे पास प्राकृतिक संख्याओं के बारे में सभी सत्य प्रथम-क्रम तर्क कथनों का ध्वनि (और इसलिए सुसंगत) और पूर्ण स्वयंसिद्ध है। फिर हम एल्गोरिदम बना सकते हैं जो इन सभी कथनों की गणना करता है। इसका कारण यह है कि एल्गोरिथ्म n (n) है, जो प्राकृतिक संख्या n दिया गया है, प्राकृतिक संख्याओं के बारे में वास्तविक प्रथम-क्रम तर्क कथन की गणना करता है, और यह कि सभी सच्चे कथनों के लिए, कम से कम n ऐसा है कि n (n) उस कथन को उत्पन्न करता है। अब मान लीजिए कि हम यह तय करना चाहते हैं कि क्या प्रतिनिधित्व वाला एल्गोरिथ्म इनपुट 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 में स्थिति दिखाया गया था।
गोडेल और पॉल कोहेन (गणितज्ञ) के संयुक्त कार्य ने अनिर्णीत कथनों के दो ठोस उदाहरण दिए हैं (शब्द के पहले अर्थ में): सातत्य परिकल्पना को जेडएफसी में न तो सिद्ध किया जा सकता है और न ही उसका खंडन किया जा सकता है (समुच्चय सिद्धांत का मानक स्वयंसिद्धीकरण), और ज़र्मेलो-फ्रेंकेल समुच्चय सिद्धान्त (जो पसंद के स्वयंसिद्ध को छोड़कर सभी जेडएफसी स्वयंसिद्ध हैं) में पसंद के स्वयंसिद्ध को न तो सिद्ध किया जा सकता है और न ही खंडन किया जा सकता है। इन परिणामों के लिए अपूर्णता प्रमेय की आवश्यकता नहीं है। गोडेल ने 1940 में सिद्ध किया कि इनमें से किसी भी कथन को ZF या जेडएफसी समुच्चय सिद्धांत में अप्रमाणित नहीं किया जा सकता है। 1960 के दशक में, कोहेन ने सिद्ध किया कि न तो ZF से सिद्ध किया जा सकता है, और जेडएफसी से सातत्य परिकल्पना को सिद्ध नहीं किया जा सकता है।
1970 में, रूसी गणितज्ञ यूरी मटियासेविच ने दिखाया कि हिल्बर्ट की दसवीं समस्या या हिल्बर्ट की दसवीं समस्या, जिसे 1900 में गणितज्ञों की अगली सदी के लिए चुनौती के रूप में प्रस्तुत किया गया था, जिसको हल नहीं किया जा सकता है। हिल्बर्ट की चुनौती ने एल्गोरिथ्म की मांग की जो डायोफैंटाइन समीकरण के सभी समाधान खोजता है। डायोफैंटाइन समीकरण फ़र्मेट के अंतिम प्रमेय का अधिक सामान्य स्थिति है; हम पूर्णांक गुणांक वाले किसी भी चर में बहुपद की पूर्णांक संख्या की खोज करते हैं। चूँकि हमारे पास केवल समीकरण है किन्तु n चर हैं, समष्टि तल में असीम रूप से कई समाधान उपस्थित हैं (और खोजने में सरल हैं); चूँकि, समस्या असंभव हो जाती है यदि समाधान केवल पूर्णांक मानों तक ही सीमित होते है। मटियासेविच ने डायोफैंटाइन समीकरण को पुनरावर्ती रूप से गणना योग्य समुच्चय पर मैप करके और गोडेल की अपूर्णता प्रमेय को प्रयुक्त करके इस समस्या को अघुलनशील दिखाया था।[5]
1936 में, एलन ट्यूरिंग ने सिद्ध किया कि हॉल्टिंग प्रॉब्लम - किसी दिए गए प्रोग्राम पर ट्यूरिंग मशीन के रुकने या न होने का सवाल शब्द के दूसरे अर्थ में अनिर्णीत है। इस परिणाम को बाद में राइस के प्रमेय द्वारा सामान्यीकृत किया गया था।
1973 में, सहारों शेलाह ने दिखाया कि समूह सिद्धांत में व्हाइटहेड समस्या शब्द के पहले अर्थ में, मानक समुच्चय सिद्धांत में अनिर्णीत है।[6] 1977 में, पेरिस और हैरिंगटन ने सिद्ध कर दिया कि पेरिस-हैरिंगटन प्रमेय या पेरिस-हैरिंगटन सिद्धांत, रैमसे प्रमेय का संस्करण है, जो पीनो अभिगृहीतों द्वारा दिए गए अंकगणित के स्वयंसिद्ध में अनिर्णायक है, किन्तु बड़े सिस्टम में सच सिद्ध हो सकता है।
क्रस्कल के वृक्ष प्रमेय, जिसका कंप्यूटर विज्ञान में अनुप्रयोग है, पियानों के स्वयंसिद्धों से भी अनिर्णीत है किन्तु समुच्चय सिद्धांत में सिद्ध है। वास्तव में कृस्कल का ट्री प्रमेय (या इसका परिमित रूप) गणित के दर्शन के आधार पर स्वीकार्य सिद्धांतों को संहिताबद्ध करने वाली अधिक सशक्त प्रणाली में अपरिहार्य है जिसे विधेयवाद कहा जाता है।
गुडस्टीन की प्रमेय प्राकृतिक संख्याओं के रैमसे सिद्धांत के बारे में कथन है जो कि किर्बी और पेरिस ने दिखाया है जो पियानो अंकगणित में अनिर्णनीय है।
ग्रेगरी चैतिन ने एल्गोरिथम सूचना सिद्धांत में अनिर्णायक कथन दिए और उस समुच्चयिंग में और अपूर्णता प्रमेय सिद्ध किया था। चैतिन के प्रमेय में कहा गया है कि किसी भी सिद्धांत के लिए जो पर्याप्त अंकगणित का प्रतिनिधित्व कर सकता है, ऊपरी सीमा सी है जैसे कि उस सिद्धांत में कोलमोगोरोव समष्टिता को सी से अधिक होने के लिए कोई विशिष्ट संख्या सिद्ध नहीं की जा सकती है। जबकि गोडेल का प्रमेय कोलाट्ज़ समस्या से संबंधित है, चैतिन का परिणाम बेरी के विरोधाभास से संबंधित है।
2007 में, शोधकर्ता कर्ट्ज़ और साइमन, जॉन हॉर्टन कॉनवे द्वारा पहले के काम पर निर्माण कर रहे थे। जे.एच. 1970 के दशक में कॉनवे ने सिद्ध किया कि कोलाट्ज़ समस्या का प्राकृतिक सामान्यीकरण अनिर्णीत है।[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.
