अनिर्णयता और हॉल्टिंग समस्या
हॉल्टिंग समस्या यह पूछती है कि क्या कोई दिया गया प्रोग्राम किसी दिए गए इनपुट पर अंततः रुकता है, और ट्यूरिंग का यह प्रमाण कि कोई भी एल्गोरिथम सभी मामलों के लिए इसका उत्तर नहीं दे सकता, एक अनिर्णयनीय समस्या का संस्थापक उदाहरण है।
Definition
एक निर्णय समस्या अनिर्णयनीय होती है जब कोई एल्गोरिथम हर इनपुट के लिए इसका सही उत्तर नहीं दे सकता; हॉल्टिंग समस्या, यह तय करना कि एक मनमाना प्रोग्राम एक मनमाने इनपुट पर रुकता है या नहीं, विहित अनिर्णयनीय समस्या है, जिसे एक स्व-संदर्भित विकर्ण तर्क द्वारा सिद्ध किया गया है।
Scope
यह विषय हॉल्टिंग समस्या की अनिर्णयता स्थापित करने वाले विकर्णीकरण तर्क, निर्णयनीय, पहचाननीय और सह-पहचाननीय समस्याओं के बीच के अंतर, राइस के प्रमेय को शामिल करता है जो दर्शाता है कि प्रोग्राम के सभी गैर-तुच्छ सिमेंटिक गुण अनिर्णयनीय हैं, और तर्क, गणित और कंप्यूटर विज्ञान में प्राकृतिक अनिर्णयनीय समस्याओं की सूची।
Core questions
- कोई एक एल्गोरिथम यह क्यों नहीं तय कर सकता कि हर प्रोग्राम रुकता है या नहीं?
- किसी समस्या के निर्णयनीय होने और केवल पहचाननीय होने में क्या अंतर है?
- प्रोग्राम व्यवहार के अनिवार्य रूप से सभी दिलचस्प गुण अनिर्णयनीय क्यों हैं?
- अनिर्णयता हॉल्टिंग समस्या से अन्य समस्याओं तक कैसे फैलती है?
Key theories
- हॉल्टिंग समस्या की अनिर्णयता
- यह मानते हुए कि एक एल्गोरिथम है जो हॉल्टिंग का निर्णय करता है, एक ऐसे प्रोग्राम के माध्यम से विरोधाभास होता है जो ठीक तभी रुकता है जब उसके न रुकने की भविष्यवाणी की जाती है, इसलिए ऐसा कोई एल्गोरिथम मौजूद नहीं हो सकता।
- राइस का प्रमेय
- किसी प्रोग्राम द्वारा गणना किए गए फ़ंक्शन का हर गैर-तुच्छ गुण — कुछ भी जो कुछ प्रोग्रामों के लिए सत्य है और व्यवहार के आधार पर दूसरों के लिए विफल रहता है — अनिर्णयनीय है, जो हॉल्टिंग परिणाम को सभी सिमेंटिक गुणों तक सामान्यीकृत करता है।
Clinical relevance
क्योंकि हॉल्टिंग और, राइस के प्रमेय के अनुसार, प्रोग्राम के सभी गैर-तुच्छ व्यवहारिक गुण अनिर्णयनीय हैं, कोई भी उपकरण अनंत लूपों का पूरी तरह से पता नहीं लगा सकता है, मनमानी शुद्धता को सत्यापित नहीं कर सकता है, या हर प्रोग्राम का पूरी तरह से विश्लेषण नहीं कर सकता है; इसलिए स्टैटिक एनालाइज़र और वेरिफ़ायर को अनुमान लगाना होगा, गलत अलार्म स्वीकार करने होंगे, या अपने दायरे को प्रतिबंधित करना होगा।
History
ट्यूरिंग ने 1936 में कैंटर और गोडेल से प्रेरित एक विकर्ण तर्क का उपयोग करके हॉल्टिंग समस्या और तर्क के लिए निर्णय समस्या की अनिर्णयता स्थापित की। राइस ने 1953 में अपने व्यापक सामान्यीकरण को सिद्ध किया, और अगले दशकों में, डायोफैंटाइन समीकरणों पर हिल्बर्ट की दसवीं समस्या सहित कई प्राकृतिक समस्याओं को अनिर्णयनीय दिखाया गया।
Key figures
- Alan Turing
- Henry Gordon Rice
- Emil Post
- Alonzo Church
Related topics
Seminal works
- turing1937
- sipser2013
Frequently asked questions
- हम यह देखने के लिए किसी प्रोग्राम को क्यों नहीं चला सकते कि वह रुकता है या नहीं?
- इसे चलाने से आपको तभी पता चलता है कि यह रुक गया है जब यह वास्तव में रुकता है; यदि यह हमेशा के लिए चलने वाला है, तो कोई भी सीमित प्रतीक्षा इसे प्रकट नहीं करती है। हॉल्टिंग समस्या एक ऐसी विधि की मांग करती है जो हर प्रोग्राम और इनपुट के लिए सीमित समय में हमेशा सही उत्तर देती है, और ट्यूरिंग ने सिद्ध किया कि ऐसी कोई विधि मौजूद नहीं है।
- क्या अनिर्णयता प्रोग्राम विश्लेषण को निराशाजनक बनाती है?
- नहीं, लेकिन यह बताता है कि सही विश्लेषण असंभव क्यों है। उपकरण रूढ़िवादी होकर, किसी भी चीज़ को चिह्नित करके, जिसे वे सुरक्षित साबित नहीं कर सकते, प्रोग्रामों के प्रतिबंधित वर्गों को सटीक रूप से संभालकर, या कई व्यावहारिक मामलों को हल करके, यह स्वीकार करते हुए कि वे प्रतिकूल या रोग संबंधी मामलों पर विफल हो सकते हैं, सामना करते हैं।