🔢 mathematics

State Complexity of Shifts of the Fibonacci Word

Die Arbeit zeigt, dass die Zustandskomplexität der Automaten, die die um $c$ verschobene Fibonacci-Wort-Folge generieren, für sowohl lsd-first- als auch msd-first-Eingabe durch $O(\log c)$ beschränkt ist, was nahe an der informationstheoretischen Untergrenze für aperiodische Folgen liegt.

Ursprüngliche Autoren: Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

Veröffentlicht 2026-03-20

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Delaram Moradi, Pierre Popoli, Jeffrey Shallit, Ingrid Vukusic

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Die große Reise: Wenn Zahlen tanzen und Automaten zählen

Stellen Sie sich vor, Sie haben eine unendliche Kette von Perlen, die sich nach einer ganz bestimmten, aber sehr kniffligen Regel aneinanderreihen. Diese Kette heißt Fibonacci-Wort. Sie sieht so aus: 01001010.... Jede Perle ist entweder schwarz (0) oder weiß (1).

Das Besondere an dieser Kette ist, dass sie nicht zufällig ist, sondern wie ein mathematischer Tanz folgt. Um zu wissen, welche Farbe die n-te Perle hat, muss man nicht die ganze Kette von vorne zählen. Man kann eine kleine Maschine (einen Automaten) bauen, die nur die Zahl n (in einer speziellen Form, die wir später erklären) bekommt und sofort sagt: „Schwarz" oder „Weiß".

Die Forscher in diesem Papier stellen sich nun eine ganz einfache, aber tiefgründige Frage:
Was passiert, wenn wir die Kette ein Stück weit verschieben?

Stellen Sie sich vor, Sie nehmen die Kette und schieben sie um 10 Perlen nach rechts. Die erste Perle ist jetzt nicht mehr die alte erste, sondern die elfte. Die neue Kette ist also (f(i+10)). Die Frage lautet: Wie groß muss die Maschine sein, um diese verschobene Kette zu erkennen?

Die zwei Arten, die Welt zu lesen (LSB und MSB)

Um die Zahl n in die Maschine einzugeben, gibt es zwei verschiedene Sprachen, ähnlich wie man ein Buch lesen kann:

LSB-first (Least Significant Bit first): Man liest die Zahl von der kleinsten Stelle zur größten (wie wenn man von rechts nach links liest: 101 bedeutet hier 1, dann 0, dann 1).
MSB-first (Most Significant Bit first): Man liest von der größten zur kleinsten Stelle (wie im normalen Leben: 101 bedeutet 1, dann 0, dann 1).

In der Mathematik ist es oft so, dass eine Aufgabe in einer Sprache viel einfacher ist als in der anderen. Bei den meisten Zahlen-Systemen (wie unserem normalen Dezimalsystem) ist das Verschieben einer Kette eine schwierige Aufgabe für die Maschine, besonders wenn man von rechts nach links liest. Man braucht dann oft riesige Maschinen.

Die magische Entdeckung: Die Fibonacci-Kette ist besonders

Die Forscher haben herausgefunden, dass die Fibonacci-Kette ein Superkraft besitzt. Egal, ob man die Zahl von links (MSB) oder von rechts (LSB) liest:

Wenn man die Kette um eine Zahl c verschiebt, braucht man für die neue Maschine nicht eine riesige Anzahl an Zuständen (Teilen der Maschine). Man braucht nur eine sehr kleine Anzahl, die mit dem Logarithmus von c wächst.

Die Analogie:
Stellen Sie sich vor, Sie wollen eine Nachricht verschlüsseln.

Bei normalen Kettensystemen (wie dem Thue-Morse-Wort) würde das Verschieben der Nachricht um 100 Stellen bedeuten, dass Sie eine Bibliothek voller neuer Schlüssel brauchen. Die Maschine wird riesig.
Bei der Fibonacci-Kette ist es wie mit einem magischen Kompass. Egal, wie weit Sie die Kette verschieben (ob um 10 oder um 1.000.000), der Kompass wird nur ein kleines bisschen größer. Er wächst nicht linear (100 Schritte = 100 mal größer), sondern logarithmisch. Das ist extrem effizient!

