Symbolic / L-system
Fibonacci word fractal
The infinite Fibonacci word is the limit of the substitution 1 → 10, 0 → 1 (or equivalently fn = fn−1 fn−2). Drawing it with a turtle that steps forward on each symbol and turns according to bit parity produces the Fibonacci word fractal.
At a glance
| Word length at step n | Fn (Fibonacci numbers) |
|---|---|
| Drawing rule | Forward 1 step per symbol; on ‘0’ turn left 90° if index is odd, right 90° if even |
| Hausdorff dimension | 3 log φ / log(1 + √2) ≈ 1.6379 |
Connection to the golden ratio
The Fibonacci word is the canonical example of a Sturmian sequence. It encodes the irrational rotation by 1/φ on the circle: read each step of the rotation, output 0 or 1 depending on which half of the circle you land in. The result is aperiodic, so the Fibonacci word fractal has no exact periodicity at any scale.
Properties
- Aperiodic but deterministic: the word is fixed by the substitution.
- Combinatorial complexity: contains exactly n + 1 distinct factors of length n.
- Self-similarity: removing every other letter (or applying the inverse substitution) yields a scaled copy.
References
- Monnerot-Dumaine, A., “The Fibonacci word fractal,” HAL preprint, 2009.
- Lothaire, M., Algebraic Combinatorics on Words, Cambridge, 2002.
- L-systems
Try it
Run an interactive playground at /tools/fibonacci-word.