तकनीकी सारांश: पर्यवेक्षक, सममिति, और भाषा वर्गों का पदानुक्रम

समस्या विवरण

शास्त्रीय गणनात्मक जटिलता (computational complexity) और औपचारिक भाषा सिद्धांत पारंपरिक रूप से समस्याओं को मशीन की गणनात्मक शक्ति (जैसे, परिमित ऑटोमेटा, पुशडाउन ऑटोमेटा, ट्यूरिंग मशीन) के आधार पर वर्गीकृत करते हैं और यह मान लेते हैं कि इनपुट एक पूर्णतः सुलभ, क्रमित प्रतीकों का अनुक्रम है। यह शोध पत्र उस दृष्टिकोण को उलट देता है, यह प्रस्तावित करते हुए कि एक गणनात्मक प्रणाली की सीमाएँ मशीन की प्रसंस्करण शक्ति से नहीं, बल्कि पर्यवेक्षक की संरचना (structure of the observer) से उत्पन्न हो सकती हैं।

केंद्रित समस्या यह है: कौन सी भाषाएँ एक गणनात्मक प्रणाली पहचान सकती है जब उसके पास संपूर्ण इनपुट स्ट्रिंग तक पहुँच नहीं होती, बल्कि केवल उसके एक विशिष्ट प्रक्षेपण (projection) या रूपांतरण तक पहुँच होती है? यह शोध पत्र इस बात की जांच करता है कि एक पर्यवेक्षक फलन $O: \Sigma^* \to S$ (जो एक इनपुट स्ट्रिंग को अवलोकन स्थान $S$ में मैप करता है) की "अंधता" या "संरचनात्मक सीमाएँ" मशीन के गणनात्मक मॉडल से स्वतंत्र होकर, पहचानने योग्य भाषाओं के वर्ग को कैसे निर्धारित करती हैं।

कार्यप्रणाली (Methodology)

यह शोध पत्र एक औपचारिक ढांचे को प्रस्तुत करता है जो एक पर्यवेक्षक (observer) की अवधारणा पर केंद्रित है:

1. पर्यवेक्षक की परिभाषा: एक पर्यवेक्षक एक फलन $O$ है जो एक इनपुट स्ट्रिंग $x$ को एक अवलोकन $O(x)$ में परिवर्तित करता है। एक गणनात्मक प्रणाली $(M, O)$ $x$ के बजाय $O(x)$ को अपने इनपुट के रूप में प्राप्त करती है।
2. O-संतृप्ति (O-Saturation): एक भाषा $L$, $O$-संतृप्त है यदि $L$ में सदस्यता केवल अवलोकन $O(x)$ पर निर्भर करती है। औपचारिक रूप से, $x \sim_O y \implies (x \in L \iff y \in L)$। यदि कोई भाषा $O$-संतृप्त नहीं है, तो $O$ पर्यवेक्षक से सुसज्जित कोई भी मशीन उसे निर्णायक रूप से हल नहीं कर सकती, चाहे उसकी गणनात्मक शक्ति कुछ भी हो।
3. अवलोकन संबंधी क्रम (Observational Order): एक प्रीऑर्डर $\preceq$ को पर्यवेक्षकों पर परिभाषित किया गया है जहाँ $O_1 \preceq O_2$ तब होता है जब $O_1$ को $O_2$ से व्युत्पन्न किया जा सकता है (अर्थात, $O_1 = f \circ O_2$)। यह भाषा वर्गों के एक पदानुक्रम $\mathcal{L}(O)$ को प्रेरित करता है, जहाँ $O_1 \preceq O_2 \implies \mathcal{L}(O_1) \subseteq \mathcal{L}(O_2)$।
4. मानक पर्यवेक्षक (Canonical Observers): पदानुक्रम के निर्माण के लिए शोध पत्र विशिष्ट पर्यवेक्षकों को परिभाषित करता है:
   • $O_\perp$: तुच्छ पर्यवेक्षक (सभी स्ट्रिंग्स को एक स्थिरांक में मैप करता है)।
   • $O_{len}$: लंबाई पर्यवेक्षक (मान $|x|$ में मैप करता है)।
   • $O_{par}$: पैरिटी (parity) पर्यवेक्षक (मान 2 के गुणांकों के रूप में गणना करता है)।
   • $O_{prof}$: प्रोफ़ाइल पर्यवेक्षक (क्रम की उपेक्षा करते हुए, प्रतीक गणनाओं के वेक्टर के रूप में मैप करता है)।
   • $O_k$: उप-अनुक्रम (subsequence) पर्यवेक्षक (लंबाई $\le k$ के उप-अनुक्रमों के सेट में मैप करता है)।
   • $O_\top$: पूर्ण पर्यवेक्षक (तत्काल/identity, $O(x) = x$)।

