Diagonalizing Through the $\omega$-Chain: Iterated Self-Certification on Bounded Turing Machines and its Least Fixed Point

यहाँ मियारा सुंग के शोध पत्र "Diagonalizing Through the $\omega$-Chain: Iterated Self-Certification on Bounded Turing Machines and its Least Fixed Point" का विस्तृत तकनीकी सारांश दिया गया है।

1. समस्या विवरण (Problem Statement)

यह शोध पत्र ट्यूरिंग मशीनों में सीमित स्व-प्रमाणन (bounded self-certification) की मौलिक सीमाओं को संबोधित करता है। विशेष रूप से, यह इस बात की जांच करता है कि क्या एक ट्यूरिंग मशीन $A$, जो एक सख्त समय सीमा $T$ के तहत कार्य करती है, यह निर्णय ले सकती है कि क्या वह अपने स्वयं के एनकोडिंग $\langle A \rangle$ को इनपुट के रूप में प्राप्त करने पर $T$ चरणों के भीतर रुकती (halt) है या नहीं।

• मुख्य संघर्ष (The Core Conflict): जबकि एक असीमित (unbounded) मशीन $A$ का अनुकरण (simulate) करके रुकने का निर्धारण कर सकती है, एक मशीन $D$ जो उसी समय सीमा $T$ के अधीन है, ऐसा नहीं कर सकती।
• ओवरहेड (The Overhead): शोध पत्र स्थापित करता है कि किसी भी मशीन के $k$ चरणों का अनुकरण करने के लिए कम से कम $k$ चरणों की आवश्यकता होती है, साथ ही एक निर्णय (verdict) देने और रुकने वाली स्थिति में संक्रमण करने के लिए कम से कम एक अतिरिक्त चरण की आवश्यकता होती है। फलस्वरूप, $T$ चरणों के भीतर रुकने के व्यवहार को तय करने के लिए $T+1$ चरणों की आवश्यकता होती है।
• परिणाम (The Consequence): एक $T$-सीमित मशीन अपने स्वयं के $T$-चरण वाले रुकने के व्यवहार को निर्धारित नहीं कर सकती; वह केवल $T-1$ तक ही देख सकती है। यह एक "संसाधन-सीमित विकर्णी तर्क" (resource-bounded diagonal argument) बनाता है जहाँ $T$ समय के भीतर $T$-वें चरण के प्रमाण की कोशिश करने से एक सख्त बड़ी समय सीमा अनिवार्य हो जाती है।

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

लेखक इस परिचालन बाधा को परिमित अवलोकन (finite observability) से अनंत गणना (infinite computation) में संक्रमण का विश्लेषण करने के लिए एक डोमेन-सैद्धांतिक ढांचे (domain-theoretic framework) में अनुवादित करते हैं।

A. डोमेन परिभाषा (Domain Definition)

शोध पत्र एक डोमेन $D$ को परिभाषित करता है जो मोनोटोनिक आंशिक फलनों (monotone partial functions) $p: \mathbb{N} \to \{0, 1, \bot\}$ का है, जो विस्तार (extension) द्वारा क्रमबद्ध है ($p \sqsubseteq q$ यदि $q$, $p$ जहाँ भी परिभाषित है वहाँ $p$ के साथ सहमत है)।

• $p(k) = 1$: मशीन चरण $k$ या उससे पहले रुक जाती है।
• $p(k) = 0$: मशीन चरण $k$ तक नहीं रुकी है।
• $p(k) = \bot$: चरण $k$ पर व्यवहार अनिर्धारित है।

B. ऑपरेटर $F$ (The Operator $F$)

एक फलन $F: D \to D$ को परिभाषित किया गया है जो मशीन के व्यवहार के अवलोकन को एक चरण आगे बढ़ाता है:

• आधार मामला ($k=0$): चरण 0 पर मशीन के प्रत्यक्ष अवलोकन को रिकॉर्ड करता है।
• आगमनात्मक चरण ($k+1$): यदि पिछला $p(k)$ $\bot$ है, तो नया $p(k+1)$ भी $\bot$ रहेगा। यदि $p(k)=1$ है, तो यह $1$ही रहेगा। यदि$p(k)=0$है, तो ऑपरेटर यह जाँचता है कि क्या मशीन ठीक चरण$k+1$ पर रुकती है।
• मुख्य गुण: $F$ केवल पिछले पद $p(k)$ पर निर्भर करता है, जिससे यह स्कॉट-निरंतर (Scott-continuous) बन जाता है।

C. पुनरावृत्ति निर्माण (Iterative Construction)

रिक्त आंशिक मॉडल $p_0 = \bot$ से शुरू करते हुए, शोध पत्र एक आरोही $\omega$-श्रृंखला (ascending $\omega$-chain) का निर्माण करता है:
$$p_0 \sqsubseteq p_1 \sqsubseteq p_2 \sqsubseteq \dots \quad \text{जहाँ} \quad p_{i+1} = F(p_i)$$
प्रत्येक $p_i$, $i$ समय सीमा वाली मशीन द्वारा किए गए रुकने के अवलोकन का प्रतिनिधित्व करता है।

3. मुख्य योगदान और परिणाम (Key Contributions and Results)

प्रमेय 1: कोई सीमित स्थिर बिंदु नहीं (No Bounded Fixed Point)

किसी भी परिमित समय सीमा $T$ के लिए, $B_T$ (समय $T$ के भीतर गणनीय मशीनें) वर्ग की कोई भी मशीन $F$ का स्थिर बिंदु (fixed point) नहीं है।

• तर्क: यदि $p \in B_T$ है, तो यह $k \geq T$ के लिए अनिर्धारित है। हालाँकि, $F(p)$ परिभाषा को $T$ तक विस्तारित करता है (क्योंकि $T$-सीमित मशीन का अनुकरण करने में $T$ चरण लगते हैं, और निर्णय के लिए $+1$ चरण आवश्यक है)। अतः, $F(p) \neq p$।
• निहितार्थ: सीमित स्व-प्रमाणन असंभव है; एक मशीन अपनी समय सीमाओं के भीतर अपने रुकने के व्यवहार को पूरी तरह से कैप्चर नहीं कर सकती।

प्रमेय 2: न्यूनतम स्थिर बिंदु अनबाउंडेड है (The Least Fixed Point is Unbounded)

ऑपरेटर का न्यूनतम स्थिर बिंदु, $p_\omega = \text{lfp}(F) = \bigsqcup_{n < \omega} p_n$ अस्तित्व में है और यह मशीन के पूर्ण रुकने के अवलोकन का प्रतिनिधित्व करता है।

• प्रकृति ($p_\omega$ की): यह एक पूर्ण फलन (total function) है जो सभी $k \in \mathbb{N}$ के लिए परिभाषित है।
• अगणनीयता (Uncomputability): $p_\omega$, $\bigcup_{T \in \mathbb{N}} B_T$ में नहीं है। इसे कंप्यूट करने के लिए अनबाउंडेड समय (समय सीमा $\omega$) की आवश्यकता होती है, जो परिमित से अनंत गणना की ओर संक्रमण का प्रतिनिधित्व करता है।

प्रमेय 3: असममित अवलोकन के माध्यम से अर्ध-निर्णय क्षमता (Semi-decidability via Asymmetric Observability)

शोध पत्र इस $\omega$-श्रृंखला के माध्यम से 'हाल्टिंग प्रॉब्लम' (Halting Problem) की अर्ध-निर्णय क्षमता (semi-decidability) की पुनर्व्याख्या करता है:

