🔢 mathematics

A Linear-Size Block-Partition Fibonacci Encoding for Gödel Numbering

यह शोध पत्र एक ब्लॉक-पार्टीशन किए गए फाइबोनैकी अनुक्रम का उपयोग करते हुए परिमित स्ट्रिंग्स (finite strings) को प्राकृतिक संख्याओं में एक रैखिक-आकार (linear-size), आक्षेपित (injective) एन्कोडिंग के माध्यम से प्रस्तुत करता है, जो रोस्को की बाइनरी कैरीलेस पेयरिंग पद्धति में निहित घातीय विस्फोट (exponential blowup) से बचते हुए इष्टतम $\Theta(m)$ वृद्धि प्राप्त करता है।

मूल लेखक: Zoltán Sóstai

प्रकाशित 2026-03-27

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

CC BY 4.0

मूल लेखक: Zoltán Sóstai

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

कल्पना कीजिए कि आपके पास संख्याओं का एक विशाल, अनंत पुस्तकालय है, लेकिन आप अपने द्वारा लिखे गए किसी भी वाक्य (जैसे "Hello World" या कोई जटिल गणितीय सूत्र) को एक एकल, अद्वितीय संख्या में बदलना चाहते हैं। इसे गोडेल नंबरिंग (Gödel numbering) कहा जाता है, जिसका नाम एक प्रसिद्ध तर्कशास्त्री के नाम पर रखा गया है जिन्होंने महसूस किया था कि यदि आप शब्दों को संख्याओं में बदल सकते हैं, तो आप तर्क (logic) का अध्ययन करने के लिए गणित का उपयोग कर सकते हैं।

पुराने तरीकों के साथ समस्या यह है कि संख्याएँ बहुत तेज़ी से विशाल हो जाती हैं। यदि आप एक छोटा सा वाक्य लिखते हैं, तो परिणामी संख्या में सैकड़ों अंक हो सकते हैं। यह एक अक्षर को स्टोर करने के लिए एक शहर के आकार के गोदाम का उपयोग करने जैसा है।

यह शोध पत्र इस बारे में उनके नए, बहुत स्मार्ट तरीके का परिचय देता है जो फाइबोनैची संख्याओं (Fibonacci numbers) (वह अनुक्रम जहाँ प्रत्येक संख्या पिछली दो संख्याओं का योग होती है: 1, 1, 2, 3, 5, 8, 13...) का उपयोग करता है।

यहाँ लेखक के आविष्कार का सरल विवरण दिया गया है:

1. "पुराने तरीके" के साथ समस्या (रोस्को की विधि)

लेखक अपने नए तरीके की तुलना एक शोधकर्ता रोस्को की पुरानी तकनीक से करते हैं।

उपमा (Analogy): कल्पना कीजिए कि आप बक्से पैक कर रहे हैं। रोस्को की विधि दो बक्सों को लेने, उन्हें एक बड़े बक्से के अंदर रखने, फिर उस बड़े बक्से को एक और भी बड़े बक्से के अंदर रखने जैसी है।
परिणाम: हर बार जब आप अपने वाक्य में एक नया अक्षर जोड़ते हैं, तो आपको पूरी चीज़ को एक नए, विशाल कंटेनर के भीतर "नेस्ट" (nest) करना पड़ता है। यदि आपके वाक्य में 10 अक्षर हैं, तो जो संख्या आपको मिलेगी वह ज़रूरत से लगभग $2^{10}$ गुना बड़ी होगी। यदि आपके पास 50 अक्षर हैं, तो संख्या इतनी विशाल होगी कि उसे लिखने के लिए ब्रह्मांड में मौजूद कुल परमाणुओं से भी अधिक परमाणुओं की आवश्यकता होगी। यह एक घातांकीय विस्फोट (exponential explosion) है।

2. नया समाधान: "ब्लॉक पार्टीशनिंग" (Block Partitioning)

लेखक का नया तरीका बक्सों को नेस्ट करने के बजाय एक होटल व्यवस्थित करने जैसा है।

