🔢 mathematics

State Complexity of Shifts of the Fibonacci Word

यह शोध पत्र प्रदर्शित करता है कि शिफ्टेड फाइबोनैची शब्दों (shifted Fibonacci words) को उत्पन्न करने वाले ऑटोमेटा की स्टेट कॉम्प्लेक्सिटी (state complexity), चाहे वे ज़ेकेन्डोर्फ प्रतिनिधित्व (Zeckendorf representation) को मोस्ट-सिग्निफिकेंट-डिजिट-फर्स्ट या लीस्ट-सिग्निफिकेंट-डिजिट-फर्स्ट क्रम में प्रोसेस कर रहे हों, शिफ्ट राशि $c$ के साथ लघुगणकीय (logarithmically) रूप से बढ़ती है, जो एपीरियॉडिक अनुक्रमों (aperiodic sequences) के लिए सूचना-सैद्धांतिक न्यूनतम (information-theoretic minimum) के करीब पहुँचती है।

मूल लेखक: Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

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

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

CC BY 4.0

मूल लेखक: Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

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

कल्पना कीजिए कि आपके पास काले या सफेद रंग के मोतियों की एक जादुई, अनंत टेप है। यह कोई रैंडम पैटर्न नहीं है; यह फाइबोनैची वर्ड (Fibonacci Word) है, जो गणित में इतना प्रसिद्ध है कि यह स्ट्रिंग्स का "गोल्डन रेशियो" जैसा है। यह कुछ ऐसा दिखता है: काला, सफेद, काला, काला, सफेद, काला, सफेद, काला... और यह बिना कभी भी एक ही हिस्से को दोहराए अनंत काल तक चलता रहता है।

गणितज्ञ इस टेप को बहुत पसंद करते हैं क्योंकि इसे केवल 5 छोटे गियर्स (states) वाले एक ऑटोमेटन (एक साधारण मशीन) द्वारा बनाया जाता है। यदि आप मशीन को बताते हैं "100वाँ मोती क्या है?", तो वह संख्या को प्रोसेस करती है और तुरंत उत्तर दे देती है।

समस्या: "शिफ्ट" (The Shift)

अब, कल्पना कीजिए कि आप टेप को देख रहे हैं, लेकिन आप उसे कुछ स्थानों तक खिसका देते हैं। शायद आप उस मोती को देखना चाहते हैं जो मूल रूप से स्थिति 100 पर था, लेकिन अब आप जानना चाहते हैं कि स्थिति 105 पर क्या है। आपने अनुक्रम (sequence) को 5 स्थानों से "शिफ्ट" कर दिया है।

बड़ा सवाल यह है कि: इस शिफ्ट को संभालने के लिए मशीन को कितना जटिल होने की आवश्यकता होगी?

यदि आप टेप को बहुत कम मात्रा में खिसकाते हैं (जैसे 5 स्थान), तो मशीन छोटी ही रहती है। लेकिन क्या होगा यदि आप इसे एक बहुत बड़ी मात्रा में खिसका दें, जैसे 1,000,000 स्थान?

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

उपमा: अनंत पुस्तकों का पुस्तकालय

फाइबोनैची वर्ड को अनंत पुस्तकों वाले एक पुस्तकालय के रूप में सोचें।

मानक मशीन: एक लाइब्रेरियन जो उन्हें किताब का पेज नंबर देने पर कोई भी पेज ढूंढ सकता है। उनके पास एक सरल मानचित्र (5 स्टेट्स) है जो मूल किताब के लिए काम करता है।
शिफ्ट की गई मशीन: अब, लाइब्रेरियन को पेज ढूंढना है, लेकिन किताब को खिसका दिया गया है। "पेज 1" अब वास्तव में "पेज 1000" है।
बुरी खबर: आमतौर पर, 1000 के शिफ्ट को संभालने के लिए, आपको एक ऐसे लाइब्रेरियन की आवश्यकता होगी जिसके पास हजारों कमरों वाला एक विशाल, भ्रमित करने वाला मानचित्र हो।
अच्छी खबर (यह शोध पत्र): लेखकों ने पाया कि फाइबोनैची लाइब्रेरी के लिए, आपको एक विशाल मानचित्र की आवश्यकता नहीं है। आपको बस एक स्मार्ट इंडेक्स की आवश्यकता है। इंडेक्स का आकार केवल उस संख्या की लंबाई के अनुपात में बढ़ता है जिससे आप शिफ्ट कर रहे हैं।
- 10 का शिफ्ट? छोटा इंडेक्स।
- 1,000,000 का शिफ्ट? अभी भी छोटा इंडेक्स।
- एक गूगोल (googol) का शिफ्ट? इंडेक्स अभी भी प्रबंधनीय है।