• सकारात्मक मामला (रुकना): यदि मशीन चरण $K$ पर रुकती है, तो यह गुण परिमित उपसर्ग (prefix) $p_{K+1}$ द्वारा प्रमाणित होता है। उत्तर परिमित समय में हल हो जाता है।
• नकारात्मक मामला (नहीं रुकना): यदि मशीन कभी नहीं रुकती, तो $p_\omega(k) = 0$ सभी $k$ के लिए होगा। "नहीं रुकता" की पुष्टि करने के लिए, शून्य के अनंत अनुक्रम को सत्यापित करना आवश्यक है।
• विकर्णी तंत्र (The Diagonal Mechanism): "नहीं रुकता" को तय करने का प्रयास परिमित सीमा $T$ के भीतर विफल हो जाता है क्योंकि $+1$ का ओवरहेड एक विकर्णी (diagonalizer) को चरण $T+1$ पर विरोधाभास उत्पन्न करने की अनुमति देता है। "विकर्णीय विलंबन का निरंतर स्थगन" (continuous deferral of the diagonal) नकारात्मक निर्णय को अगणनीय अनंत सीमा की ओर धकेल देता है।

4. महत्व और निहितार्थ (Significance and Implications)

1. हाल्टिंग प्रॉब्लम का पुनर्निर्धारण: यह शोध पत्र हाल्टिंग प्रॉब्लम को केवल एक तार्किक असंभवता के रूप में नहीं, बल्कि एक संसाधन-सीमित घटना के रूप में प्रस्तुत करता है। एक सीमित मशीन द्वारा स्व-प्रमाणन में विफलता का कारण अनुकरण ओवरहेड ($+1$ चरण) है, जो अपने स्वयं के समय प्रतिबंधों के भीतर एक स्थिर बिंदु बनने से रोकता है।
2. डोमेन-सैद्धांतिक समाधान: यह प्रदर्शित करता है कि जबकि कोई सीमित मशीन स्व-प्रमाणन प्राप्त नहीं कर सकती, ऑपरेटर का स्कॉट सीमा (Scott limit) मशीन के रुकने के व्यवहार को सफलतापूर्वक हल करता है। "समाधान" इस स्व-संदर्भित विरोधाभास को हल करता है, लेकिन केवल एक उच्च कम्प्यूटेशनल स्तर (अनबाउंडेड समय) पर।
3. लॉवेरे के प्रमेय से संबंध (Connection to Lawvere's Theorem): यह शोध पत्र अनुकरण ओवरहेड को लॉवेरे के फिक्स्ड पॉइंट प्रमेय से जोड़ता है। एक सीमित मशीन की अपने स्वयं के फलन स्थान (function space) पर अधिरोपण (surjection) करने में असमर्थता (ओवरहेड के कारण) एक ऐसी पुनरावृत्ति प्रक्रिया को संचालित करती जिसका स्थिर बिंदु मूल 'सीमित गणनाओं' की श्रेणी से बाहर स्थित है।
4. व्यापकता (Generality): परिणाम मॉडल-स्वतंत्र हैं। कोई भी कम्प्यूटेशनल सिस्टम जिसमें एक परिमित संसाधन सीमा और स्पष्ट रूप से सकारात्मक अनुकरण ओवरहेड (जैसे, बाउंडेड रजिस्टर मशीन, फिक्स्ड-डेप्थ सर्किट) है, वही $\omega$-श्रृंखला व्यवहार और सीमित स्व-प्रमाणन की विफलता प्रदर्शित करेगा।

निष्कर्ष (Conclusion)

मियारा सुंग का कार्य स्व-प्रमाणन को आंशिक फलनों के डोमेन पर एक पुनरावृत्ति ऑपरेटर के रूप में मॉडल करके हाल्टिंग प्रॉब्लम पर एक नवीन दृष्टिकोण प्रदान करता है। यह सिद्ध करता है कि सीमित स्व-प्रमाणन विफल होता है क्योंकि अनिवार्यतः 'टेम्पोरल ओवरहेड' (temporal overhead) मौजूद है, लेकिन परिणामी $\omega$-श्रृंखला का न्यूनतम स्थिर बिंदु (least fixed point) पूर्ण रुकने के व्यवहार को कैप्चर करता है। यह स्थिर बिंदु केवल अनबाउंडेड गणना के माध्यम से साकार होता है, जो प्रभावी रूप से यह दर्शाता है कि परिमित अवलोकन से "हाल्टिंग की सच्चाई" तक का संक्रमण, उन परिमित संसाधन सीमाओं से बाहर कदम रखने की मांग करता है जो स्वयं मशीन को परिभाषित करती हैं।