🔢 mathematics

Additive systems for $\mathbb{Z}$ are undecidable

यह शोध पत्र यह प्रदर्शित करता है कि $\mathbb{Z}$ के उपसमुच्चयों के एक मानक संग्रह के योगसमूह (sumset) द्वारा संपूर्ण पूर्णांकों को कवर करने का निर्धारण करना अनिर्णायक (undecidable) है, क्योंकि इस समस्या को फ्रैक्ट्रान (Fractran) के सार्वभौमिक रुकने की समस्या (universal halting problem) के समकक्ष दिखाया गया है और यह कोलात्ज़ अनुमान (Collatz conjecture) से जुड़ा हुआ है।

मूल लेखक: Andrei Zabolotskii

प्रकाशित 2026-04-01

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

CC BY 4.0

मूल लेखक: Andrei Zabolotskii

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

मुख्य विचार: LEGO की तरह नंबर बनाना

कल्पना कीजिए कि आपके पास LEGO ब्रिक्स का एक विशाल, अनंत डिब्बा है। लेकिन ये केवल साधारण ब्रिक्स नहीं हैं; ये विशिष्ट प्रकारों या परतों (layers) में व्यवस्थित हैं।

लेयर 0 में छोटे ब्रिक्स हैं (जैसे 0, 1, 2)।
लेयर 1 में मध्यम आकार के ब्रिक्स हैं (जैसे 0, 10, 20)।
लेयर 2 में बड़े ब्रिक्स हैं (जैसे 0, 100, 200)।

लक्ष्य: क्या आप प्रत्येक परत से ठीक एक ब्रिक का उपयोग करके कोई भी पूर्णांक (positive, negative, या zero) बना सकते हैं?

यदि आप संख्या 538 बना सकते हैं, तो आप लेयर 2 से एक "500" का ब्रिक, लेयर 1 से एक "30" का ब्रिक, और लेयर 0 से एक "8" का ब्रिक चुन सकते हैं।
नियम सख्त है: आपको हर लेयर से ठीक एक ब्रिक का उपयोग करना होगा, और योग अद्वितीय होना चाहिए। आप संख्या 538 को दो अलग-अलग तरीकों से नहीं बना सकते।

गणित में, इसे एडिटिव सिस्टम (Additive System) कहा जाता है।

भाग 1: आसान मामला (धनात्मक संख्याएं)

लंबे समय से, गणितज्ञों को पता था कि इसे केवल धनात्मक संख्याओं (0, 1, 2, 3...) के लिए कैसे हल किया जाए।

उपमा: एक मानक दशमलव प्रणाली (बेस 10) के बारे में सोचें।
- लेयर 0: अंक 0–9।
- लेयर 1: 10 के गुणज (0, 10, 20...)।
- लेयर 2: 100 के गुणज।
यह पूरी तरह से काम करता है। प्रत्येक धनात्मक संख्या के पास ब्रिक्स की एक सटीक "रेसिपी" होती है। प्रसिद्ध गणितज्ञ डी ब्रुइन (de Bruijn) ने पता लगाया था कि ये "परफेक्ट रेसिपी" वास्तव में कैसी दिखती हैं।

भाग 2: कठिन मामला (सभी पूर्णांक)

यह शोध पत्र पूछता है: क्या होगा यदि हम ऋणात्मक संख्याओं (..., -3, -2, -1, 0, 1, 2, 3...) को भी बनाना चाहें?

समस्या: यह बहुत कठिन है। आप केवल धनात्मक ब्रिक्स का उपयोग नहीं कर सकते। आपको "ऋणात्मक ब्रिक्स" या धनात्मक और ऋणात्मक का एक अजीब मिश्रण की आवश्यकता होगी।
"कैनोनिकल कलेक्शन" (The Canonical Collection): लेखक इन परतों को व्यवस्थित करने का एक नया, संरचित तरीका आविष्कार करते हैं। वे इन्हें कैनोनिकल कलेक्शंस कहते हैं। इन्हें अपने LEGO लेयर्स को व्यवस्थित करने के लिए विशिष्ट निर्देशों के सेट के रूप में समझें ताकि वे शायद प्रत्येक पूर्णांक को कवर कर सकें।

मोड़: यह "क्या यह रुकेगा?" का खेल है

