EP49

EP49: L-Systems & Algorithmic Composition

并行字符串替换 · 分形维度 · 黄金角 · 涌现音乐结构

▶ 5:30 Formal LanguagesNonlinear DynamicsMusicologyCombinatorics

前置知识

EP16 Rossini's Code — Budden, Gossett, and the Convention System

Overview / 概述

A tree grows one rule at a time — yet from just two substitution rules, an infinite self-similar structure emerges. This is the central insight of Lindenmayer systems (L-systems): simple parallel string-rewriting rules, iterated repeatedly, produce fractal geometry and — with an appropriate interpretation scheme — fractal musical structure.

中文: “一棵树的生长规则，竟然能’长出’一首赋格？”

L-systems were invented in 1968 by the Hungarian biologist Aristid Lindenmayer to model the development of filamentous plants. The key innovation is parallel rewriting: at each step, every symbol in the string is simultaneously replaced by its expansion. This is in sharp contrast to context-free grammars (EP16), which expand one nonterminal at a time in a sequential derivation. The result of parallel rewriting is that each local piece of the string is a miniature copy of the whole — the hallmark of self-similarity.

The same mathematical machinery that generates the Koch snowflake, the Sierpiński triangle, and the branching patterns of ferns can be mapped, via a turtle interpretation, onto pitch sequences, rhythmic structures, and harmonic branching. This episode develops the formal theory of L-systems, computes their fractal dimension using the Hausdorff-Besicovitch formula, and connects the Fibonacci sequence and the golden angle to natural and musical proportion.

Prerequisites / 前置知识

Context-Free Grammars and Formal Languages (EP16) — sequential string rewriting, derivation trees, and the distinction between terminal and nonterminal symbols; L-systems are the parallel analogue of CFGs.

Definitions

Definition 49.1 (Lindenmayer System (L-System))

A deterministic context-free L-system (D0L-system) is a triple

$\mathcal{L} = (V,\, \omega,\, P)$

where:

$V$ is a finite alphabet of symbols.
$\omega \in V^+$ is the axiom (initial string), a non-empty word over $V$ .
$P : V \to V^*$ is the production function, assigning to each symbol $a \in V$ a replacement string $P(a) \in V^*$ .

The system evolves by parallel rewriting: given current string $w = a_1 a_2 \cdots a_n$ , the next string is

$w' = P(a_1)\, P(a_2)\, \cdots\, P(a_n)$

where juxtaposition denotes string concatenation. The string at step $n$ is denoted $w^{(n)}$ , with $w^{(0)} = \omega$ .

Worked example — the Fibonacci L-system. Let $V = \{A, B\}$ , $\omega = A$ , and production rules $P(A) = AB$ , $P(B) = A$ . The first five generations are:

Step	String	Length
$n = 0$	A	1
$n = 1$	AB	2
$n = 2$	ABA	3
$n = 3$	ABAAB	5
$n = 4$	ABAABABA	8

The lengths 1, 2, 3, 5, 8, … are consecutive Fibonacci numbers. This is not coincidental — it follows directly from the structure of the rewriting rules.

中文: “你认出来了吗？这是斐波那契数列——每一步的长度是前两步之和。”

Definition 49.2 (Turtle Interpretation)

A turtle interpretation maps an L-system string over an extended alphabet $V \supseteq \{F, +, -, [, ]\}$ to a geometric path (or a musical sequence) via the following state machine. The turtle carries a state $(\mathbf{p}, \theta)$ : position $\mathbf{p} \in \mathbb{R}^2$ and heading angle $\theta \in [0, 2\pi)$ .

Symbol	Geometric action	Musical action
$F$	Move forward by step $\delta$ , drawing a segment	Play one note at current pitch
$+$	Turn left by angle $\alpha$	Raise pitch by interval $\alpha$
$-$	Turn right by angle $\alpha$	Lower pitch by interval $\alpha$
$[$	Push $(\mathbf{p}, \theta)$ onto stack	Begin a chord branch (push state)
$]$	Pop $(\mathbf{p}, \theta)$ from stack	End chord branch (pop state)

