अंकगणितीय पदानुक्रम
अंकगणितीय पदानुक्रम प्राकृतिक संख्याओं के सेटों को परिभाषित करने के लिए आवश्यक वैकल्पिक क्वांटिफायर की संख्या के आधार पर वर्गीकृत करता है, जो तार्किक जटिलता को अगणनीयता की डिग्री से जोड़ता है।
Definition
अंकगणितीय पदानुक्रम प्रथम-क्रम अंकगणित में परिभाषित सेटों को एक गणनीय मैट्रिक्स के सामने असीमित क्वांटिफायर के प्रत्यावर्तन की गणना करके स्तरीकृत करता है, जिसमें सिग्मा-एन सेट एक अस्तित्वगत क्वांटिफायर से शुरू होने वाले ब्लॉक द्वारा परिभाषित होते हैं और पाई-एन सेट एक सार्वभौमिक क्वांटिफायर से शुरू होने वाले ब्लॉक द्वारा परिभाषित होते हैं।
Scope
यह विषय गणनीय संबंधों पर क्वांटिफायर प्रत्यावर्तन द्वारा सिग्मा, पाई और डेल्टा स्तरों में परिभाषित सेटों के वर्गीकरण को शामिल करता है, पोस्ट का प्रमेय जो पदानुक्रम को पुनरावृत्त हॉल्टिंग समस्या और ट्यूरिंग जंप से संबंधित करता है, पदानुक्रम की कठोरता, और विश्लेषणात्मक पदानुक्रम तक इसका विस्तार।
Core questions
- क्वांटिफायर प्रत्यावर्तन एक सेट की जटिलता को कैसे मापता है?
- प्रत्येक स्तर पर सिग्मा, पाई और डेल्टा वर्ग एक दूसरे से कैसे संबंधित हैं?
- पदानुक्रम हॉल्टिंग समस्या को दोहराने के अनुरूप कैसे है?
- पदानुक्रम कठोर क्यों है, जिसमें प्रत्येक स्तर पिछले स्तर से यथोचित रूप से बड़ा है?
Key theories
- क्वांटिफायर वर्गीकरण
- एक सेट सिग्मा-एन होता है यदि इसे एक गणनीय संबंध पर अस्तित्वगत रूप से शुरू होने वाले n वैकल्पिक क्वांटिफायर ब्लॉकों द्वारा परिभाषित किया जा सकता है, और पाई-एन यदि सार्वभौमिक रूप से शुरू होता है; गणनीय रूप से गणना योग्य सेट ठीक सिग्मा-वन सेट होते हैं।
- पोस्ट का प्रमेय
- एक सेट सिग्मा-(n+1) होता है जब यह n-वें ट्यूरिंग जंप के सापेक्ष गणनीय रूप से गणना योग्य होता है, जो पदानुक्रम के स्तरों को पुनरावृत्त सापेक्ष हॉल्टिंग समस्याओं से जोड़ता है।
- पदानुक्रम की कठोरता
- प्रत्येक ट्यूरिंग जंप पिछले वाले की तुलना में सख्ती से अधिक जटिल होता है, इसलिए अंकगणितीय पदानुक्रम का प्रत्येक स्तर अपने नीचे के स्तरों को यथोचित रूप से समाहित करता है और पदानुक्रम ध्वस्त नहीं होता है।
Clinical relevance
अंकगणितीय पदानुक्रम तर्क और कंप्यूटर विज्ञान में परिभाषित समस्याओं की जटिलता के लिए मानक मानदंड है: यह गणनीय सेटों की समग्रता, परिमितता और सह-परिमितता जैसी समस्याओं को सटीक स्तरों पर रखता है, और यह उस सीमा को निर्धारित करता है जो गणनीय रूप से गणना योग्य है और जिसके लिए मजबूत अगणनीय संसाधनों की आवश्यकता होती है।
History
क्लीन और मोस्तोव्स्की ने लगभग 1943 में स्वतंत्र रूप से अंकगणितीय पदानुक्रम प्रस्तुत किया, जिसमें गणनीय विधेय पर क्वांटिफायर जटिलता द्वारा सेटों को वर्गीकृत किया गया। पोस्ट के प्रमेय ने पदानुक्रम को ट्यूरिंग जंप से जोड़ा, जिससे परिभाषा-आधारित और गणना-आधारित दृष्टिकोणों को एकीकृत किया गया, और बाद में इस ढांचे को विश्लेषणात्मक पदानुक्रम में ऊपर की ओर विस्तारित किया गया।
Key figures
- Stephen Cole Kleene
- Andrzej Mostowski
- Emil Post
Related topics
Seminal works
- rogers1987
- soare1987
- cutland1980
Frequently asked questions
- पदानुक्रम में उच्च स्तर का क्या अर्थ है?
- अधिक वैकल्पिक क्वांटिफायर का अर्थ है एक अधिक जटिल परिभाषा और, पोस्ट के प्रमेय के अनुसार, एक समस्या जिसे तय करने के लिए हॉल्टिंग समस्या के अधिक पुनरावृत्तियों की आवश्यकता होती है। पदानुक्रम में उच्च सेट अपने नीचे के सेटों की तुलना में गणना के लिए सख्ती से कम सुलभ होते हैं।
- गणनीय रूप से गणना योग्य सेट कहाँ स्थित होते हैं?
- वे सिग्मा-वन स्तर पर कब्जा करते हैं, जो एक गणनीय संबंध पर एक एकल अस्तित्वगत क्वांटिफायर द्वारा परिभाषित होते हैं। उनके पूरक पाई-वन स्तर पर कब्जा करते हैं, और जो सेट दोनों होते हैं, डेल्टा-वन सेट, ठीक गणनीय सेट होते हैं।