लेखक को एहसास होता है कि यह जांचना कि एक कैनोनिकल कलेक्शन काम करता है या नहीं (यानी, क्या यह हर पूर्णांक बना सकता है?), वास्तव में "क्या यह प्रक्रिया अंततः रुकेगी?" खेलने के समान है।

वह गणित की समस्या को एक डायनामिकल सिस्टम (Dynamical System) (एक मशीन जो चलती रहती है) में बदल देते हैं।

मशीन: आप एक संख्या से शुरू करते हैं। आप उस पर एक नियम लागू करते हैं। आपको एक नई संख्या मिलती है। आप नियम को फिर से लागू करते हैं।
प्रश्न: क्या यह मशीन अंततः शून्य (Zero) तक पहुँचकर रुक जाती है?
- यदि मशीन हर शुरुआती संख्या के लिए शून्य तक पहुँचती है, तो आपका LEGO कलेक्शन परफेक्ट है (यह एक एडिटिव सिस्टम है)।
- यदि मशीन किसी एक संख्या के लिए भी लूप में फंस जाती है या अनंत काल तक चलती रहती है, तो आपका कलेक्शन टूटा हुआ है।

चौंकाने वाले संबंध

यहीं पर यह पेपर रोमांचक हो जाता है। लेखक सिद्ध करते हैं कि इन LEGO कलेक्शंस के काम करने का निर्णय लेना, गणित और कंप्यूटर विज्ञान की कुछ सबसे प्रसिद्ध, अनसुलझी पहेलियों को हल करने के बराबर है।

1. कोलात्ज़ अनुमान (Collatz Conjecture - 3n+1 की समस्या)

आपने इसके बारे में सुना होगा। यह एक सरल नियम है:

यदि संख्या सम (even) है, तो 2 से विभाजित करें।
यदि संख्या विषम (odd) है, तो 3 से गुणा करें और 1 जोड़ें।
दोहराते रहें।
रहस्य: क्या यह हमेशा अंततः 1 तक पहुँचता है? कोई नहीं जानता। इसे ट्रिलियनों संख्याओं के लिए परखा गया है, लेकिन इसके पास कोई प्रमाण नहीं है।

पेपर की खोज: लेखक ने एक विशिष्ट LEGO कलेक्शन बनाया जहाँ यह प्रश्न "क्या यह कलेक्शन काम करता है?" बिल्कुल वही है जो यह पूछना है कि "क्या कोलात्ज़ अनुमान सत्य है?"

यदि आप LEGO समस्या को हल कर सकते, तो आप कोलात्ज़ को हल कर लेते।
यदि आप कोलात्ज़ को हल कर सकते, तो आप जान जाते कि यह LEGO कलेक्शन काम करता है या नहीं।

2. हैल्टिंग प्रॉब्लम (The Halting Problem - "रुकें या चलें" की समस्या)

यह कंप्यूटर विज्ञान की एक अवधारणा है। कल्पना कीजिए कि आपके पास एक कंप्यूटर प्रोग्राम है। क्या आप एक मास्टर प्रोग्राम लिख सकते हैं जो किसी भी अन्य प्रोग्राम को देखकर आपको बता सके कि: "क्या यह प्रोग्राम अंततः रुक जाएगा, या यह अनंत काल तक चलता रहेगा?"

उत्तर: नहीं। यह गणितीय रूप से अनिर्णीत (undecidable) है। ऐसा कोई एल्गोरिदम नहीं है जो हर प्रोग्राम के लिए इस सवाल को हल कर सके।

पेपर की खोज: लेखक ने फ्रैक्ट्रन (Fractran) नामक एक अजीब प्रोग्रामिंग भाषा पर आधारित एक विशेष LEGO कलेक्शन बनाया।

उन्होंने सिद्ध किया: "क्या यह फ्रैक्ट्रन-आधारित LEGO कलेक्शन काम करता है?" यह पूछने के समान है कि "क्या यह फ्रैक्ट्रन प्रोग्राम हर इनपुट के लिए रुकता है?"
चूंकि हम जानते हैं कि सभी प्रोग्रामों के लिए "रुकें या चलें" वाला सवाल हल करना असंभव है, इसका मतलब है कि यह तय करना असंभव है कि ये LEGO कलेक्शंस काम करेंगे या नहीं।