होटल की उपमा:
- कल्पना कीजिए कि अनंत मंजिलों वाला एक होटल है।
- पूरे मेहमानों को एक विशाल कमरे में रखने के बजाय, हम होटल को ब्लॉकों (blocks) में विभाजित करते हैं।
- ब्लॉक 1 आपके वाक्य के पहले अक्षर के लिए है।
- ब्लॉक 2 दूसरे अक्षर के लिए है।
- ब्लॉक 3 तीसरे अक्षर के लिए है।
- जादुई अंतर (The Magic Gap): ब्लॉक 1 और ब्लॉक 2 के बीच, हम एक गैप (gap) (एक खाली गलियारा) छोड़ देते हैं। ब्लॉक 2 और ब्लॉक 3 के बीच, हम एक और गैप छोड़ते हैं।
यह कैसे काम करता है:
- यदि आपका पहला अक्षर "A" है, तो आप ब्लॉक 1 में एक विशिष्ट कमरा चुनते हैं।
- यदि आपका दूसरा अक्षर "B" है, तो आप ब्लॉक 2 में एक विशिष्ट कमरा चुनते हैं।
- क्योंकि ब्लॉकों के बीच गैप है, इसलिए यह गारंटी है कि आपने "A" के लिए जो कमरा चुना है और "B" के लिए जो कमरा चुना है, वे कभी भी एक-दूसरे के बगल में नहीं होंगे।
गैप क्यों महत्वपूर्ण है:
- फाइबोनैची संख्याओं की दुनिया में, एक विशेष नियम (ज़ेकेंडॉर्फ का प्रमेय - Zeckendorf's Theorem) है जो कहता है: यदि आप ऐसी संख्याएँ चुनते हैं जो अनुक्रम में एक-दूसरे के बगल में नहीं हैं, तो एक विशिष्ट कुल योग प्राप्त करने के लिए उन्हें जोड़ने का केवल एक ही तरीका होता है।
- क्योंकि हमारे "गैप" यह सुनिश्चित करते हैं कि कमरे पड़ोसी न हों, इसलिए कमरों के नंबरों का योग एक अद्वितीय कोड बनाता है। कोई भी दो अलग-अलग वाक्य कभी भी एक ही कुल संख्या परिणाम के रूप में नहीं दे सकते।

3. परिणाम: रैखिक वृद्धि (Linear Growth)

यह सबसे बड़ी जीत है।

पुराना तरीका (रोस्को): एक अक्षर जोड़ने से संख्या का आकार दोगुना हो जाता है। (घातांकीय वृद्धि)।
नया तरीका (ब्लॉक पार्टीशन): एक अक्षर जोड़ने से संख्या में बस एक निश्चित, छोटा सा "स्थान" जुड़ जाता है।
- यदि 1-अक्षर वाला शब्द 2-अंकों की संख्या बनाता है, तो 10-अक्षर वाला शब्द 20-अंकों की संख्या बनाएगा।
- यदि 100-अक्षर वाला शब्द 200-अंकों की संख्या बनाता है।
- यह रैखिक (linearly) रूप से बढ़ता है। यह एक दीवार में हर नए अक्षर के लिए एक ईंट जोड़ने जैसा है, न कि पूरी दीवार को दोगुना बड़ा बनाने के लिए उसे फिर से बनाने जैसा।

4. यह क्यों मायने रखता है

लेखक यह सिद्ध करते हैं कि यह तरीका सैद्धांतिक रूप से जितना संभव है, उतना ही कुशल है। आप किसी अन्य आधार प्रणाली (जैसे मानक बाइनरी) का उपयोग किए बिना इससे बेहतर कुछ नहीं कर सकते, लेकिन चूंकि यह फाइबोनैची संख्याओं का उपयोग करता है, इसलिए इसमें विशेष गणितीय गुण हैं जो बाद में उन्नत तर्क और कंप्यूटर विज्ञान के लिए उपयोगी हो सकते हैं।

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

यहाँ ज़ोल्टान स्टोस्टई (Zoltán Sóstai) के शोध पत्र "A LINEAR-SIZE BLOCK-PARTITION FIBONACCI ENCODING FOR GÖDEL NUMBERING" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र गोडेल नंबरिंग (Gödel numbering) की समस्या को संबोधित करता है: एक निश्चित वर्णमाला $\Sigma$ पर परिमित स्ट्रिंग्स (जैसे सूत्र या प्रमाण जैसे सिंटैक्टिक ऑब्जेक्ट्स) का प्राकृतिक संख्याओं में इंजेक्टिव मैपिंग (injective mapping)।

संदर्भ: गोडेल के अपूर्णता के प्रमेय (incompleteness theorems) ऐसे ही एनकोडिंग पर आधारित हैं। पारंपरिक विधियाँ, जैसे कि प्राइम-पावर एनकोडिंग ( $2^{a_1+1} \cdot 3^{a_2+1} \cdots$ ), ऐसे नंबर उत्पन्न करती हैं जिनका विकास सुपर-लीनियर (super-linear) होता है (अक्सर छोटे स्ट्रिंग्स के लिए भी सैकड़ों अंक), जिससे वे गणनात्मक रूप से बोझिल हो जाते हैं।
मौजूदा विकल्प: रोस्को (Rosko, 2025) ने "कैरिलैस पेयरिंग" (carryless pairing) फंक्शन के साथ ज़ेकेन्डॉर्फ प्रतिनिधित्व (non-consecutive Fibonacci संख्याओं का योग) का उपयोग करने का प्रस्ताव दिया था। हालाँकि, यह शोध पत्र इस पद्धति के मानक अनुप्रयोग में एक महत्वपूर्ण दोष की पहचान करता है: अनुक्रमों (sequences) के लिए "राइट-नेस्टिंग" (right-nesting) बाइनरी पेयरिंग करने से अंकों की संख्या में घातीय (exponential) वृद्धि ( $\Theta(2^m)$ ) होती है, जो अक्षम है।
लक्ष्य: एक ऐसा एनकोडिंग बनाना जो इंजेक्टिव हो, जिसकी लंबाई को पुनः प्राप्त (recover) किया जा सके, और जो स्ट्रिंग की लंबाई $m$ के सापेक्ष अंकों के विकास को लीनियर ( $\Theta(m)$ ) बनाए रखे, जो एक स्थिरांक कारक (constant factor) तक सूचना-सैद्धांतिक निचली सीमा (information-theoretic lower bound) से मेल खाता हो।

2. कार्यप्रणाली: ब्लॉक-पार्टिशन एनकोडिंग (Methodology: Block-Partition Encoding)

लेखक अंतराल (gaps) द्वारा अलग किए गए निरंतर ब्लॉकों में फाइबोनैची अनुक्रम को विभाजित करने पर आधारित एक नवीन निर्माण प्रस्तावित करते हैं।

मुख्य परिभाषाएँ

वर्णमाला (Alphabet): एक परिमित वर्णमाला $\Sigma = \{\sigma_0, \dots, \sigma_{k-1}\}$ जिसमें प्रतीक कोड $c \in \{0, \dots, k-1\}$ हैं।
ब्लॉक का आकार (Block Size): $\beta = k + 1$ के रूप में परिभाषित है।
ब्लॉक विभाजन (Block Partition): फाइबोनैची अनुक्रम के इंडेक्स को प्रत्येक स्ट्रिंग स्थिति $i \ge 0$ $i \geq 0$ के लिए ब्लॉकों $B_i$ $B_{i}$ में विभाजित किया गया है।
- ब्लॉक $B_i$ में शामिल इंडेक्स हैं: $\{2 + i\beta, 2 + i\beta + 1, \dots, 2 + i\beta + (k-1)\}$ ।
- अंतराल (Gap): इंडेक्स $2 + i\beta + k$ का उपयोग नहीं किया जाता है। यह अंतराल यह सुनिश्चित करता है कि ब्लॉक $B_i$ का सबसे बड़ा इंडेक्स और $B_{i+1}$ का सबसे छोटा इंडेक्स कम से कम 2 इंडेक्स से अलग हों।
एनकोडिंग नियम: स्ट्रिंग $s = s_1 \dots s_m$ के लिए जिसके प्रतीक कोड $c_1, \dots, c_m$ हैं:
$\ulcorner s \urcorner = \sum_{i=0}^{m-1} F_{2 + i\beta + c_{i+1}}$
प्रत्येक स्थिति $i$ पर स्थित प्रतीक अपने समर्पित ब्लॉक $B_i$ से ठीक एक फाइबोनैची संख्या चुनता है।

सैद्धांतिक आधार

यह एनकोडिंग ज़ेकेन्डॉर्फ के प्रमेय (Zeckendorf's Theorem) पर आधारित है, जो कहता है कि प्रत्येक धनात्मक पूर्णांक का एक अद्वितीय प्रतिनिधित्व गैर-सन्निकट (non-consecutive) फाइबोनैची संख्याओं के योग के रूप में होता है।

गैर-निकटता (Non-Adjacency): निर्माण यह सुनिश्चित करता है कि चयनित इंडेक्स कभी भी लगातार (consecutive) नहीं होते। ब्लॉक के भीतर, केवल एक इंडेक्स चुना जाता है। ब्लॉकों के बीच, अंतराल कम से कम 2 का अलगाव सुनिश्चित करता है।
विशिष्टता (Uniqueness): क्योंकि गैर-सन्निकट फाइबोनैची संख्याओं का योग अद्वितीय होता है (ज़ेकेन्डॉर्फ प्रमेय के अनुसार), परिणामी योग चुनी गई इंडेक्स के सेट को और इस प्रकार मूल स्ट्रिंग को विशिष्ट रूप से निर्धारित करता है।

3. मुख्य योगदान (Key Contributions)

लीनियर-साइज़ निर्माण: यह शोध पत्र ज़ेकेन्डॉर्फ-आधारित एनकोडिंग का पहला निर्माण प्रस्तुत करता है जो अनुक्रम एनकोडिंग के लिए लीनियर डिजिट ग्रोथ ( $\Theta(m)$ ) प्राप्त करता है, जो नेस्टेड पेयरिंग विधियों के घातीय विस्तार (exponential blowup) से बचता है।
इंजेक्टिविटी और डिकोडेबिलिटी:
- इंजेक्टिविटी (Injectivity): ज़ेकेन्डॉर्फ प्रतिनिधित्व की विशिष्टता के माध्यम से सिद्ध की गई है। भिन्न स्ट्रिंग्स भिन्न योगों में मैप होती हैं।
- लंबाई की पुनः प्राप्ति (Length Recovery): मूल स्ट्रिंग की लंबाई $m$ को कोड $n$ में पदों की संख्या गिनकर ( $|Z(n)| = m$ ) सीधे प्राप्त किया जा सकता है।
- डिकोडिंग (Decoding): एक ग्रीडी एल्गोरिदम (greedy algorithm) योग में प्रत्येक पद के ब्लॉक इंडेक्स और प्रतीक कोड की पहचान करके स्ट्रिंग को पुनर्गठित कर सकता है।
जटिलता विश्लेषण (Complexity Analysis):
- कोड की लंबाई: अंकों की संख्या $\Theta(m)$ के रूप में बढ़ती है। विशेष रूप से, 10-प्रतीक वाली वर्णमाला के लिए, ओवरहेड प्रति प्रतीक लगभग 2.3 अंक है।
- इष्टतमता (Optimality): निर्माण एक स्थिरांक कारक तक सूचना-सैद्धांतिक निचली सीमा ( $\Omega(m)$ ) से मेल खाते हुए स्पर्शोन्मुखी रूप से (asymptotically) इष्टतम है।
नेस्टेड पेयरिंग की आलोचना: यह शोध पत्र कठोरता से सिद्ध करता है कि रोस्को की राइट-नेस्टेड कैरीलेस पेयरिंग का स्वाभाविक अनुप्रयोग $\Theta(2^m)$ अंकों का विकास करता है, जो दर्शाता है कि ब्लॉक-पार्टिशन दृष्टिकोण क्यों श्रेष्ठ है।

4. परिणाम (Results)

प्रमेय 5.1 (लीनियर कोड लेंथ): लंबाई $m$ की किसी भी स्ट्रिंग के लिए, वर्स्ट-केस डिजिट काउंट $\Theta(m)$ है।
प्रमेय 5.2 (स्पर्शोन्मुखी इष्टतमता): एनकोडिंग एक स्थिरांक कारक तक इष्टतम है। $k=10$ के लिए, स्थिरांक कारक सैद्धांतिक न्यूनतम की तुलना में लगभग 2.3 है।
प्रपोजिशन 5.3 (घातीय विस्तार): राइट-नेस्टेड कैरीलेस पेयरिंग $\Theta(2^m)$ $Θ (2^{m})$ अंकों वाले कोड प्रदान करती है।
- उदाहरण: ब्लॉक पार्टीशन के माध्यम से एनकोड की गई लंबाई-5 की स्ट्रिंग अधिकतम फाइबोनैची इंडेक्स 55 का उपयोग करती है। नेस्टेड पेयरिंग के माध्यम से उसी स्ट्रिंग के लिए इंडेक्स 245 का उपयोग किया जाता है, जो तीव्र विचलन को दर्शाता है।
तुलना: शोध पत्र चार विधियों की तुलना करता है:
- प्राइम-पावर (गोडेल): सुपर-लीनियर।
- बेस-k पोजीशनल: लीनियर (इष्टतम स्थिरांक)।
- राइट-नेस्टेड कैरीलेस पेयरिंग (रोस्को): घातीय ( $\Theta(2^m)$ )।
- ब्लॉक पार्टीशन (यह शोध पत्र): लीनियर ( $\Theta(m)$ )।

5. महत्व (Significance)

दक्षता: यह एनकोडिंग प्राइम-पावर गोडेल नंबरिंग का एक व्यावहारिक, संक्षिप्त विकल्प प्रदान करती है, जो सिंटैक्टिक ऑब्जेक्ट्स को दर्शाने के लिए आवश्यक संख्याओं के परिमाण को काफी कम कर देती है।
सैद्धांतिक अंतर्दृष्टि: यह "कैरiless पेयरिंग" की सीमाओं को स्पष्ट करता है, यह दिखाते हुए कि जबकि यह जोड़ों (pairs) के लिए उपयोगी है, नेइव नेस्टिंग अनुक्रम एनकोडिंग के लिए घातीय अक्षमता की ओर ले जाती है।
भावी अनुप्रयोग: इस एनकोडिंग की योगात्मक प्रकृति (स्वतंत्र पदों का योग) सीमित अंकगणित (bounded arithmetic) और गुणा के बिना प्रणालियों में संभावित उपयोग का सुझाव देती है, जो संभावित रूप से कमजोर तार्किक प्रणालियों में सिंटैक्टिक प्रेडिकेट्स ( $\Delta_0$ -definability) या अपूर्णता प्रमाणों को परिभाषित करने में सहायता कर सकती है।
विभेद: लेखक इसे डेटा संपीड़न (data compression) में उपयोग किए जाने वाले मानक "फाइबोनैची कोडिंग" से स्पष्ट रूप से अलग करते हैं, यह नोट करते हुए कि हालांकि दोनों ज़ेकेन्डॉर्फ प्रतिनिधित्व का उपयोग करते हैं, यह विधि पूर्णांकों को बाइनरी स्ट्रिंग्स के रूप में नहीं, बल्कि स्ट्रिंग्स को एकल संख्या के रूप में एनकोड करती है।

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