💻 computer science

Loop Termination and Generalized Collatz Sequences

यह शोध पत्र पूर्णांकों पर एक-चर रैखिक-प्रतिबंध लूप (one-variable linear-constraint loops) की समाप्ति और सामान्यीकृत कोलात्ज़ अनुक्रमों (generalized Collatz sequences) के बीच एक घनिष्ठ संबंध स्थापित करता है, जो यह सिद्ध करता है कि इन अनुक्रमों के बारे में एक विशिष्ट अनुमान पर निर्भर करते हुए लूप की समाप्ति बहुपद समय (polynomial time) में निर्णायक (decidable) है, और साथ ही यह भी प्रदर्शित करता है कि ऐसे लूपों के लिए कोई भी निर्णय प्रक्रिया (decision procedure) इस अनुमान के खुले मामलों को हल कर देगी।

मूल लेखक: Mishel Carelli

प्रकाशित 2026-05-15

📖 6 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Mishel Carelli

मूल पेपर CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक रोबोट को भूलभुलैया (maze) में चलते हुए देख रहे हैं। हर बार जब रोबोट एक कदम उठाता है, तो वह दीवारों पर लिखे नियमों के एक सख्त सेट का पालन करता है। बड़ा सवाल जो कंप्यूटर वैज्ञानिक पूछते हैं: क्या यह रोबोट कभी एक अंतहीन लूप (endless loop) में फंस जाएगा, बिना रुके हमेशा के लिए चलता रहेगा?

यह शोध पत्र एक विशिष्ट प्रकार के रोबोट और एक विशिष्ट प्रकार की भूलभुलैया के लिए इस प्रश्न को संबोधित करता है। यहाँ उस कहानी का विवरण है जो लेखिका, मिशेल कारेली (Mishel Carelli) ने खोजा और सरल शब्दों में समझाया है।

1. रोबोट और नियम

"रोबोट" एक कंप्यूटर प्रोग्राम है जिसमें केवल एक संख्या (एक सिंगल वेरिएबल) होती है जो समय के साथ बदलती रहती है। "नियम" सरल गणितीय असमानताएं (inequalities) हैं (जैसे "अगली संख्या वर्तमान संख्या के दोगुने से 5 कम होनी चाहिए")।

लेखिका "क्या यह हमेशा के लिए चलेगा?" के प्रश्न को दो परिदृश्यों में विभाजित करती हैं:

लूप (The Loop): रोबोट एक घेरे में घूमता है, बार-बार ठीक उन्हीं जगहों पर आता है।
एकतरफा रास्ता (The One-Way Street): रोबोट किसी भी जगह को दोहराता नहीं है, लेकिन वह चलते रहना जारी रखता है, और दूर होता जाता है।

2. चक्र की समस्या (Cycles)

सबसे पहले, लेखिका ने "लूप" परिदृश्य को देखा।

खोज: यदि एक रोबोट जो केवल एक संख्या का उपयोग करता है, एक लूप में फंस जाता है, तो उसे इसके लिए किसी विशाल या जटिल चक्र की आवश्यकता नहीं होती। उसे केवल एक छोटे से चक्र की आवश्यकता होती जिसमें एक या दो कदम हों।
उपमा: कल्पना कीजिए कि एक बच्चा गोल घूम रहा है। आपको लग सकता है कि अनंत काल तक घूमने के लिए उसे एक बड़े खेल के मैदान की आवश्यकता होगी। लेकिन यह शोध पत्र सिद्ध करता है कि यदि वह घूम रहा है, तो वह केवल एक छोटी सी जगह में घूम रहा है, या तो एक पैर पर खड़ा होकर (1 स्टेप) या दो जगहों के बीच आगे-पीछे कूदकर (2 स्टेप्स)।
परिणाम: क्योंकि हम जानते हैं कि चक्र दो कदमों से बड़ा नहीं हो सकता, इसलिए हम आसानी से जांच सकते हैं कि क्या रोबोट एक लूप में फंसा हुआ है। इस समस्या का यह हिस्सा हल हो गया है।

3. एकतरफा रास्ता समस्या (Self-Avoiding Traces)