निष्कर्ष: यह क्यों मायने रखता है

पेपर निष्कर्ष निकालता है कि इन विशिष्ट प्रकार के नंबर सिस्टम के लिए, कोई सामान्य नियम या एल्गोरिदम नहीं है जो आपको बता सके कि वे सभी पूर्णांकों को कवर करते हैं।

रूपक (Metaphor): कल्पना कीजिए कि आपके पास LEGO का एक डिब्बा है। कभी-कभी आप डिब्बे को देखकर कह सकते हैं, "हाँ, यह सब कुछ बनाता है।" लेकिन इस विशिष्ट, जटिल प्रकार के डिब्बे के लिए, यह प्रश्न "क्या यह सब कुछ बनाता है?" कोलात्ज़ रहस्य को हल करने या यह भविष्यवाणी करने जितना ही कठिन है कि कोई कंप्यूटर प्रोग्राम क्रैश होगा या नहीं।
मुख्य बात: गणित केवल उत्तर खोजने के बारे में नहीं है; कभी-कभी, प्रश्न स्वयं ही अनसुलझाने योग्य होता है। लेखक ने दिखाया कि संख्याओं की संरचना इतनी गहरी और जटिल है कि इसमें कंप्यूटिंग और संख्या सिद्धांत की सबसे कठिन समस्याओं के समान कठिनाई छिपी हुई है।

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

यहाँ अंद्रेई ज़बोलोत्स्की के शोध पत्र "Additive systems for $\mathbb{Z}$ are undecidable" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र पूर्णांकों ( $\mathbb{Z}$ ) के लिए एडिटिव सिस्टम्स (additive systems) के लक्षण वर्णन की मौलिक समस्या को संबोधित करता है।

