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