यह अविश्वसनीय रूप से कुशल है। यह किसी भी गैर-दोहराव वाले पैटर्न के लिए संभव सैद्धांतिक न्यूनतम आकार के बहुत करीब है।

उन्होंने यह कैसे किया? (गुप्त नुस्खा)

लेखकों ने इस पहेली को हल करने के लिए तीन उपकरणों के मिश्रण का उपयोग किया:

"फाइबोनैची रूलर" (ज़ेकेनडॉर्फ प्रतिनिधित्व - Zeckendorf Representation):
सामान्य बेस-10 (1, 2, 3...) में गिनती करने के बजाय, उन्होंने फाइबोनैची संख्याओं (1, 2, 3, 5, 8, 13...) पर आधारित एक विशेष तरीके से गिनती की। यह एक मेज को इंचों के बजाय एक विशेष रूलर से मापने जैसा है जिसमें केवल 1, 2, 3, 5 और 8 इंच के निशान हैं। इस रूलर का एक विशेष गुण है: आप कभी भी दो निशानों का लगातार उपयोग नहीं कर सकते। यह "कोई लगातार निशान नहीं" वाला नियम मशीन को सरल रखने की कुंजी है।
"गोल्डन सर्कल" (डायोफेंटाइन एप्रोक्सिमेशन - Diophantine Approximation):
उन्होंने इस समस्या को एक वृत्त (circle) के रूप में देखा। कल्पना कीजिए कि फाइबोनैची संख्याएँ एक वृत्त के चारों ओर घूम रही हैं। वे जहाँ भी पहुँचती हैं, वही स्थान निर्धारित करता है कि मोती काला है या सफेद। जब आप अनुक्रम को शिफ्ट करते हैं, तो आप अनिवार्य रूप से इस वृत्त को घुमा रहे होते हैं। लेखकों ने सिद्ध किया कि चाहे आप इसे कितना भी घुमा लें, "लैंडिंग स्पॉट्स" व्यवस्थित, स्पष्ट स्लाइस में रहते हैं।
"रोबोट लॉयर" (स्वचालित प्रमाण - Automated Proving):
उन्होंने केवल अनुमान नहीं लगाया; उन्होंने Walnut नामक एक कंप्यूटर प्रोग्राम का उपयोग किया। Walnut को एक बहुत ही सख्त रोबोट वकील की तरह समझें। लेखकों ने फाइबोनैची टेप के नियमों को एक औपचारिक भाषा में लिखा, और रोबोट ने बिना किसी संदेह के यह साबित करने के लिए हर एक संभावित परिदृश्य की जांच की कि मशीन का आकार वास्तव में छोटा ही रहता है।

टेप को पढ़ने के दो तरीके

शोध पत्र ने मशीन को संख्या फीड करने के दो तरीकों को देखा:

LSD-First (Least Significant Digit): संख्या को दाएं से बाएं पढ़ना (जैसे 123 को "3, फिर 2, फिर 1" के रूप में पढ़ना)।
MSD-First (Most Significant Digit): संख्या को सामान्य रूप से बाएं से दाएं पढ़ना (जैसे "1, फिर 2, फिर 3")।

आमतौर पर, बाएं से दाएं पढ़ना इन मशीनों के लिए बहुत कठिन होता है और इसके लिए बहुत अधिक गियर्स की आवश्यकता होती है। लेकिन फाइबोनैची वर्ड के लिए, लेखकों ने सिद्ध किया कि दोनों विधियों के परिणामस्वरूप एक छोटा, कुशल मशीन प्राप्त होता है।

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