कठिन हिस्सा "एकतरफा रास्ता" है। यह तब होता है जब रोबोट हमेशा के लिए चलता है लेकिन कभी भी एक ही संख्या पर दोबारा कदम नहीं रखता।

एक प्रसिद्ध पहेली से संबंध: लेखिका ने महसूस किया कि इन एक-संख्या वाले प्रोग्रामों के लिए, रोब la का पथ बिल्कुल एक प्रसिद्ध, अनसुलझी गणितीय पहेली की तरह दिखता है जिसे कोलात्ज़ अनुमान (Collatz Conjecture) या "3x + 1" समस्या कहा जाता है।
- कोलात्ज़ पहेली: किसी भी संख्या से शुरू करें। यदि यह सम (even) है, तो 2 से भाग दें। यदि यह विषम (odd) है, तो 3 से गुणा करें और 1 जोड़ें। दोहराएं। क्या हर संख्या अंततः 4-2-1 के लूप में गिर जाती है? अभी तक कोई निश्चित रूप से नहीं जानता।
- शोध पत्र का मोड़: लेखिका ने इस पहेली का एक "कमजोर" संस्करण बनाया जिसे रीचेबिलिटी कंजेक्चर (Reachability Conjecture) कहा जाता है। यह पूछता है: "यदि एक संख्या हमेशा के लिए बढ़ती रहती है, तो क्या वह अंततः एक विशिष्ट प्रकार की संख्या (एक विशिष्ट अवशेष वर्ग/residue class) तक पहुँचेगी?"
बड़ा व्यापार (The Big Trade): यह शोध पत्र कंप्यूटर विज्ञान और संख्या सिद्धांत (number theory) के बीच एक पूर्ण दो-तरफा रास्ता दिखाता है:
1. यदि हम इस "रीचेबिलिटी कंजेक्चर" को सच साबित कर सकते हैं, तो हम तुरंत बता सकते हैं कि कोई भी एक-संख्या वाला प्रोग्राम रुकेगा या हमेशा के लिए चलेगा।
2. इसके विपरीत, यदि हम एक ऐसा कंप्यूटर प्रोग्राम बनाते हैं जो यह तय कर सके कि ये लूप रुकते हैं या नहीं, तो वह प्रोग्राम "रीचेबिलिटी कंजेक्चर" को भी हल कर देगा।

4. रोबोट के पथ का "मानचित्र" (The Map)

यह पता लगाने के लिए कि क्या रोबोट हमेशा के लिए चलता रहेगा, लेखिका ने ज्यामिति (geometry) का उपयोग किया।

कल्पना कीजिए कि रोबोट की संभावित चालों को ग्राफ पेपर पर खींचा गया है। यह आकार एक पॉलीहेड्रॉन (polyhedron) (एक 3D आकार जिसके सपाट चेहरे होते हैं, या इस 2D मामले में एक बहुभुज/polygon) कहलाता है।
लेखिका ने देखा कि यह आकार किस दिशा में "संकेत" करता है।
- यदि आकार उस दिशा में संकेत करता है जहाँ संख्याएँ बढ़ती जा रही हैं, तो रोबोट हमेशा के लिए चलता रहेगा।
- यदि आकार उस दिशा में संकेत करता है जहाँ संख्याएँ छोटी होती जा रही हैं, तो वह अंततः रुक जाएगा।
चुनौती: यहाँ एक पेचीदा मामला (corner case) है। कभी-कभी आकार इस तरह संकेत करता है जो ऐसा दिखता है कि वह हमेशा के लिए चल सकता है, लेकिन यह इस बात पर निर्भर करता है कि क्या रोबोट उस विशिष्ट "विशेष संख्या" तक पहुँचता है जिसका उल्लेख रीचेबिलिटी कंजेक्चर में किया गया है।
- यदि कंजेक्चर सत्य है, तो रोबोट को अंततः उस विशेष संख्या तक पहुँचना ही होगा और रुकना होगा।
- यदि कंजेचर गलत है, तो रोबोट उसके पास से चुपके से निकल सकता है और हमेशा के लिए चलता रह सकता है।