परिभाषा: एक मोनॉइड $M$ के लिए एडिटिव सिस्टम, समुच्चयों का एक संग्रह $\mathcal{A} = \{A_0, A_1, \dots\}$ है, जहाँ प्रत्येक तत्व $n \in M$ को एक अद्वितीय परिमित योग $n = a_0 + a_1 + \dots$ के रूप में दर्शाया जा सकता है, जहाँ $a_i \in A_i$ है।
संदर्भ: गैर-ऋणात्मक पूर्णांकों ( $\mathbb{N}_0$ ) के लिए, ये सिस्टम्स डी ब्रुइन के प्रमेय (de Bruijn's Theorem) द्वारा पूरी तरह से अभिलक्षित हैं, जो यह बताता है कि $\mathbb{N}_0$ के लिए कोई भी एडिटिव सिस्टम एक "ब्रिटिश नंबर सिस्टम" (परिवर्तित आधारों वाला एक सिस्टम) का संकुचन (contraction) होता है।
अंतराल (The Gap): $\mathbb{Z}$ (सभी धनात्मक और ऋणात्मक पूर्णांकों का प्रतिनिधित्व करने के लिए) के लिए समरूप समस्या काफी कठिन है। हालाँकि विशिष्ट उदाहरण मौजूद हैं (जैसे नेगाबाइनरी या बैलेंस्ड टेनरी सिस्टम), लेकिन कोई सामान्य संरचनात्मक लक्षण वर्णन उपलब्ध नहीं है। केंद्रीय प्रश्न यह है: किसी विशिष्ट संग्रहों के समूह को देखते हुए, क्या वह $\mathbb{Z}$ के लिए एक एडिटिव सिस्टम है? (अर्थात, क्या उसका डायरेक्ट समसेट पूरे पूर्णांक सेट को कवर करता है?)

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

लेखक एडिटिव कॉम्बिनेटरिक्स, डायनेमिकल सिस्टम्स और कंप्यूटेबिलिटी थ्योरी को संयोजित करने वाली एक बहु-चरणीय कार्यप्रणाली का उपयोग करता है:

A. कैनोनिकल कलेक्शंस (Canonical Collections) का परिचय

ज्ञात उदाहरणों (जैसे नेगाबाइनरी और बैलेंस्ड टेनरी सिस्टम) को सामान्य बनाने के लिए, लेखक कैनोनिकल कलेक्शंस को परिभाषित करता है।

संरचना: एक संग्रह जिसे आधारों के अनुक्रम $(b_i)_{i \in \mathbb{N}_0}$ (जहाँ $b_i > 1$ ) और समुच्चयों के अनुक्रम $(T_i)_{i \in \mathbb{N}_0}$ द्वारा परिभाषित किया जाता है, जहाँ प्रत्येक $T_i$ , $b_i$ के सापेक्ष एक पूर्ण अवशेष तंत्र (complete residue system) है जिसमें 0 शामिल है।
निर्माण: संग्रह में सेट $A_i = (b_0 b_1 \dots b_{i-1}) T_i$ हैं।
गुण: किसी भी कैनोनिकल कलेक्शन का समसेट (sumset) हमेशा डायरेक्ट (यदि योग मौजूद है तो अद्वितीय प्रतिनिधित्व मौजूद है) होता है, लेकिन यह गारंटी नहीं है कि यह पूर्ण (पूरे $\mathbb{Z}$ को कवर करना) होगा।

B. डायनेमिकल सिस्टम्स में अनुवाद

मुख्य कार्यप्रणालीगत बदलाव एडिटिव समस्या को एक नॉन-ऑटोनॉमस डायनेमिकल सिस्टम में अनुवादित करना है।

मैप (The Map): दिए गए पूर्णांक $n$ के लिए, लेखक मैप्स का एक अनुक्रम $f_i: \mathbb{Z} \to \mathbb{Z}$ परिभाषित करता है:
$f_i(n) = \frac{n - t_i(n)}{b_i}$
जहाँ $t_i(n)$ , $T_i$ का वह अद्वितीय तत्व है जो $n \pmod{b_i}$ के अनुरूप है।
ट्रैजेक्टरी (Trajectory): $n$ का "विस्तार" (expansion) ट्रैजेक्टरी $n, f_0(n), f_1(f_0(n)), \dots$ के अनुरूप होता है।
तुल्यता: एक कैनोनिकल कलेक्शन पूर्ण ( $\mathbb{Z}$ के लिए एक एडिटिव सिस्टम) है यदि और केवल यदि प्रत्येक पूर्णांक $n \in \mathbb{Z}$ की ट्रैजेक्टरी अंततः 0 तक पहुँचती है और वहीं रहती है।

C. अनिर्णय योग्य समस्याओं (Undecidable Problems) में न्यूनीकरण

लेखक विशिष्ट कैनोनिकल कलेक्शंस का निर्माण करता है जहाँ "ट्रैजेक्टरी 0 तक पहुँचना" की स्थिति गणितीय रूप से प्रसिद्ध अनसुलझी या अनिर्णय योग्य समस्याओं के समान है:

कोलात्ज़ अनुमान (Collatz Conjecture): एक ऐसा संग्रह बनाना जहाँ ट्रैजेक्टरी $3n+1$ मैप की नकल करती है।
फ्रैक्ट्रान हैल्टिंग प्रॉब्लम (Fractran Halting Problem): एक ऐसा संग्रह बनाना जहाँ ट्रैजेक्टरी एक फ्रैक्ट्रान प्रोग्राम (एक ट्यूरिंग-पूर्ण ए senseoteric प्रोग्रामिंग भाषा) के निष्पादन की नकल करती है।

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

प्रमेय 1: कोलात्ज़ अनुमान के साथ तुल्यता

लेखक एक विशिष्ट कैनोनिकल कलेक्शन $\mathcal{A}_C$ का निर्माण करता है ताकि:

$\mathcal{A}_C$ , $\mathbb{Z}$ के लिए एक एडिटिव सिस्टम है यदि और केवल यदि कोलात्ज़ अनुमान सत्य है।
तंत्र: आधार $b_i$ और अवशेष सेट $T_i$ इस प्रकार चुने जाते हैं कि डायनेमिकल सिस्टम $f_i$ , धनात्मक पूर्णांकों के लिए कोलात्ज़ फंक्शन ($odd $के लिए$ 3n+1$, $even $के लिए$ n/2$) को दोहराता है। प्रमाण यह दर्शाता है कि कोई भी पूर्णांक ट्रैजेक्टरी के "कोलात्ज़ रिजीम" में अंततः प्रवेश करता है।

प्रमेय 2: यूनिवर्सल हैल्टिंग प्रॉब्लम के साथ तुल्यता

लेखक एक फ्रैक्ट्रान प्रोग्राम $F$ पर आधारित फ्रैक्ट्रान-प्रकार के कैनोनिकल कलेक्शंस को परिभाषित करता है।

परिणाम: एक फ्रैक्ट्रान प्रोग्राम $F$ सभी इनपुट के लिए रुकता (halts) है यदि और केवल यदि संगत कैनोनिकल कलेक्शन $\mathcal{A}_F$ पूर्ण है।
महत्व: चूंकि फ्रैक्ट्रान के लिए यूनिवर्सल हैल्टिंग प्रॉब्लम अनिर्णय योग्य है (कोई एल्गोरिदम यह निर्धारित नहीं कर सकता कि कोई भी मनमाना प्रोग्राम सभी इनपुट पर रुकता है या नहीं), इसलिए इस प्रकार के कैनोनिकल कलेक्शंस के लिए पूर्णता (completeness) निर्धारित करने की समस्या भी अनिर्णय योग्य है।

कोरोलरी 2: अनिर्णयता (Undecidability)

यह तय करना कि क्या दिया गया फ्रैक्ट्रान-प्रकार का कैनोनिकल कलेक्शन $\mathbb{Z}$ के लिए एक एडिटिव सिस्टम है, अनिर्णय योग्य (undecidable) है।

इसका तात्पर्य यह है कि कोई सामान्य एल्गोरिदम नहीं है जो यह निर्धारित कर सके कि एक "सुव्यवस्थित" (सीमित डेटा विवरण वाला) एडिटिव सिस्टम $\mathbb{Z}$ को कवर करता है या नहीं।

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

एक लंबे समय से खुले रहे प्रश्न का समाधान: यह शोध पत्र $\mathbb{Z}$ के लिए एडिटिव सिस्टम्स की संरचनात्मक जटिलता का एक निश्चित उत्तर प्रदान करता है। $\mathbb{N}_0$ के विपरीत, जिसका एक स्पष्ट लक्षण वर्णन है (डी ब्रुइन का प्रमेय), $\mathbb{Z}$ के मामले को कम्प्यूटेशनल रूप से कठिन (intractable) दिखाया गया है।
क्षेत्रों का मिलन: यह एडिटिव कॉम्बिनेटरिक्स (टाइलिंग और समसेट्स), डायनेमिकल सिस्टम्स (ट्रैजेक्टरी कन्वर्जेंस), और कंप्यूटेबिलिटी थ्योरी (अनिर्णयता) के बीच एक गहरा संबंध स्थापित करता है।
सत्यापन की कठिनाई (Hardness of Verification): परिणाम बताते हैं कि यह सत्यापित करना कि क्या विशिष्ट नियम सभी पूर्णांकों के लिए एक अद्वितीय प्रतिनिधित्व उत्पन्न करते है, कोलात्ज़ अनुमान या हैल्टिंग प्रॉब्लम को हल करने जितना ही कठिन है। यह समझाता है कि $\mathbb{Z}$ के लिए डी ब्रुइन के प्रमेय के समान कोई सामान्य लक्षण वर्णन प्रमेय क्यों मौजूद नहीं है।
संख्या प्रणालियों पर नया दृष्टिकोण: संख्या प्रणालियों को डायनेमिकल ट्रैजेक्टरीज के रूप में फ्रेम करके, यह शोध पत्र गैर-मानक संख्या प्रणालियों के कन्वर्जेंस और कवरेज गुणों का विश्लेषण करने के लिए एक नया उपकरण प्रदान करता है।

निष्कर्ष (Conclusion)

ज़बोलोत्स्की यह प्रदर्शित करते हैं कि "क्या यह संग्रह $\mathbb{Z}$ के लिए एक एडिटिव सिस्टम है?" यह प्रश्न न केवल कठिन है, बल्कि कलेक्शंस के एक स्वाभाविक, सुव्यवस्थित परिवार के लिए अनिर्णय योग्य (undecidable) है। कोलात्ज़ अनुमान और फ्रैक्ट्रान प्रोग्राम्स के तर्क को इन एडिटिव सिस्टम्स की संरचना में समाहित करके, यह शोध पत्र सिद्ध करता है कि ऐसे सिस्टम्स की पूर्णता गणित और कंप्यूटर विज्ञान की कुछ सबसे कठिन समस्याओं से अटूट रूप से जुड़ी हुई है।