कंप्यूटर विज्ञान की दुनिया में, "स्टेट कॉम्प्लेक्सिटी" (State Complexity) का अर्थ है कि किसी काम को करने के लिए कंप्यूटर को कितनी मेमोरी की आवश्यकता होती है।

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

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

यहाँ डेलारम मोराडी, पियरे पोपोली, जेफरी शालिट और इनग्रिड वुकुसिक के शोध पत्र "State Complexity of Shifts of the Fibonacci Word" का विस्तृत तकनीकी सारांश दिया गया है।

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

यह शोध पत्र फाइबोनैची शब्द $f = (f_i)_{i \ge 0}$ के शिफ्ट किए गए संस्करणों की स्टेट कॉम्प्लेक्सिटी (state complexity) की जांच करता है।

संदर्भ: फाइबोनैची शब्द एक ऑटोमैटिक अनुक्रम (विशेष रूप से, फाइबोनैची-ऑटोमैटिक) का एक मानक उदाहरण है। इसे एक 'डिटरमिनिस्टिक फाइनाइट ऑटोमैटन विद आउटपुट' (DFAO) द्वारा उत्पन्न किया जाता है।
संचालन (The Operation): लेखक एक निश्चित पूर्णांक शिफ्ट $c \ge 0$ के लिए शिफ्ट किए गए अनुक्रम $(f_{i+c})_{i \ge 0}$ पर विचार करते हैं।
प्रश्न: यह देखते हुए कि मूल अनुक्रम $f$ एक छोटे DFAO द्वारा उत्पन्न होता है (जेकेंडोर्फ प्रतिनिधित्व में, लीस्ट-सिग्निफिकेंट-डिजिट-फर्स्ट के लिए 5 अवस्थाएँ, या lsd-first, और मोस्ट-सिग्निफिकेंट-डिजिट-फर्स्ट के लिए 2 अवस्थाएँ, या msd-first), शिफ्ट किए गए अनुक्रम $(f_{i+c})_{i \ge 0}$ को उत्पन्न करने के लिए आवश्यक न्यूनतम DFAO की स्टेट कॉम्प्लेक्सिटी क्या है?
प्रेरणा: मानक बेस- $k$ प्रणालियों में, एक अनुक्रम को $c$ द्वारा शिफ्ट करने के लिए lsd-first इनपुट के लिए आमतौर पर $O(m \log c)$ अवस्थाओं की आवश्यकता होती है। हालाँकि, जेकेंडोर्फ प्रतिनिधित्व के लिए, मानक एडिशन ट्रांसड्यूसर मौजूद नहीं होते क्योंकि जोड़ (addition) को एकल पास (single pass) में नहीं किया जा सकता है। इसके अलावा, थ्यू-मोर्स (Thue-Morse) जैसे अन्य अनुक्रमों के लिए, msd-first शिफ्ट में $O(c)$ अवस्थाओं की आवश्यकता हो सकती है। लेखक यह निर्धारित करना चाहते हैं कि क्या फाइबोनैची शब्द शिफ्ट के लिए अधिक कुशल जटिलता प्रदर्शित करता है।

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

लेखक ऑटोमेटा थ्योरी (automata theory), डायोफेंटाइन एप्रोक्सिमेशन (Diophantine approximation), और फॉर्मल लॉजिक (formal logic) को संयोजित करने वाला एक हाइब्रिड दृष्टिकोण अपनाते हैं।

A. फाइबोनैची शब्द का गणितीय लक्षण वर्णन

प्रमाण का मुख्य आधार गोल्डन रेशियो $\phi = \frac{1+\sqrt{5}}{2}$ के गुणजों के भिन्नात्मक भागों (fractional parts) का उपयोग करके फाइबोनैची शब्द का ज्यामितीय लक्षण वर्णन है।

