अनिर्णनीय प्रॉब्लम

इस लेख में सुधार किया जा रहा है। इसकी भाषा को सरल बना दिया जाएगा, और सन्दर्भ भी जोड़ दिए जाएंगे। थोड़ा समय दीजिए।

सैद्धांतिक कंप्यूटर विज्ञान में अनिर्णनीय प्रॉब्लम (अंग्रेज़ी: undecidable problem) एक ऐसी निर्णय प्रॉब्लम को कहते हैं जिसका हल करने के लिए अल्गोरिद्म नहीं बन सकता है। सरल शब्दों में अनिर्णनीय प्रॉब्लम "हाँ या ना" उत्तर वाले प्रश्नों के ऐसे समूह को कहते हैं जिसके लिए ऐसा अल्गोरिद्म बनाना असंभव है जो समूह के हर प्रश्न के लिए सही उत्तर देता हो।

उदाहरण

अनिर्णनीय प्रॉब्लम का एक उदाहरण हॉल्टिंग प्रॉब्लम है। हॉल्टिंग प्रॉब्लम निम्नलिखित निर्णय प्रॉब्लम को कहते हैं:

"कंप्यूटर प्रोग्राम P इनपुट i मिलने पर क्या कभी रुकेगा?"

ऊपर दिया गया उदाहरण एक प्रश्न नहीं है, बल्कि प्रश्नों का एक समूह है (हर कंप्यूटर प्रोग्राम P और इनपुट i के लिए एक प्रश्न है)।

अनिर्णनीय प्रॉब्लमों के अस्तित्व का कारण

प्रॉब्लमों की कुल संख्या अगणनीय अनंत है पर संभव अल्गोरिद्मों की कुल संख्या गणनीय अनंत है। कैंटर के प्रमेय के अनुसार अगणनीय अनंतता गणनीय अनंतता से ज्यादा बड़ी है। इसलिए प्रॉब्लमों की कुल संख्या संभव अल्गोरिद्मों की कुल संख्या से ज्यादा है, और इसलिए हर प्रॉब्लम के लिए अल्गोरिद्म नहीं बन सकता है। वास्तव में, अगणनीय अनंतता गणनीय अनंतता से इतनी बड़ी है कि यदि निर्णय प्रॉब्लमों के समुच्चय से एक निर्णय प्रॉब्लम यादृच्छिक ढंग से चुनी जाए, तो उसके अनिर्णनीय होने की सम्भावना 100% है।