संगणनीय गणनीय समुच्चय और ट्यूरिंग डिग्री
संगणनीय गणनीय समुच्चय वे होते हैं जिनके सदस्यों को प्रभावी ढंग से सूचीबद्ध किया जा सकता है, और ट्यूरिंग डिग्री सापेक्ष संगणनीयता के आधार पर सभी समुच्चयों को रैंक करती है, जिससे अनसुलझी समस्याओं के परिदृश्य को व्यवस्थित किया जाता है।
Definition
एक समुच्चय संगणनीय गणनीय होता है यदि कोई एल्गोरिथम उसके सदस्यों को ठीक-ठीक सूचीबद्ध करता है; एक समुच्चय दूसरे के लिए ट्यूरिंग न्यूनीकरणशील होता है यदि इसे दूसरे को एक ओरेकल के रूप में उपयोग करके संगणित किया जा सकता है, और पारस्परिक न्यूनीकरणशीलता के तहत तुल्यता वर्ग ट्यूरिंग डिग्री होते हैं, जो सापेक्ष संगणनीयता द्वारा आंशिक रूप से क्रमित होते हैं।
Scope
यह विषय संगणनीय गणनीय समुच्चयों और उनके मूल गुणों, ट्यूरिंग न्यूनीकरणशीलता और डिग्री के आंशिक क्रम, एक पूर्ण गणनीय समुच्चय के रूप में हॉल्टिंग समुच्चय, पोस्ट की समस्या और प्राथमिकता विधि द्वारा इसके समाधान, और संगणनीय गणनीय डिग्री के संरचनात्मक सिद्धांत को शामिल करता है।
Core questions
- एक संगणनीय और केवल संगणनीय गणनीय समुच्चय के बीच क्या अंतर है?
- ट्यूरिंग न्यूनीकरणशीलता दो समुच्चयों की कठिनाई की तुलना कैसे करती है?
- क्या संगणनीय समुच्चयों और हॉल्टिंग समस्या के बीच कड़ाई से संगणनीय गणनीय डिग्री मौजूद हैं?
- अनसुलझी डिग्री की वैश्विक संरचना क्या है?
Key theories
- पूरकता और हॉल्टिंग समुच्चय
- एक समुच्चय ठीक-ठीक संगणनीय होता है जब वह और उसका पूरक दोनों संगणनीय गणनीय होते हैं, और हॉल्टिंग समुच्चय संगणनीय गणनीय होता है लेकिन संगणनीय नहीं होता, जो विहित पूर्ण गणनीय समुच्चय है।
- पोस्ट की समस्या और प्राथमिकता विधि
- पोस्ट ने पूछा कि क्या संगणनीय समुच्चयों और हॉल्टिंग समस्या के बीच कड़ाई से संगणनीय गणनीय डिग्री मौजूद हैं; फ्रीडबर्ग और मुचनिक ने परिमित-चोट प्राथमिकता विधि का आविष्कार करके हाँ में उत्तर दिया।
- डिग्री की संरचना
- ट्यूरिंग डिग्री और संगणनीय गणनीय डिग्री उन्नत प्राथमिकता निर्माणों के माध्यम से अध्ययन की गई समृद्ध, सघन रूप से क्रमित संरचनाएं बनाती हैं, जो जटिल परिभाषा और एम्बेडिंग गुणों को प्रकट करती हैं।
Clinical relevance
डिग्री का सिद्धांत अनसुलझी समस्याओं का सूक्ष्म वर्गीकरण प्रदान करता है, यह दर्शाता है कि अनिर्णयता अनगिनत कड़ाई से बढ़ते स्तरों में आती है, और उनका अध्ययन करने के लिए विकसित प्राथमिकता विधि एक केंद्रीय प्रमाण तकनीक है जिसने रिवर्स गणित और एल्गोरिथम यादृच्छिकता के विश्लेषण को प्रभावित किया है।
History
पोस्ट ने 1944 में संगणनीय गणनीय समुच्चयों को प्रस्तुत किया और अपनी समस्या रखी, जिसमें पूछा गया था कि क्या अपूर्ण अगणनीय गणनीय डिग्री मौजूद हैं। फ्रीडबर्ग और मुचनिक ने लगभग 1956 में प्राथमिकता विधि के साथ स्वतंत्र रूप से इसे हल किया, जो सैक्स, सोरे और कई अन्य लोगों द्वारा डिग्री के गहन संरचनात्मक अध्ययन के लिए प्रमुख उपकरण बन गया।
Key figures
- Emil Post
- Richard Friedberg
- Albert Muchnik
- Robert Soare
Related topics
Seminal works
- soare1987
- post1944
- rogers1987
Frequently asked questions
- संगणनीयता सिद्धांत में ओरेकल क्या है?
- एक ओरेकल एक बाहरी स्रोत है जो एक निश्चित समुच्चय के लिए सदस्यता प्रश्नों का तुरंत उत्तर देता है। एक ओरेकल वाली मशीन अपनी गणना के दौरान उन उत्तरों का उपयोग कर सकती है, और ट्यूरिंग न्यूनीकरणशीलता यह पूछती है कि क्या एक समुच्चय को दूसरे समुच्चय को उसके ओरेकल के रूप में सुसज्जित मशीन द्वारा संगणित किया जा सकता है।
- पोस्ट की समस्या क्यों महत्वपूर्ण थी?
- इसने पूछा कि क्या संगणनीय गणनीय समुच्चयों के बीच अनिर्णयता के मध्यवर्ती स्तर हैं, जो निर्णय योग्य और हॉल्टिंग समस्या के बीच हैं। सकारात्मक उत्तर ने डिग्री की एक सूक्ष्म संरचना का खुलासा किया और प्राथमिकता विधि की आवश्यकता थी, एक शक्तिशाली नई तकनीक जिसने पूरे विषय को आकार दिया है।