5. अंतिम निर्णय

शोध पत्र एक सशर्त "हाँ" के साथ समाप्त होता है:

यदि "रीचेबिलिटी कंजेचर" (संख्या पैटर्न के बारे में एक गणितीय अनुमान) सत्य है, तो हमारे पास यह तय करने के लिए एक तेज़, कुशल तरीका है कि ये एक-संख्या वाले प्रोग्राम रुकेंगे या नहीं।
यदि हम कभी यह तय करने का तरीका ढूंढ लेते हैं कि ये प्रोग्राम रुकते हैं या नहीं, तो हम स्वचालित रूप से उस गणितीय अनुमान को सिद्ध (या गलत साबित) कर देंगे।

सारांश

यह शोध पत्र स्वयं प्रसिद्ध कोलात्ज़ पहेली को हल नहीं करता है। इसके बजाय, यह एक अनुवादक के रूप में कार्य करता है। यह कहता है: "एक संख्या वाले रुकने वाले कंप्यूटर प्रोग्रामों की समस्या, संख्या पैटर्न के बारे में एक विशिष्ट अनसुलझी गणितीय पहेली के बिल्कुल समान है।"

यदि गणितज्ञ संख्या वाली पहेली को हल करते हैं, तो कंप्यूटर वैज्ञानिक तुरंत प्रोग्राम-रुकने वाली समस्या को ठीक कर सकते हैं। यदि कंप्यूटर वैज्ञानिक प्रोग्राम की समस्या को ठीक करते हैं, तो गणितज्ञों ने संख्या वाली पहेली को हल कर लिया होगा। जब तक एक पक्ष पहेली को हल नहीं करता, दूसरा पक्ष खुला रहता है।

तकनीकी सारांश: लूप टर्मिनेशन और जनरलाइज्ड कोलात्ज़ सीक्वेंस

समस्या विवरण
यह शोध पत्र पूर्णांकों ( $\mathbb{Z}$ ) पर सिंगल-पाथ लीनियर-कन्स्ट्रेंट लूप्स (SLCs) के लिए टर्मिनेशन समस्या की डैसिडेबिलिटी (decidability) को संबोधित करता है। एक SLC को वर्तमान स्टेट वेरिएबल्स $x$ और अगले स्टेट वेरिएबल्स $x'$ के बीच रैखिक असमिकाओं (linear inequalities) के एक सिस्टम द्वारा परिभाषित किया जाता है:
$\text{while } (Cx \le d) \text{ do } \begin{pmatrix} x \\ x' \end{pmatrix} \le b$
जबकि एफाइन लूप्स (डिटरमिनिस्टिक अपडेट्स) के लिए $\mathbb{Z}, \mathbb{Q},$ और $\mathbb{R}$ पर टर्मिनेशन समस्या डैसिडेबल है, और मल्टी-पाथ लीनियर लूप्स के लिए अनडैसिडेबल है, SLCs (जो कॉनवेक्स नॉन-डिटरमिनिज्म की अनुमति देते हैं) की स्थिति अभी भी खुली (open) है। यह कार्य विशेष रूप से एक-वेरिएबल केस ( $n=1$ ) पर केंद्रित है, जो एक ऐसा प्रतिबंध है जो अपनी स्पष्ट सरलता के बावजूद, अनसुलझे संख्या-सिद्धांत संबंधी अनुमानों (number-theoretic conjectures) से गहराई से जुड़ा हुआ है।

कार्यप्रणाली और दृष्टिकोण
लेखक अनंत ट्रेसेस (infinite traces) की प्रकृति के आधार पर टर्मिनेशन समस्या को दो अलग-अलग उप-समस्याओं में विभाजित करता है:

चक्रीय ट्रेसेस (Cyclic Traces): परिमित अनुक्रम $s_1, \dots, s_k, s_1$ जो दोहराते हैं।
सेल्फ-अवॉइडिंग ट्रेसेस (Self-Avoiding Traces): अनंत अनुक्रम $s_1, s_2, \dots$ जहाँ सभी स्टेट्स विशिष्ट (distinct) होते हैं।

