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