लेम्मा 1 (Lemma 1): $f(i) = 1$ यदि और केवल यदि $\{i\phi\} \in (-\phi, -2\phi) \pmod 1$ ।
लेम्मा 2 (Shifted): $f(i+c) = 1$ यदि और केवल यदि $\{i\phi\} \in (-(c+1)\phi, -(c+2)\phi) \pmod 1$ ।
यह प्रक्रिया अनुक्रम को उत्पन्न करने की समस्या को इस बात को निर्धारित करने की समस्या में बदल देती है कि मान $\{i\phi\}$ किस अंतराल (interval) में आता है।

B. यूनिट इंटरवल का विभाजन (Partitioning the Unit Interval)

लेखक जेकेंडोर्फ प्रतिनिधित्व के आधार पर अंतराल $[0, 1)$ के विशिष्ट विभाजन (partitions) का निर्माण करते हैं।

lsd-first के लिए: वे जेकेंडोर्फ प्रतिनिधित्व के पहले $d$ अंकों द्वारा प्रेरित एक विभाजन $I_d(m)$ को परिभाषित करते हैं। वे सिद्ध करते हैं कि किसी पूर्णांक $n$ के लो-ऑर्डर बिट्स उस अंतराल को निर्धारित करते हैं जिसमें $\{n\phi\}$ स्थित होता है। इन अंतरालों के छोर (endpoints) $\{-k\phi\}$ से संबंधित हैं।
msd-first के लिए: वे एक ऋणात्मक पूर्णांक प्रतिनिधित्व को "शिफ्ट" करने (सबसे महत्वपूर्ण अंक को हटाना) से प्राप्त पूर्णांकों के अनुक्रम के आधार पर एक विभाजन $P(r)$ को परिभाषित करते हैं। यह दिखाया गया है कि यह विभाजन msd-first फाइबोनैची प्रतिनिधित्व के साथ सुसंगत (consistent) है, जिसका अर्थ है कि एक अंक पढ़ने से ऑटोमैटन उसी विभाजन के भीतर एक विशिष्ट अंतराल से दूसरे अंतराल में परिवर्तित हो जाता है।

C. स्वचालित प्रमेय सिद्ध करना (Automated Theorem Proving)

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

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

A. मुख्य प्रमेय: लॉगरिदमिक स्टेट कॉम्प्लेक्सिटी

शोध पत्र का प्राथमिक परिणाम यह है कि शिफ्ट किए गए फाइबोनैची शब्द की स्टेट कॉम्प्लेक्सिटी lsd-first और msd-first दोनों इनपुट के लिए $O(\log c)$ है।

प्रमेय 1 (lsd-first): $(f_{i+c})$ के लिए एक lsd-first DFAO है जिसकी अवस्थाएँ $O(\log c)$ हैं।
प्रमेय 3 (msd-first): एक msd-first DFAO है जिसकी अवस्थाएँ $O(\log c)$ हैं।

यह एक महत्वपूर्ण खोज है क्योंकि:

यह थ्यू-मोर्स अनुक्रम के विपरीत है, जहाँ msd-first शिफ्ट के लिए $O(c)$ अवस्थाओं की आवश्यकता हो सकती है।
यह एपीरियॉडिक अनुक्रमों के लिए सूचना-सैद्धांतिक निचली सीमा (lower bound) $\Omega(\frac{\log c}{\log \log c})$ के करीब है।

B. सटीक स्टेट कॉम्प्लेक्सिटी फॉर्मूला (lsd-first)

लेखक lsd-first मामले के लिए आवश्यक न्यूनतम अवस्थाओं के लिए एक सटीक सूत्र प्रदान करते हैं (प्रमेय 2):
$\text{States} = 2(|(c)_F| + 1) + 1 - g(c)$
जहाँ:

$|(c)_F|$ $c$ के जेकेंडोर्फ प्रतिनिधित्व की लंबाई है।
$g(c) = 1$ यदि $f(c-1) = f(c-2) = 0$ , और $0$ अन्यथा।
यह पुष्टि करता है कि $O(\log c)$ सीमा इष्टतम (optimal) है, क्योंकि अवस्थाओं की संख्या $c$ के जेकेंडोर्फ प्रतिनिधित्व की लंबाई के साथ रैखिक रूप से बढ़ती है।

C. निर्माण तकनीकें (Construction Techniques)