The stack mechanism (bracket pair $[ \cdots ]$ ) enables branching structure — the defining feature that allows L-systems to model trees (and polyphonic music) rather than just linear curves.

Worked example — Koch curve. Let $V = \{F, +, -\}$ , axiom $\omega = F$ , rule $P(F) = F{+}F{-}F{-}F{+}F$ , turning angle $\alpha = 90°$ . After three iterations the turtle traces the boundary of the Koch snowflake, a fractal with Hausdorff dimension $\log 4 / \log 3 \approx 1.26$ .

中文: “Koch 曲线的规则：F 替换为 F 加 F 减 F 减 F 加 F。迭代三次，得到分形雪花边界。”

Definition 49.3 (Hausdorff-Besicovitch (Fractal) Dimension)

For a self-similar set generated by $N$ copies of itself, each scaled by factor $r < 1$ (the self-similarity ratio), the similarity dimension (which coincides with the Hausdorff dimension for geometrically regular L-system outputs) is

$d_H = \frac{\log N}{\log(1/r)}$

For a line segment: $N = 1$ , $r = 1$ , giving $d_H = 1$ . For a filled square: $N = 4$ , $r = 1/2$ , giving $d_H = 2$ . For the Koch curve: $N = 4$ , $r = 1/3$ , giving $d_H = \log 4 / \log 3 \approx 1.2619$ .

Definition 49.4 (Golden Angle)

The golden ratio is $\varphi = (1 + \sqrt{5})/2 \approx 1.618$ . The golden angle is

$\alpha_g = 360° \cdot \frac{1}{\varphi^2} = 360° \cdot (2 - \varphi) \approx 137.508°$

Equivalently, $\alpha_g = 360° / \varphi^2$ . In phyllotaxis (the arrangement of leaves, seeds, or scales on a plant), each successive element is placed at angular offset $\alpha_g$ from the previous one. The resulting spiral pattern exhibits Fibonacci numbers of arms in adjacent directions.

中文: “这个角度是三百六十度除以黄金比的平方，等价于三百六十度乘以二减黄金比，约等于一百三十七点五度——因为黄金比是’最难被有理数逼近的无理数'，按黄金角排列能在所有尺度上避免聚集。”

Main Theorems / 主要定理

Theorem 49.1 (Fibonacci Growth from Parallel Rewriting)

Let $\mathcal{L} = (\{A,B\},\, A,\, P)$ with $P(A) = AB$ , $P(B) = A$ . Denote by $a_n$ and $b_n$ the number of $A$ ’s and $B$ ’s in $w^{(n)}$ , and let $F_n = a_n + b_n$ be the total length. Then:

$F_n = F_{n-1} + F_{n-2}, \qquad F_0 = 1,\quad F_1 = 2$

so $F_n$ is the $(n+2)$ -th Fibonacci number. Moreover, $\lim_{n \to \infty} F_{n+1}/F_n = \varphi$ .

Proof.

The key is to track $a_n$ and $b_n$ separately. Under one parallel rewriting step, each $A$ produces one $A$ and one $B$ , while each $B$ produces one $A$ . Therefore:

$a_{n+1} = a_n + b_n, \qquad b_{n+1} = a_n$

It follows that $F_{n+1} = a_{n+1} + b_{n+1} = (a_n + b_n) + a_n = F_n + a_n = F_n + b_{n+1}$ . Since $b_{n+1} = a_n = F_{n-1} - b_{n-1} + b_{n-1} \cdots$ , a simpler path: $a_n = F_{n-1}$ and $b_n = F_{n-2}$ (verifiable by induction), so $F_n = F_{n-1} + F_{n-2}$ . The ratio $F_{n+1}/F_n \to \varphi$ is a classical result from the characteristic equation $x^2 = x + 1$ , whose positive root is $\varphi$ . $\square$

Theorem 49.2 (Parallel vs Sequential Rewriting)

Let

\mathcal{G} = (V_N, V_T, S, \mathcal{R})

be a context-free grammar and

\mathcal{L} = (V, \omega, P)

be a D0L-system over the same alphabet and rules. Starting from the same axiom with a single nonterminal, the set of strings derivable in

\mathcal{G}

in exactly

k

sequential steps is strictly larger than the single string

