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

इस लेख में सुधार किया जा रहा है। इसकी भाषा को सरल बना दिया जाएगा, और सन्दर्भ भी जोड़ दिए जाएंगे। थोड़ा समय दीजिए। सैद्धांतिक कंप्यूटर विज्ञान में अनिर्णनीय प्रॉब्लम (undecidable problem) एक ऐसी निर्णय प्रॉब्लम को कहते हैं जिसका हल करने के लिए अल्गोरिद्म नहीं बन सकता है। सरल शब्दों में अनिर्णनीय प्रॉब्लम "हाँ या ना" उत्तर वाले प्रश्नों के ऐसे समूह को कहते हैं जिसके लिए ऐसा अल्गोरिद्म बनाना असंभव है जो समूह के हर प्रश्न के लिए सही उत्तर देता हो।Kozen 1999 220 उदाहरण अनिर्णनीय प्रॉब्लम का एक उदाहरण हॉल्टिंग प्रॉब्लम है।Kozen 1999 p. 231, Sec. "Undecidability of the Halting Problem" हॉल्टिंग प्रॉब्लम निम्नलिखित निर्णय प्रॉब्लम को कहते हैं: "कंप्यूटर प्रोग्राम P इनपुट i मिलने पर क्या कभी रुकेगा?"Kozen 1999 p. 230, Sec. "Diagonalization" ऊपर दिया गया उदाहरण एक प्रश्न नहीं है, बल्कि प्रश्नों का एक समूह है (हर कंप्यूटर प्रोग्राम P और इनपुट i के लिए एक प्रश्न है)। अनिर्णनीय प्रॉब्लमों के अस्तित्व का कारण प्रॉब्लमों की कुल संख्या अगणनीय अनंत है पर संभव अल्गोरिद्मों की कुल संख्या गणनीय अनंत है। कैंटर के प्रमेय के अनुसार अगणनीय अनंतता गणनीय अनंतता से ज्यादा बड़ी है। इसलिए प्रॉब्लमों की कुल संख्या संभव अल्गोरिद्मों की कुल संख्या से ज्यादा है, और इसलिए हर प्रॉब्लम के लिए अल्गोरिद्म नहीं बन सकता है।Hopcroft Motwani Ullman 2001 p. 310, para. "Why Undecidable Problems Must Exist" वास्तव में, अगणनीय अनंतता गणनीय अनंतता से इतनी बड़ी है कि यदि निर्णय प्रॉब्लमों के समुच्चय से एक निर्णय प्रॉब्लम यादृच्छिक ढंग से चुनी जाए, तो उसके अनिर्णनीय होने की सम्भावना 100% है। ग्रन्थसूची Hopcroft John E. Motwani Rajeev Ullman Jeffrey D. Introduction to automata theory, languages, and computation https://archive.org/details/trent_0116404725818 2001 Addison-Wesley Boston, Mass. [u.a.] 0-201-44124-1 2 अंग्रेज़ी harv Kozen Dexter C. Automata and computability 1999 Springer New York, NY [u.a.] 0-387-94907-0 corr. 3 printing. अंग्रेज़ी https://books.google.co.in/books?id=8lKyxS8_CNoC&lpg=PP1&dq=automata%20and%20computability&pg=PP1#v=onepage&q&f=false 30 जनवरी 2016 harv https://web.archive.org/web/20160204040007/https://books.google.co.in/books?id=8lKyxS8_CNoC&lpg=PP1&dq=automata%20and%20computability&pg=PP1#v=onepage&q&f=false 4 फ़रवरी 2016 live श्रेणी:विज्ञान श्रेणी:कम्प्यूटर विज्ञान