अनिर्णनीय प्रॉब्लम
सैद्धांतिक कंप्यूटर विज्ञान में अनिर्णनीय प्रॉब्लम (अंग्रेज़ी: undecidable problem) एक ऐसी निर्णय प्रॉब्लम को कहते हैं जिसका हल करने के लिए अल्गोरिद्म नहीं बन सकता है। सरल शब्दों में अनिर्णनीय प्रॉब्लम "हाँ या ना" उत्तर वाले प्रश्नों के ऐसे समूह को कहते हैं जिसके लिए ऐसा अल्गोरिद्म बनाना असंभव है जो समूह के हर प्रश्न के लिए सही उत्तर देता हो।[1]
उदाहरण संपादित करें
अनिर्णनीय प्रॉब्लम का एक उदाहरण हॉल्टिंग प्रॉब्लम है।[2] हॉल्टिंग प्रॉब्लम निम्नलिखित निर्णय प्रॉब्लम को कहते हैं:
- "कंप्यूटर प्रोग्राम P इनपुट i मिलने पर क्या कभी रुकेगा?"[3]
ऊपर दिया गया उदाहरण एक प्रश्न नहीं है, बल्कि प्रश्नों का एक समूह है (हर कंप्यूटर प्रोग्राम P और इनपुट i के लिए एक प्रश्न है)।
अनिर्णनीय प्रॉब्लमों के अस्तित्व का कारण संपादित करें
प्रॉब्लमों की कुल संख्या अगणनीय अनंत है पर संभव अल्गोरिद्मों की कुल संख्या गणनीय अनंत है। कैंटर के प्रमेय के अनुसार अगणनीय अनंतता गणनीय अनंतता से ज्यादा बड़ी है। इसलिए प्रॉब्लमों की कुल संख्या संभव अल्गोरिद्मों की कुल संख्या से ज्यादा है, और इसलिए हर प्रॉब्लम के लिए अल्गोरिद्म नहीं बन सकता है।[4] वास्तव में, अगणनीय अनंतता गणनीय अनंतता से इतनी बड़ी है कि यदि निर्णय प्रॉब्लमों के समुच्चय से एक निर्णय प्रॉब्लम यादृच्छिक ढंग से चुनी जाए, तो उसके अनिर्णनीय होने की सम्भावना 100% है।[4]
सन्दर्भ संपादित करें
- ↑ Kozen (1999, p. 220)
- ↑ Kozen (1999, p. 231, Sec. "Undecidability of the Halting Problem")
- ↑ Kozen (1999, p. 230, Sec. "Diagonalization")
- ↑ अ आ Hopcroft, Motwani & Ullman (2001, p. 310, para. "Why Undecidable Problems Must Exist")
ग्रन्थसूची संपादित करें
- Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to automata theory, languages, and computation (अंग्रेज़ी में) (2 संस्करण). Boston, Mass. [u.a.]: Addison-Wesley. आई॰ऍस॰बी॰ऍन॰ 0-201-44124-1.
- Kozen, Dexter C. (1999). Automata and computability (अंग्रेज़ी में) (corr. 3 printing. संस्करण). New York, NY [u.a.]: Springer. आई॰ऍस॰बी॰ऍन॰ 0-387-94907-0. मूल से 4 फ़रवरी 2016 को पुरालेखित. अभिगमन तिथि 30 जनवरी 2016.