w^{(k)}

produced by

\mathcal{L}

k

parallel steps, unless all production rules are of the form

A \to a

(terminal productions).

Proof.

In a CFG, at each derivation step one nonterminal is chosen and expanded; the choice of which nonterminal to expand may differ, yielding multiple possible derived strings. In an L-system, the parallel map

w \mapsto P(w_1)P(w_2)\cdots P(w_n)

is a function — it admits no choice. Hence from a given string, one application of

P

produces exactly one successor. The CFG’s derivation relation is a binary relation (many-to-many), whereas the L-system’s rewriting relation is a function (one-to-one). When rules are non-trivial (

P(A)

contains more than one symbol), multiple nonterminals in the CFG string can each be chosen first, producing different intermediate strings — none of which match the L-system’s single deterministic output.

\square

中文: “L 系统是并行重写：每一步同时替换所有字符。并行重写产生了自相似结构——每个局部都是整体的缩小版。这是植物生长的基本机制。”

Theorem 49.3 (Hausdorff Dimension of the Koch Curve)

The Koch curve, generated by the L-system with rule $F \to F{+}F{-}F{-}F{+}F$ and angle $\alpha = 90°$ , has Hausdorff dimension

$d_H(\text{Koch}) = \frac{\log 4}{\log 3} \approx 1.2619$

In particular, $d_H$ is strictly between 1 (line) and 2 (plane).

Proof.

After one application of the rule, each segment of length $\ell$ is replaced by $N = 4$ segments each of length $\ell/3$ (the scaling ratio is $r = 1/3$ because the original segment is divided into thirds, with the middle third replaced by two sides of an equilateral triangle). By the Moran equation for self-similar sets with a single scaling ratio, the similarity dimension satisfies

$N \cdot r^{d_H} = 1 \quad \Longrightarrow \quad 4 \cdot (1/3)^{d_H} = 1 \quad \Longrightarrow \quad d_H = \frac{\log 4}{\log 3}$

Under the open set condition (which holds for the Koch curve by geometric inspection), the similarity dimension equals the Hausdorff dimension. $\square$

Theorem 49.4 (Golden Angle Optimality)

Among all angular offsets

\alpha \in (0°, 360°)

, the golden angle

\alpha_g = 360° / \varphi^2 \approx 137.5°

uniquely minimizes clustering: for any number

n

of elements placed at successive offsets

\alpha_g

, no two elements occupy the same angular position (mod

360°

), and the gaps between elements are as uniform as possible at every scale. This follows because

\varphi

has the slowest-converging continued fraction expansion among all positive reals.

Proof.

The continued fraction expansion of

\varphi

[1; 1, 1, 1, \ldots]

— all partial quotients equal 1, which are the smallest possible. By the theory of continued fractions (Hurwitz’s theorem), a number with all partial quotients equal to 1 is the hardest to approximate by rationals: for any rational

p/q

|\varphi - p/q| > 1/(\sqrt{5}\, q^2)

, and this bound is tight. An offset of

\alpha_g = 2\pi(1 - 1/\varphi) = 2\pi/\varphi^2

radians corresponds to the irrational rotation by

1/\varphi^2

of the circle. Since

1/\varphi^2

is never well-approximated by a rational

p/q

, no

n

consecutive placements cluster near any arc. The three-distance theorem (Steinhaus 1950) then guarantees that

n

points placed at offsets

\{k/\varphi^2 \bmod 1\}_{k=0}^{n-1}

create gaps of at most three distinct lengths — the most uniform possible for an irrational rotation.

\square

Numerical Examples

Fractal dimension comparison table:

Structure	L-system rule	$N$ copies	Scaling $r$	$d_H = \log N / \log(1/r)$
Line segment	$F \to FF$	2	1/2	1.000
Koch curve	$F \to F{+}F{-}F{-}F{+}F$	4	1/3	1.262
Sierpiński triangle	(gasket L-system)	3	1/2	1.585
Space-filling curve	Hilbert curve limit	4	1/2	2.000

Fibonacci L-system string length:

For the rules $A \to AB$ , $B \to A$ , the string length at step $n$ is $F_{n+2}$ (the $(n+2)$ -th Fibonacci number):