Wie funktioniert das? (Die Zeckendorf-Methode)

Um das zu verstehen, müssen wir wissen, wie die Zahlen in dieser Welt geschrieben werden. Wir nutzen nicht das normale 1-2-3-4-System, sondern das Zeckendorf-System.
Statt Potenzen von 10 (1, 10, 100) nutzen wir hier Fibonacci-Zahlen (1, 2, 3, 5, 8, 13...).
Die Regel ist: Man darf keine zwei benachbarten Fibonacci-Zahlen addieren.

Die Zahl 10 ist also nicht 5+5, sondern 8+2. In unserer Sprache sieht das aus wie 10010.

Die Forscher haben bewiesen, dass diese spezielle Art, Zahlen zu schreiben, es der Maschine erlaubt, das Verschieben der Kette extrem clever zu berechnen. Sie nutzen dabei ein Werkzeug aus der Zahlentheorie, das Diophantische Approximation heißt.

Die Metapher:
Stellen Sie sich vor, die Fibonacci-Zahlen sind wie Treppe, die sich spiralförmig um einen Turm windet. Wenn Sie einen Schritt verschieben, müssen Sie nicht den ganzen Turm neu bauen. Sie nutzen die Spirale, um zu sehen, wo Sie landen, und brauchen dafür nur ein paar wenige Markierungen.

Das Ergebnis in einem Satz

Die Forscher haben gezeigt, dass man für jede beliebige Verschiebung der Fibonacci-Kette eine winzige, effiziente Maschine bauen kann. Die Größe dieser Maschine hängt nur davon ab, wie viele „Ziffern" man braucht, um die Verschiebungsanzahl zu schreiben, und nicht von der Verschiebungsanzahl selbst.

Das ist fast so gut wie es theoretisch möglich ist. Es ist, als würde man sagen: „Um eine unendliche Kette um eine Million Schritte zu verschieben, brauchen wir nicht eine Million neue Teile, sondern nur etwa so viele Teile, wie man braucht, um die Zahl '1.000.000' aufzuschreiben."

Warum ist das wichtig?

Dies ist ein Durchbruch in der Beschreibungskomplexität. Es zeigt uns, dass bestimmte mathematische Strukturen (wie die Fibonacci-Kette) eine inhärente Einfachheit besitzen, die wir nutzen können, um Computerprogramme und Algorithmen viel kleiner und schneller zu machen. Es verbindet die Welt der Automaten (Computer) mit der Welt der Zahlen (Zahlentheorie) auf eine elegante Weise.

Zusammenfassend: Die Fibonacci-Kette ist wie ein gut geölter Mechanismus. Wenn man ihn verschiebt, klemmt er nicht und wird nicht riesig. Er bleibt klein, schlank und effizient – egal wie weit man ihn schiebt.

1. Problemstellung

Das Papier untersucht die Zustandskomplexität (State Complexity) von Automaten, die verschobene Folgen des unendlichen Fibonacci-Wortes $f$ generieren.