lsd-first निर्माण: ऑटोमैटन $\{n\phi\}$ वाले अंतराल $I_d(m)$ को ट्रैक करता है। एक बार जब इनपुट की लंबाई $d$ इतनी पर्याप्त हो जाती है कि अंतराल $I_d(m)$ लक्ष्य अंतराल $J_c = (-(c+1)\phi, -(c+2)\phi)$ (या इसके पूरक) के भीतर पूरी तरह से समाहित हो जाता है, तो ऑटोमैटन एक "सिंक" (sink) अवस्था में चला जाता है। ऐसी "मध्यवर्ती" अवस्थाओं की संख्या $c$ के अंकों द्वारा सीमित है।
msd-first निर्माण: लेखक $P(-(c+1))$ और $P(-(c+2))$ के विभाजनों के छोरों को मिलाकर एक विभाजन $P$ का निर्माण करते हैं। चूंकि यह विभाजन msd-first प्रतिनिधित्व के साथ सुसंगत है, इसलिए ऑटोमैटन की अवस्थाएँ सीधे $P$ में अंतरालों के अनुरूप होती हैं। अंतरालों (endpoints) की संख्या $c$ से छोटी फाइबोनैची संख्याओं के अनुपात में होती है, जिससे $O(\log c)$ अवस्थाएँ प्राप्त होती हैं।

4. महत्व (Significance)

एक विशिष्ट मामले का समाधान: यह शोध पत्र शिफ्ट ऑपरेशन के तहत सबसे प्रसिद्ध एपीरियॉडिक शब्द (फाइबोनैची शब्द) के लिए स्टेट कॉम्प्लेक्सिटी के प्रश्न को हल करता है, यह दिखाते हुए कि यह अन्य ऑटोमैटिक अनुक्रमों की तुलना में "इष्टतम" व्यवहार करता है।
पद्धतिगत नवाचार: यह डायोफेंटाइन एप्रोक्सिमेशन ( $\{n\phi\}$ के गुण) को ऑटोमेटा थ्योरी के साथ जोड़ने की शक्ति को प्रदर्शित करता है। अवस्थाओं को परिभाषित करने के लिए भिन्नात्मक भागों (fractional parts) का उपयोग करना फाइबोनैची-ऑटोमैटिक अनुक्रमों के लिए एक नवीन और शक्तिशाली तकनीक है।
टूल वैलिडेशन: अंतरालों के जटिल ज्यामितीय गुणों को सिद्ध करने के लिए Walnut का सफल उपयोग शब्दों के संयोजन (combinatorics on words) में स्वचालित प्रमेय सिद्ध करने की उपयोगिता को पुख्ता करता है।
सामान्यीकरण की क्षमता: लेखक सुझाव देते हैं कि ये तकनीकें अन्य द्विघाती अपरिमेय (quadratic irrationals) और संभावित रूप से ट्राइबोनैची (Tribonacci) शब्द तक विस्तारित हो सकती हैं, जो अन्य संख्या प्रणालियों में शिफ्ट की स्टेट कॉम्प्लेक्सिटी में भविष्य के अनुसंधान के द्वार खोलती हैं।

सारांश (Summary)

यह शोध पत्र सिद्ध करता है कि फाइबोनैची शब्द को $c$ स्थानों से शिफ्ट करने से एक ऐसा अनुक्रम प्राप्त होता है जिसे केवल $O(\log c)$ अवस्थाओं वाले परिमित ऑटोमैटन द्वारा पहचाना जा सकता है, चाहे इनपुट को मोस्ट या लीस्ट सिग्निफिकेंट डिजिट से पढ़ा जाए। यह गोल्डन रेशियो के गुणजों के भिन्नात्मक भागों की ज्यामिति को समस्या से जोड़कर और विशिष्ट अंतराल विभाजनों का निर्माण करके प्राप्त किया गया है जो जेकेंडोर्फ प्रतिनिधित्व की संरचना का सम्मान करते हैं। परिणाम फाइबोनैची शब्द की अद्वितीय संरचनात्मक दक्षता को अन्य ऑटोमैटिक अनुक्रमों की तुलना में उजागर करते हैं।