|w^{(0)}| = 1, \quad |w^{(1)}| = 2, \quad |w^{(2)}| = 3, \quad |w^{(3)}| = 5, \quad |w^{(4)}| = 8, \quad |w^{(10)}| = 144

The ratio $|w^{(n+1)}| / |w^{(n)}|$ converges to $\varphi \approx 1.618$ exponentially fast: by step $n = 10$ , the ratio $144/89 = 1.6180\ldots$ agrees with $\varphi$ to four decimal places.

Golden angle phyllotaxis: In a sunflower with 89 clockwise spirals and 55 counterclockwise spirals, the ratio $89/55 \approx 1.618$ . With 144 seeds placed at successive golden-angle offsets, covering a disk of radius $R$ , the packing density approaches $\pi/(2\sqrt{3}) \approx 90.7\%$ — close to optimal hexagonal packing, achieved without any global coordination.

Musical Connection / 音乐联系

音乐联系

The same rules, grown into sound

The turtle interpretation maps the same L-system alphabet to music: $F$ becomes a note event, $+$ and $-$ become ascending and descending pitch steps (by a chosen interval $\alpha$ ), and bracket pairs $[\cdots]$ produce simultaneous harmonic branches (chords or ornaments).

With the Fibonacci rules $A \to AB$ , $B \to A$ and the musical assignment $A \mapsto$ quarter note, $B \mapsto$ eighth note, the resulting rhythm at each generation is a longer version of the pattern at the previous generation — rhythmic self-similarity. The ratio of quarter to eighth notes at step $n$ is $a_n / b_n = F_{n-1}/F_{n-2} \to \varphi$ : the golden ratio emerges in the rhythmic proportion.

中文: “音乐版本：F 是一个音符，加号是升调，减号是降调，方括号是和弦分支。同一规则，生成旋律结构。”

Fractal dimension as musical complexity: The Hausdorff dimension $d_H$ of an L-system’s geometric output provides a heuristic measure of structural complexity for its musical counterpart. A melody generated by a Koch-like rule ( $d_H \approx 1.26$ ) has more local variation than a simple ascending scale ( $d_H = 1$ ), but less global filling than a random walk ( $d_H \to 2$ ). This analogy is heuristic: the direct relationship between $d_H$ and perceived musical complexity has not been established in the music cognition literature.

中文: “L 系统生成的旋律，其自相似程度可以用分形维度来类比量化——维度越高，结构越复杂（这是一种启发性类比，分形维度与感知复杂度的直接关系尚未在音乐认知文献中建立）。”

Golden ratio in musical proportion: The golden ratio appears as a structural proportion in several celebrated compositions. Bartók’s Music for Strings, Percussion and Celesta (1936) has been analyzed (Lendvai 1971) as placing the climactic entry of the fugue subject at the golden section of the movement. Whether Bartók deliberately applied $\varphi$ or the effect arises from Fibonacci-structured phrase lengths is debated; the mathematical structure is present regardless of compositional intent.

Dividing a phrase or a form by the golden ratio produces sections of length $\varphi : 1$ , so that the shorter section is to the longer as the longer is to the whole — the defining property of $\varphi$ :

$\frac{a}{b} = \frac{a+b}{a} = \varphi, \qquad a = \varphi\, b$

Connection to EP16 (CFGs): The parallel/sequential distinction (Theorem 49.2) connects directly to

EP16’s context-free grammars

. CFGs model hierarchical musical syntax — phrase structure, cadential patterns — through sequential derivation trees. L-systems extend this to growth processes where all sub-structures develop simultaneously, producing the emergent self-similarity absent in CFG derivations.

中文: “自相似性不是复杂算法的结果，而是简单规则多次迭代的涌现属性。”

Limits and Open Questions / 局限性与开放问题