Das Fibonacci-Wort: $f = (f_i)_{i \ge 0} = 01001010\dots$ ist eine der bekanntesten aperiodischen Folgen in der Kombinatorik auf Wörtern. Es kann durch verschiedene äquivalente Definitionen charakterisiert werden, darunter als Fixpunkt eines Morphismus, als Grenzwert von Wortfolgen oder als charakteristisches Wort einer irrationalen Steigung (Sturmianisches Wort).
Die Aufgabe: Gegeben sei ein Verschiebungsparameter $c \ge 0$ . Gesucht ist die Größe des kleinsten deterministischen endlichen Automaten mit Ausgabe (DFAO), der die verschobene Folge $(f(i+c))_{i \ge 0}$ berechnet.
Zwei Eingabeformate: Die Analyse erfolgt für zwei Darstellungsweisen der Eingabe $i$ $i$ :
1. lsd-first (Least Significant Digit first): Die Ziffern werden von der kleinsten zur größten Stelle gelesen (entspricht der üblichen Basis- $k$ -Darstellung, hier im Zeckendorf-System).
2. msd-first (Most Significant Digit first): Die Ziffern werden von der größten zur kleinsten Stelle gelesen.
Hintergrund: Während das ursprüngliche Fibonacci-Wort durch einen sehr kleinen Automaten (5 Zustände für lsd-first, 2 für msd-first) generiert werden kann, ist unklar, wie stark die Komplexität bei einer Verschiebung um $c$ anwächst. Bei allgemeinen $k$ -automatischen Folgen kann eine Verschiebung im msd-first-Format zu einer exponentiellen oder zumindest linearen Komplexität führen (z. B. beim Thue-Morse-Wort). Das Ziel ist zu bestimmen, ob das Fibonacci-Wort eine Ausnahme darstellt.

2. Methodik

Die Autoren kombinieren Techniken aus der Zustandskomplexität, der Diophantischen Approximation und der Logik/Automatentheorie.