विश्लेषण ट्रांजिशन पॉलीहेड्रॉन $R \subseteq \mathbb{R}^2$ (वैध ट्रांजिशन का सेट) के ज्यामितीय गुणों पर अत्यधिक निर्भर है। पेपर $R$ को वर्टिसेस के कॉनवेक्स हल (convex hull) और एक रिसेसन कोन (recession cone) में विघटित करने के लिए मिंकोव्स्की-वेय्ल प्रमेय (Minkowski-Weyl theorem) का उपयोग करता है। लूप के व्यवहार का विश्लेषण $\mathbb{R}^2$ के विशिष्ट क्षेत्रों (जैसे, वे क्षेत्र जहाँ वेरिएबल का पूर्ण मान बढ़ता है) के सापेक्ष इस रिसेसन कोन की दिशा की जांच करके किया जाता है।

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

1. एक-वेरिएबल लूप्स में साइकिल डिटेक्शन
पेपर एक-वेरिएबल SLCs के लिए साइकिल के संबंध में एक मजबूत संरचनात्मक परिणाम सिद्ध करता है:

प्रमेय: यदि एक एक-वेरिएबल SLC में एक साइकिल मौजूद है, तो उसमें अधिकतम दो लंबाई की साइकिल मौजूद होती है।
निहितार्थ: यह साइकिल डिटेक्शन समस्या को लंबाई 1 या 2 की साइकिलों की जाँच करने तक सीमित कर देता है। चूंकि बाउंडेड साइकिलों की जाँच को इंटीजर लीनियर प्रोग्रामिंग (ILP) में बदला जा सकता है, इसलिए एक-वेरिएबल लूप्स के लिए साइकिल डिटेक्शन डैसिडेबल है।
तुलना: यह परिणाम $n \ge 2$ वेरिएबल्स वाले लूप्स के लिए लागू नहीं होता, जहाँ बिना किसी छोटी साइकिल के भी मनमाने लंबाई के चक्र मौजूद हो सकते हैं।

2. जनरलाइज्ड कोलात्ज़ सीक्वेंस के साथ संबंध
मुख्य योगदान एक-वेरिएबल SLCs की टर्मिनेशन और जनरलाइज्ड कोलात्ज़ सीक्वेंस के रीचेबिलिटी कॉन्जेक्चर (Reachability Conjecture) के बीच एक सटीक समानता स्थापित करना है।

जनरलाइज्ड कोलात्ज़ मैपिंग्स: ये $d$ के रेसिड्यू क्लास (residue class) के आधार पर टुकड़ों में परिभाषित मैप्स $T: \mathbb{Z} \to \mathbb{Z}$ हैं।
वीक कोलात्ज़ मैपिंग्स: एक विशिष्ट उप-वर्ग जहाँ मैप का रूप $T(x) = \lfloor \frac{mx - (a+i)}{d} \rfloor$ होता है।
रीचेबिलिटी कॉन्जेक्चर: यह प्रस्तावित करता है कि किसी भी वीक कोलात्ज़ मैपिंग के लिए, यदि एक सीक्वेंस अनबाउंडेड (unbounded) है, तो उसे अंततः $d$ के एक विशिष्ट रेसिड्यू क्लास (विशेष रूप से, जहाँ $mT^k(n) \equiv a \pmod d$ ) को विजिट करना होगा।
समानता: पेपर सिद्ध करता है कि कोई भी एल्गोरिदम जो एक-वेरिएबल SLCs के लिए टर्मिनेशन को तय करने में सक्षम है, वह विशिष्ट वीक कोलात्ज़ मैपिंग्स के लिए रीचेबिलिटी कॉन्जेक्चर को भी तय कर सकता है। इसके विपरीत, यदि रीचेबिलिटी कॉन्जेक्चर सत्य है, तो एक-वेरिएबल SLCs के लिए टर्मिनेशन डैसिडेबल हो जाता है।

3. मुख्य प्रमेय: कंडीशनल डैसिडेबिलिटी