मुख्य योगदान और परिणाम

1. ऑर्डर-ब्लाइंड ऑटोमेटा और क्रमपरिवर्तन-बंद भाषाएँ (Permutation-Closed Languages)

शोध पत्र एक ऑर्डर-ब्लाइंड ऑटोमेटा की विशेषता बताता है, जो एक ऐसी मशीन है जो स्ट्रिंग के अनुक्रम के बजाय उसके प्रोफ़ाइल (प्रतीक गणनाओं का मल्टीसेट) को संसाधित करती है।

• प्रमेय 2.5: एक भाषा ऑर्डर-ब्लाइंड ऑटोमेटा द्वारा तभी पहचानी जा सकती है जब वह क्रमपरिवर्तन-बंद (permutation-closed) (प्रतीक पुनर्व्यवस्था के तहत अपरिवर्तित) हो।
• यह परिणाम दर्शाता है कि अवस्थाओं (states) की परिमितता प्राथमिक बाधा नहीं है; बल्कि, पर्यवेक्षक ही वर्ग को निर्धारित करता है। यहाँ तक कि एक तुच्छ पर्यवेक्षक के साथ ट्यूरिंग मशीन भी केवल $\emptyset$ और $\Sigma^*$ को ही पहचान सकती है।

2. अवलोकन संबंधी पदानुक्रम (The Observational Hierarchy)

शोध पत्र मानक पर्यवेक्षकों की अवलोकन क्षमता के आधार पर भाषा वर्गों के एक आंशिक क्रम (partial order) का निर्माण करता है। पदानुक्रम एक विशिष्ट संरचना प्रदर्शित करता है:

• डायमंड-आकार का प्रोफ़ाइल उप-लैटिस (Diamond-Shaped Profile Sub-lattice):
  • $O_\perp \prec O_{len} \prec O_{prof} \prec O_\top$ (लंबाई शाखा)
  • $O_\perp \prec O_{par} \prec O_{prof} \prec O_\top$ (पैरिटी शाखा)
  • $O_{len}$ और $O_{par}$ तुलनाहीन (incomparable) हैं।
• अनंत उप-अनुक्रम शाखा:
  • $O_\perp \prec O_1 \prec O_2 \prec \dots \prec O_\top$।
  • यह शाखा साइमन के 'पीसवाइज टेस्टेबल' (piecewise testable) भाषाओं के पदानुक्रम के अनुरूप है।
• लंबवतता (Orthogonality): प्रोफ़ाइल उप-लैटिस (गणना संबंधी जानकारी) और उप-अनुक्रम शाखा (आंशिक क्रम संबंधी जानकारी) तुलनाहीन हैं। $O_{prof}$, किसी भी $O_k$ के साथ तुलनाहीन है।

3. चोमस्की पदानुक्रम के साथ लंबवतता (Orthogonality with the Chomsky Hierarchy)

शोध पत्र सिद्ध करता है कि अवलोकन संबंधी पदानुक्रम चोमस्की पदानुक्रम (Regular, Context-Free, आदि) के साथ पूर्णतः लंबवत (orthogonal) है।

• ऐसी भाषाएँ मौजूद हैं जो Regular हैं लेकिन $O$-संतृप्त नहीं हैं (जैसे, $0^*1^*$ $O_{prof}$-संतृप्त नहीं है)।
• ऐसी भाषाएँ मौजूद हैं जो $O$-संतृप्त हैं लेकिन Regular नहीं हैं (जैसे, $\{x \mid |x|_0 = |x|_1\}$ $O_{prof}$-संतृप्त है लेकिन regular नहीं है)।
• यह स्थापित करता है कि "संरचनात्मक अंधता" और "गणनात्मक जटिलता" वर्गीकरण के स्वतंत्र अक्ष हैं।

4. साइमन के पदानुक्रम के साथ संबंध

शोध-पत्र साइमन के प्रमेय को पुनर्गठित करता जो पीसवाइज टेस्टेबल भाषाओं से संबंधित है।

• पर्यवेक्षकों का परिवार $\{O_k\}$ साइमन के पदानुक्रम में तुल्यता संबंधों (equivalence relations) के सटीक अनुरूप है।
• एक नियमित भाषा पीसवाइज टेस्टेबल है यदि और केवल यदि वह किसी $O_k$ द्वारा निर्णायक रूप से हल की जा सकती है।
• प्रोफ़ाइल वर्ग $\mathcal{L}(O_{prof})$ और पीसवाइज टेस्टेबल भाषाओं का संघ $\bigcup_k \mathcal{L}(O_k)$ तुलनाहीन हैं।

5. पर्यवेक्षक-पैरामीटराइज्ड जटिलता वर्ग (PO और NPO)