Stochastic and context-sensitive L-systems. The D0L-systems in this episode are deterministic and context-free. Real biological growth involves randomness (stochastic L-systems, SL-systems) and neighbor-dependent rules (context-sensitive L-systems, 2L-systems). The musical analogues — probabilistic melody generation and context-aware harmonization — remain largely unexplored as a unified formal framework.
Fractal dimension and music perception. The Hausdorff dimension $d_H$ is a geometric invariant of the L-system’s output curve. Claiming that $d_H$ directly measures perceived musical complexity requires a psychoacoustic bridge that does not yet exist in the literature. Controlled listening experiments comparing melodies of equal length but differing $d_H$ have not been systematically conducted.
Turtle interpretation is non-canonical. The mapping from L-system alphabet to musical parameters (which symbol = note, which = pitch shift, what interval $\alpha$ , what time unit) is chosen by the composer, not determined by mathematics. Different interpretations of the same L-system produce entirely different musical surfaces. There is no principled theory of which interpretations preserve musically meaningful structure.
Inversibility. Given a musical passage, no general algorithm recovers the L-system that generated it, because many L-systems produce the same string at a given iteration and the turtle interpretation is lossy. The inverse problem — L-system inference from a musical surface — is computationally hard (NP-hard in general for string compression problems).

Conjecture (Perceptual Equivalence at Matching Dimension)

Two melodies generated by different L-systems but with the same Hausdorff dimension $d_H$ are rated as equally “complex” or “ornate” by naive listeners in a forced-choice experiment, controlling for tempo, range, and mode.

Falsification criterion: A controlled listening study presenting pairs of L-system melodies matched on $d_H$ but differing in production rules finds a statistically significant preference for one over the other, or a significant difference in perceived complexity ratings (e.g., $p < 0.05$ on a paired $t$ -test). Such a result would demonstrate that $d_H$ is not the relevant perceptual invariant, motivating a search for a dimensionless musical complexity measure beyond fractal geometry.

Golden ratio in composition: design or coincidence? The appearances of $\varphi$ in analyses of Bartók, Debussy, and others (Lendvai 1971; Howat 1983) remain contested. Without access to compositional sketches or explicit composer statements, it is impossible to distinguish deliberate golden-section planning from the analyst’s selection bias (finding $\varphi$ where Fibonacci-approximated phrase lengths happen to appear).

Academic References / 参考文献

Lindenmayer, A. (1968). Mathematical models for cellular interactions in development, Parts I and II. Journal of Theoretical Biology 18(3), 280–315.
Prusinkiewicz, P. & Lindenmayer, A. (1990). The Algorithmic Beauty of Plants. Springer-Verlag, New York. Free PDF: http://algorithmicbotany.org/papers/
Prusinkiewicz, P. & Hanan, J. (1989). Lindenmayer Systems, Fractals, and Plants. Lecture Notes in Biomathematics 79. Springer.
Mandelbrot, B. B. (1982). The Fractal Geometry of Nature. W.H. Freeman, New York.
Falconer, K. (2003). Fractal Geometry: Mathematical Foundations and Applications, 2nd ed. Wiley.
Lendvai, E. (1971). Béla Bartók: An Analysis of His Music. Kahn & Averill, London.
Howat, R. (1983). Debussy in Proportion: A Musical Analysis. Cambridge University Press.
Steinhaus, H. (1950). Sur la division des segments. Colloquium Mathematicae 2, 298–302. (Origin of the three-distance theorem.)
Slater, N. B. (1950). The distribution of the integers $N$ for which $\{\theta N\} < \phi$ . Proceedings of the Cambridge Philosophical Society 46(4), 525–534.
Johnson, T. A. (1996). Applying Klee’s “Pedagogical Sketchbook” to the Analysis of Music. Music Theory Spectrum 18(2), 190–208.
Hsü, K. J. & Hsü, A. J. (1990). Fractal geometry of music. Proceedings of the National Academy of Sciences 87(3), 938–941.
Brothers, H. J. (2007). Structural scaling in Bach’s cello suite no. 3. Fractals 15(1), 89–95.
Rozenberg, G. & Salomaa, A. (Eds.) (1980). The Mathematical Theory of L Systems. Academic Press.
Allouche, J.-P. & Shallit, J. (2003). Automatic Sequences: Theory, Applications, Generalizations. Cambridge University Press. Ch. 1–2 (morphisms and fixed points of parallel rewriting).
Voss, R. F. & Clarke, J. (1975). “1/f noise” in music and speech. Nature 258, 317–318.