प्रमेय: यदि रीचेबिलिटी कॉन्जेक्चर सत्य है, तो पूर्णांकों पर एक-वेरिएबल SLCs की टर्मिनेशन पॉलिनोमियल टाइम में डैसिडेबल है।
तंत्र: निर्णय प्रक्रिया में शामिल है:
1. लंबाई $\le 2$ की साइकिलों की जाँच करना (ILP के माध्यम से)।
2. अनबाउंडेड ग्रोथ के क्षेत्रों की ओर संकेत करने वाले ट्रांजिशन पॉलीहेड्रॉन के रिसेसन कोन का विश्लेषण करना।
3. "थिन" (thin) मामलों में, जहाँ रिसेसन कोन एक रेखा या एक एकल किरण (ray) है, विश्लेषण पॉलीहेड्रॉन के इंटीजर स्लाइस की "हाइट" (height) की जाँच करने तक सीमित हो जाता है। यदि हाइट कम है, तो ट्रेस एक वीक कोलात्ज़ सीक्वेंस के अनुरूप होता है। रीचेबिलिटी कॉन्जेक्चर का उपयोग यह निष्कर्ष निकालने के लिए किया जाता है कि ऐसे सीक्वेंस सेल्फ-अवॉइडिंग नहीं हो सकते (अर्थात, वे अंततः एक ऐसे रेसिड्यू क्लास से टकराएंगे जो टर्मिनेशन या साइकिल को मजबूर करता है)।

4. कॉन्जेक्चर पर आंशिक परिणाम

पेपर $d=2$ के मामले में रीचेबिलिटी कॉन्जेक्चर को सिद्ध करता है।
$d > 2$ के लिए, कॉन्जेक्चर अनसुलझा (open) है। पेपर एक उदाहरण प्रदान करता है (एक मैपिंग जिसमें $d=3$ है) जहाँ कॉन्जेक्चर वर्तमान में अनसुलझा है, जो यह दर्शाता है कि SLC टर्मिनेशन पर प्रगति वर्तमान में संख्या-सिद्धांत संबंधी सीमाओं के कारण रुकी हुई है।

महत्व और दावे
यह पेपर एक-वेरिएबल SLC टर्मिनेशन समस्या को पूरी तरह से डैसिडेबल एफाइन लूप्स और अनडैसिडेबल मल्टी-पाथ लूप्स के बीच एक "मिडल ग्राउंड" के रूप में प्रस्तुत करता है।

सैद्धांतिक अंतर्दृष्टि: यह प्रदर्शित करता है कि लूप टर्मिनेशन की कठिनाई केवल प्रोग्राम की जटिलता का मामला नहीं है, बल्कि यह पूर्णांक अनुक्रमों के गहरे संख्या-सिद्धांत संबंधी गुणों से आंतरिक रूप से जुड़ी हुई है।
कंडीशनल रिजल्ट: पेपर बिना कॉन्जेक्चर को माने, अनकंडीशनल टर्मिनेशन समस्या को हल करने का दावा नहीं करता है। इसके बजाय, यह रीचेबिलिटी कॉन्जेक्चर के अधीन एक पॉलिनोमियल-टाइम निर्णय प्रक्रिया प्रदान करता है।
सेमी-एल्गोरिदम: कॉन्जेक्चर को माने बिना, प्रस्तावित विधि एक सेमी-एल्गोरिदम के रूप में कार्य करती है: यह अधिकांश मामलों में टर्मिनेशन या नॉन-टर्मिनेशन को सिद्ध कर सकती है लेकिन "थिन" ट्रेसेस के विशिष्ट उदाहरणों के लिए उत्तर देने में विफल रहती है जो कोलात्ज़ कॉन्जेक्चर के ओपन इंस्टेंस के अनुरूप होते हैं।

संक्षेप में, यह कार्य लूप टर्मिनेशन समस्या को एक विशिष्ट वर्ग के प्रोग्रामों के लिए एक संख्या-सिद्धांत संबंधी समस्या के रूप में पुनर्गठित करता है, और यह सिद्ध करता है कि पूर्व को हल करना विशेष रूप से उत्तरवर्ती (latter) के इंस्टेंस को हल करने के समान है।