इस ढांचे को जटिलता सिद्धांत में विस्तारित करने के लिए $PO$और$NPO$वर्गों को परिभाषित किया गया है, जहाँ जटिलता इनपुट आकार$|x|$के बजाय अवलोकन के आकार$|enc(O(x))|$ के सापेक्ष मापी जाती है।

• संरचनात्मक पतन (Structural Collapse): शोध पत्र सिद्ध करता है कि $PO_{prof} = NPO_{prof}$।
  • महत्व: यह $P$ बनाम $NP$का समाधान नहीं है। इसके बजाय, यह एक **संरचनात्मक पतन** है जो इसलिए होता है क्योंकि$O_{prof}$ सभी संयोजी संरचना (combinatorial structure/order) को हटा देता है। क्रम के बिना, गैर-नियतिवाद (nondeterminism) नियतिवाद (determinism) पर कोई लाभ नहीं देता है।
  • कठोर समावेशन (Strict Containment): $PO_{prof} \subsetneq P$। वर्ग $PO_{prof}$ में केवल वे $O_{prof}$-संतृप्त भाषाएँ शामिल हैं जो प्रोफ़ाइल आकार के सापेक्ष बहुपद समय (polynomial time) में गणनीय हैं। चूंकि $0^*1^*$ वर्ग $P$ में है लेकिन $O_{prof}$-संतृप्त नहीं है, इसलिए समावेशन सख्त (strict) है।
• कठिनाई और अंधता की स्वतंत्रता: शोध पत्र प्रदर्शित करता है कि गणनात्मक कठिनाई और अवलोकन संबंधी निर्णायकता स्वतंत्र हैं। ऐसी भाषाएँ $P$ में हैं जो $O_{prof}$-संतृप्त नहीं हैं, और ऐसी भाषाएँ भी हैं जो रिकर्सिवली एन्यूमेरेबल (RE) वर्ग से बाहर हैं लेकिन $O_{prof}$-संतृप्त हैं (जैसे, प्रतीक गणनाओं पर आधारित हाल्टिंग समस्या वाली भाषाएँ)।

महत्व और दावे

शोध पत्र का दावा है कि यह औपचारिक भाषाओं और गणनात्मक समस्याओं को वर्गीकृत करने के लिए एक नया, स्वतंत्र अक्ष प्रस्तुत करता है। इसका प्राथमिक महत्व निम्नलिखित में निहित है:

1. मशीन शक्ति को पर्यवेक्षक संरचना से अलग करना: यह स्थापित करता है कि एक पर्यवेक्षक की "कमजोरी" एक समस्या को ट्यूरिंग मशीन के लिए भी असंभव बना सकती है, जबकि एक कमजोर मशीन (जैसे, DFA) एक मजबूत पर्यवेक्षक के साथ उसे हल कर सकती है।
2. कठिनाई और अंधता के बीच अंतर: यह गणनात्मक कठिनाई (एल्गोरिद्मिक जटिलता के कारण होने वाली कठिनाई) और संरचनात्मक अंधता (सूचना की हानि के कारण अंतर करने में असमर्थता) को औपचारिक रूप से अलग करता है। $PO_{prof} = NPO_{prof}$ का पतन यह प्रमाण है कि ये अलग-अलग घटनाएँ हैं; यह पतन इसलिए होता है क्योंकि पर्यवेक्षक उस संरचना को हटा देता है जो समस्याओं को कठिन बनाती है, न कि इसलिए कि गैर-नियतिवाद स्वाभाविक रूप से कमजोर है।
3. भौतिक व्याख्या: यह ढांचा सांख्यिकीय यांत्रिकी (statistical mechanics) के साथ एक औपचारिक समानता प्रदान करता है, जहाँ एक स्थूल (macroscopic) पर्यवेक्षक (जो केवल तापमान या घनत्व जैसे समग्र मात्राओं को देखता है) एक-दूसरे के क्रमपरिवर्तनों (permutations) वाले सूक्ष्म इतिहासों के बीच अंतर नहीं कर सकता है। यह "ऊष्मागतिक अपरिवर्तनीयता" (thermodynamic irreversibility) को एक अवलोकन संबंधी गुण के रूप में समझने के लिए एक गणितीय आधार प्रदान करता है।

शोध पत्र निष्कर्ष निकालता है कि अवलोकन संबंधी पदानुक्रम उन प्रणालियों के विश्लेषण के लिए एक कठोर ढांचा प्रदान करता जहाँ सूचना स्वाभाविक रूप से सीमित या संकलित (aggregated) होती है, और यह सुझाव देता है कि भविष्य के शोध को संभाव्य पर्यवेक्षकों (probabilistic observers), पर्यवेक्षकों के श्रेणीबद्ध संयोजन (categorical compositions), और अवलोकन संबंधी जटिलता एवं सूचना संरक्षण के बीच मात्रात्मक संबंध की खोज करनी चाहिए।