Zeckendorf-Darstellung: Da das Fibonacci-Wort eng mit dem Zeckendorf-System (Darstellung natürlicher Zahlen als Summe nicht-konsekutiver Fibonacci-Zahlen) verknüpft ist, bilden diese Darstellungen die Grundlage für die Eingabe. Das Papier führt zudem eine spezielle Darstellung für negative Zahlen im Zeckendorf-System ein, die für die Analyse der Verschiebung notwendig ist.
Diophantische Approximation & Fraktionale Teile: Ein zentrales Werkzeug ist die Charakterisierung des $i$ $i$ -ten Bits von $f$ $f$ über den fraktionalen Teil $\{i\phi\}$ ${i ϕ}$ (wobei $\phi$ $ϕ$ der goldene Schnitt ist).
- Lemma 1: $f(i) = 1 \iff \{i\phi\} \in (-\phi, -2\phi) \pmod 1$ .
- Daraus folgt für die verschobene Folge: $f(i+c) = 1 \iff \{i\phi\} \in (-(c+1)\phi, -(c+2)\phi) \pmod 1$ .
Intervall-Partitionen:
- Für den lsd-first-Fall wird eine Partition des Intervalls $[0, 1)$ definiert, die durch die niedrigen Bits der Zeckendorf-Darstellung von $i$ induziert wird. Die Autoren zeigen, dass die Kenntnis der ersten $k$ Bits ausreicht, um zu bestimmen, in welchem Intervall $\{i\phi\}$ liegt.
- Für den msd-first-Fall wird eine konsistente Partition konstruiert, die unter dem Hinzufügen von Bits (Operation $n(a)$ ) und dem Entfernen von Bits (Operation $n'$ ) stabil bleibt.
Automatisierte Beweisführung (Walnut): Ein Teil der Beweise, insbesondere die Überprüfung von Eigenschaften der Intervall-Transformationen beim Lesen von Bits, wurde mit dem Theorem-Prover Walnut durchgeführt. Dies ermöglichte rigorose Verifizierungen komplexer logischer Aussagen über die Fibonacci-Folge.

3. Wichtige Beiträge und Ergebnisse

Das Hauptergebnis des Papiers ist die Bestimmung der asymptotischen Zustandskomplexität für beide Eingabeformate.

A. lsd-first Fall (Theorem 1)

Ergebnis: Für jede Verschiebung $c$ existiert ein lsd-first DFAO mit $O(\log c)$ Zuständen, der $(f(i+c))_{i \ge 0}$ generiert.
Konstruktion: Der Automat nutzt die Tatsache, dass die ersten $k$ Ziffern der Zeckendorf-Darstellung von $i$ (wobei $F_k \approx c$ ) ausreichen, um das Intervall zu bestimmen, in dem $\{i\phi\}$ liegt. Sobald das Intervall vollständig innerhalb des Zielintervalls $(-(c+1)\phi, -(c+2)\phi)$ liegt oder vollständig außerhalb, geht der Automat in einen „Sink-Zustand" (Endzustand mit fester Ausgabe).
Optimalität (Theorem 2): Die Autoren geben eine exakte Formel für die minimale Anzahl der Zustände an: $2(|(c)_F| + 1) + 1 - g(c)$ , wobei $|(c)_F|$ die Länge der Zeckendorf-Darstellung von $c$ ist. Da die Länge logarithmisch mit $c$ wächst, ist die Schranke $O(\log c)$ scharf.

B. msd-first Fall (Theorem 3)

Ergebnis: Auch für das msd-first Format existiert ein DFAO mit $O(\log c)$ Zuständen.
Herausforderung: Im Gegensatz zum lsd-first Fall gibt es keinen einfachen Transducer, der eine Addition $i+c$ in einem Durchlauf berechnet, da das Übertragen von Ziffern (Carry) von links nach rechts schwierig ist.
Lösung: Die Autoren konstruieren eine Partition von $[0, 1)$ basierend auf den Endpunkten $\{-(c+1)\phi\}$ und $\{-(c+2)\phi\}$ . Sie zeigen, dass diese Partition „konsistent" mit der msd-first-Darstellung ist: Das Hinzufügen eines Bits am Ende der Darstellung (was dem msd-first-Einlesen entspricht) führt zu einer wohldefinierten Transformation der Intervalle innerhalb der Partition. Die Anzahl der Intervalle (und damit der Zustände) wächst logarithmisch mit $c$ .

4. Signifikanz und Einordnung

Informationstheoretisches Minimum: Die Komplexität $O(\log c)$ liegt sehr nahe am informationstheoretischen Minimum für aperiodische verschobene Folgen. Ein einfaches Zählargument zeigt, dass für nicht-periodische Folgen die Komplexität mindestens $\Omega(\frac{\log c}{\log \log c})$ betragen muss. Das Fibonacci-Wort erreicht also fast die bestmögliche Effizienz für eine Verschiebung.
Kontrast zu anderen Folgen: Dies steht im starken Kontrast zu Folgen wie dem Thue-Morse-Wort, bei dem die msd-first-Komplexität für Verschiebungen linear ( $O(c)$ ) oder sogar stärker wächst. Das Fibonacci-Wort ist somit ein bemerkenswertes Beispiel für eine aperiodische Folge, die unter Verschiebungen „robust" bleibt.
Methodischer Fortschritt: Die Arbeit demonstriert erfolgreich die Kombination von klassischer Automatentheorie, tiefer Zahlentheorie (Diophantische Approximation mit $\phi$ ) und automatischer Beweisführung. Die Einführung der negativen Zeckendorf-Darstellung und die Analyse der Intervall-Transformationen bieten neue Werkzeuge für die Untersuchung anderer numerischer Systeme und Folgen.
Zukunftsausblick: Die Autoren deuten an, dass sich diese Ergebnisse auf andere quadratische Irrationalzahlen und auf das Tribonacci-Wort verallgemeinern lassen, wobei die Analyse dort komplexer sein könnte.

Fazit: Das Papier beweist, dass die Zustandskomplexität von Verschiebungen des Fibonacci-Wortes für beide gängigen Eingabeformate (lsd-first und msd-first) logarithmisch in der Verschiebung $c$ ist. Dies stellt eine optimale oder nahezu optimale Effizienz dar und hebt das Fibonacci-Wort als ein besonders gutartiges Objekt in der Theorie der automatischen Folgen hervor.