38.02.01 · dynamics / symbolic-dynamics

Shift Spaces and Subshifts

shipped3 tiersLean: none

Anchor (Master): Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 1–6 (shift spaces, languages, sliding-block codes, sofic shifts, the conjugacy theory); Brin-Stuck 2002 *Introduction to Dynamical Systems* (Cambridge) Ch. 3; Kitchens 1998 *Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts* (Springer Universitext); Hedlund 1969 *Endomorphisms and automorphisms of the shift dynamical system* (Math. Systems Theory 3) — the originating paper for cellular automata as shift-commuting maps

Intuition Beginner

Imagine writing down what a moving system is doing by recording only a coarse summary at each tick of the clock. You partition the space into a few labelled regions, and at every step you write down the label of the region the system is sitting in. A trajectory becomes a string of symbols — a flight of letters drawn from a small alphabet — and the original complicated motion becomes the much simpler act of reading that string one letter at a time. Symbolic dynamics studies these strings as objects in their own right, and the surprising payoff is that the messy geometry of a chaotic system often becomes the tidy combinatorics of a list of letters.

The clock keeps ticking, so the natural motion on strings is to slide your reading window one place to the right: forget the first letter and start from the second. This sliding is the shift. Watching a string under repeated shifting is the symbolic version of watching a point move under the original rule. The whole space of all possible strings, with the shift acting on it, is the full shift — the universe of every conceivable record.

Not every string can actually occur. A real system may forbid certain short patterns: maybe a $1$ can never be immediately followed by another $1$ . The strings that avoid every forbidden pattern form a smaller world sitting inside the full shift, called a subshift. The single most useful fact of the subject is that a subshift is completely pinned down by its list of banned words — its grammar. To describe a symbolic system you do not draw a picture; you write down its forbidden words.

Visual Beginner

Picture a long strip of boxes stretching out to the right, each box holding a single $0$ or $1$ . That is one point of the full shift on two symbols: an endless binary record. The shift slides the whole strip one box to the left, so the second box becomes the first and the rest follow.

To the side sits a tiny rule-graph: two circles labelled $0$ and $1$ with arrows showing which letter may follow which. An arrow from $0$ to $0$ , from $0$ to $1$ , and from $1$ to $0$ , but no arrow from $1$ back to $1$ . Strings that only ever walk along arrows of this graph are exactly the strings with no two consecutive ones — the golden-mean subshift. The table below contrasts the full shift with this subshift.

feature	full shift on two symbols	golden-mean subshift
alphabet	the letters $0$ and $1$	the letters $0$ and $1$
allowed strings	every string	strings with no $1$ next to a $1$
forbidden words	none	the single word $11$
the move	slide one box left	slide one box left
how many length- $n$ strings	$2$ to the power $n$	the $n$ -th Fibonacci-type count

Worked example Beginner

Let us count how many short strings the golden-mean subshift allows. The rule is simple: a string is allowed when it never contains two ones in a row. We count allowed strings of each length.

Step 1. Length $1$ . The allowed strings are $0$ and $1$ . That is $2$ strings.

Step 2. Length $2$ . Write all four binary pairs: $00, 01, 10, 11$ . The pair $11$ has two ones in a row, so it is banned. The allowed pairs are $00, 01, 10$ . That is $3$ strings.

Step 3. Length $3$ . Extend each allowed length- $2$ string by one more letter, keeping only extensions that do not create a $11$ . From $00$ we may add $0$ or $1$ , giving $000$ and $001$ . From $01$ we may add only $0$ (adding $1$ would make $011$ ), giving $010$ . From $10$ we may add $0$ or $1$ , giving $100$ and $101$ . The allowed length- $3$ strings are $000, 001, 010, 100, 101$ . That is $5$ strings.

Step 4. Spot the pattern. The counts are $2, 3, 5$ . Each count is the sum of the two before it: indeed length $4$ gives $3 + 5 = 8$ . These are the Fibonacci numbers. The reason is that an allowed string either ends in $0$ (and anything allowed can come before it) or ends in $01$ (forced, because before a final $1$ must come a $0$ ).

What this tells us: a single banned word, $11$ , already produces a rich counting law. The number of allowed strings grows like the Fibonacci sequence, at a rate governed by the golden ratio — which is exactly why this little system is named the golden-mean subshift. Forbidding one short pattern shapes the entire long-run combinatorics.

Check your understanding Beginner

Exercise (easy, multiple choice).

The shift applied to a sequence of symbols does which of the following?

A. Reverses the order of all the symbols. B. Replaces every symbol by the next letter of the alphabet. C. Drops the first symbol and moves every later symbol one place earlier. D. Sorts the symbols into increasing order.

Hint

Think of reading a tape one tick at a time: after one tick, where does the reading window point?

Answer

C. The shift slides the reading window one place along: the symbol that was in position one is forgotten, and every later symbol moves one place earlier. Feedback-correct: this sliding is the symbolic stand-in for one tick of the original system's clock. Feedback-wrong: the shift does not reverse, relabel, or sort the symbols — it only translates the sequence.

Formal definition Intermediate+

Fix a finite set $A$ with at least two elements, the alphabet. The full shift over $A$ is the sequence space $A^{Z} = {x = (x_{n})_{n \in Z} : x_{n} \in A}$ (the two-sided shift) or $A^{N} = {x = (x_{n})_{n \geq 0}}$ (the one-sided shift). Either is given the product topology, the coarsest topology making every coordinate projection $x \mapsto x_{n}$ continuous when $A$ carries the discrete topology. This topology is induced by the metric $$ d(x,y) = 2^{-\min{ |n| ,:, x_n \neq y_n }}, \qquad d(x,x) = 0, $$ with the convention that the minimum over the empty set is $+ \infty$ . Two sequences are close exactly when they agree on a long central block; this is the shift metric of 38.01.01, here taken as the defining datum.

For a finite word (or block) $w = w_{0} w_{1} \dots w_{k - 1} \in A^{k}$ and an index $i$ , the cylinder set $$ [w]i = { x \in A^{\mathbb{Z}} : x{i+j} = w_j \text{ for } 0 \le j < k } $$ is the set of sequences carrying the word $w$ starting at position $i$ . Cylinder sets are simultaneously open and closed (clopen), and they form a basis for the product topology.

Definition (shift map). The shift $σ : A^{Z} \to A^{Z}$ is $(σ x)_{n} = x_{n + 1}$ . On the two-sided shift $σ$ is a homeomorphism; on the one-sided shift $σ$ is a continuous, surjective, $∣ A ∣$ -to-one map.

Definition (subshift). A subshift (or shift space) is a subset $X \subseteq A^{Z}$ that is closed (in the product topology) and shift-invariant ( $σ (X) = X$ ). The pair $(X, σ ∣_{X})$ is a topological dynamical system in the sense of 38.01.01, and the full shift is the case $X = A^{Z}$ .

Definition (forbidden words and the language). For a set $F \subseteq A^{*} = ⋃_{k \geq 0} A^{k}$ of finite words, let $$ \mathsf{X}{\mathcal{F}} = { x \in A^{\mathbb{Z}} : \text{no word of } \mathcal{F} \text{ occurs in } x }, $$ the sequences avoiding every word of $F$ . Conversely, the language of a subset $X$ is $$ \mathcal{L}(X) = { w \in A^* : w \text{ occurs in some } x \in X }, $$ the set of words that actually appear. A word occurs in $x$ if $x{i} \cdots x_{i+k-1} = w $f or so m e$ i$.

Definition (subshift of finite type). A subshift $X$ is of finite type (an SFT) if $X = X_{F}$ for some finite $F$ . A subshift is sofic if it is the image of an SFT under a sliding-block code (defined below). When $F$ consists of length- $2$ words, $X$ is a topological Markov chain: it is described by a $0/1$ transition matrix $T$ over $A$ , with $T_{ab} = 1$ iff the word $ab$ is allowed, and $X = {x : T_{x_{n} x_{n + 1}} = 1 for all n}$ . This $0/1$ matrix is the topological analogue of the stochastic transition matrix of a Markov chain 37.05.02: where the stochastic matrix records the probability of $a \to b$ , the transition matrix records merely whether $a \to b$ is permitted, and the irreducibility and period notions transfer verbatim to the support graph.

Definition (sliding-block code). Let $X \subseteq A^{Z}$ and $Y \subseteq B^{Z}$ be subshifts. Fix integers $- m \leq a \leq 0 \leq m$ (a window $[- m, m]$ ) and a block map $Φ : L_{2 m + 1} (X) \to B$ on the allowed words of length $2 m + 1$ . The induced map $ϕ : X \to Y$ , $$ (\phi x)n = \Phi(x{n-m} , x_{n-m+1} \cdots x_{n+m}), $$ is a sliding-block code (with memory and anticipation $m$ ). A sliding-block code commutes with the shift by construction: $ϕ \circ σ = σ \circ ϕ$ .

A sign / index convention. Coordinates run over $Z$ with $(σ x)_{n} = x_{n + 1}$ (the shift moves the window forward in time, equivalently translates the sequence to the left), and the metric weights disagreements by $2^{- ∣ n ∣}$ so that agreement on the central block $[- N, N]$ forces $d (x, y) \leq 2^{- (N + 1)}$ . This matches Lind-Marcus and Brin-Stuck; the one-sided shift uses $∣ n ∣ = n \geq 0$ throughout.

Counterexamples to common slips

Forbidden-word sets are far from unique. The golden-mean subshift is $X_{{11}}$ but also $X_{{11, 111, 0110}}$ — adding already-impossible words changes nothing. The canonical invariant is the language $L (X)$ , not any particular $F$ .
Not every closed invariant set is of finite type. The even subshift (blocks of zeros between successive ones always have even length) needs the infinite forbidden list ${1 0^{2 k + 1} 1 : k \geq 0}$ ; no finite list defines it. It is sofic but not an SFT.
Shift-invariance must be two-sided for the two-sided shift. A subshift requires $σ (X) = X$ , not merely $σ (X) \subseteq X$ . The forward orbit closure of a single non-periodic point need not be shift-invariant unless one takes the full bi-infinite orbit closure.
A subshift can be empty. If $F$ forbids every letter of $A$ as a length- $1$ word, $X_{F} = \emptyset$ . Non-emptiness is a real hypothesis, guaranteed when every long word extends to a longer allowed word (the extension property).

Key theorem with proof Intermediate+

Theorem (characterisation of subshifts; Curtis-Hedlund-Lyndon). Let $A$ be a finite alphabet.

(a) A subset $X \subseteq A^{Z}$ is a subshift (closed and shift-invariant) if and only if $X = X_{F}$ for some set of forbidden words $\mathcal{F} \subseteq A^$.*

(b) A map $ϕ : X \to Y$ between subshifts is continuous and shift-commuting ( $ϕ \circ σ = σ \circ ϕ$ ) if and only if $ϕ$ is a sliding-block code.

(See ^{[Lind-Marcus 1995 Ch. 1–2]}, ^{[Brin-Stuck 2002 §3.2]}, ^{[Hedlund 1969]}.)

Proof. Write $A^{Z}$ with the shift metric and product topology throughout; recall that cylinder sets are clopen and that $A^{Z}$ is compact, being a product of finite discrete spaces (Tychonoff).

Part (a), " $\Leftarrow$ ". Let $X = X_{F}$ . Shift-invariance is immediate: $x$ avoids every word of $F$ iff $σ x$ does, since the occurrences of a word in $σ x$ are exactly the occurrences in $x$ shifted by one index. For closedness, fix $w \in F$ of length $k$ and let $U_{w} = {x : w occurs in x} = ⋃_{i \in Z} [w]_{i}$ , a union of open cylinder sets, hence open. Then $X_{F} = A^{Z} ∖ ⋃_{w \in F} U_{w}$ is the complement of an open set, hence closed.

Part (a), " $\Rightarrow$ ". Let $X$ be closed and shift-invariant. Let $F = A^{*} ∖ L (X)$ be the set of words that occur in no point of $X$ . We show $X = X_{F}$ . The inclusion $X \subseteq X_{F}$ holds because every word occurring in a point of $X$ lies in $L (X)$ , so no point of $X$ contains a word of $F$ . For the reverse, take $x \in X_{F}$ ; every finite central block $x_{- N} \dots x_{N}$ lies in $L (X)$ , so there is a point $y^{(N)} \in X$ in which this block occurs, and after applying a power of $σ$ (using invariance) we may place the block at the centre, giving $z^{(N)} \in X$ with $z_{j}^{(N)} = x_{j}$ for $∣ j ∣ \leq N$ . Then $d (z^{(N)}, x) \leq 2^{- (N + 1)} \to 0$ , so $z^{(N)} \to x$ ; since $X$ is closed, $x \in X$ . Hence $X_{F} \subseteq X$ , and the two sets coincide.

Part (b), " $\Leftarrow$ ". A sliding-block code with window $[- m, m]$ commutes with the shift by construction, $(ϕ σ x)_{n} = Φ ((σ x)_{n - m} \dots (σ x)_{n + m}) = Φ (x_{n + 1 - m} \dots x_{n + 1 + m}) = (ϕ x)_{n + 1} = (σ ϕ x)_{n}$ . Continuity: if $x, x^{'}$ agree on $[- (N + m), N + m]$ then $ϕ x, ϕ x^{'}$ agree on $[- N, N]$ , since each output coordinate in that range depends only on input coordinates within $m$ of it; thus $d (x, x^{'}) \leq 2^{- (N + m + 1)} \Rightarrow d (ϕ x, ϕ x^{'}) \leq 2^{- (N + 1)}$ , which is (uniform) continuity.

Part (b), " $\Rightarrow$ ". Let $ϕ : X \to Y$ be continuous and shift-commuting. The coordinate map $Ψ : X \to B$ , $Ψ (x) = (ϕ x)_{0}$ , is continuous on the compact space $X$ , hence uniformly continuous: there is $m$ such that $d (x, x^{'}) \leq 2^{- m}$ implies $Ψ (x) = Ψ (x^{'})$ (the target $B$ is discrete, so "within $2^{- 1}$ " means "equal"). But $d (x, x^{'}) \leq 2^{- m}$ means $x, x^{'}$ agree on the window $[- m, m]$ , so $Ψ (x)$ depends only on $x_{- m} \dots x_{m}$ . This defines a block map $Φ : L_{2 m + 1} (X) \to B$ with $Ψ (x) = Φ (x_{- m} \dots x_{m})$ . Shift-commutation transports this to every coordinate: $(ϕ x)_{n} = (σ^{n} ϕ x)_{0} = (ϕ σ^{n} x)_{0} = Ψ (σ^{n} x) = Φ (x_{n - m} \dots x_{n + m})$ . So $ϕ$ is the sliding-block code of $Φ$ . $□$

Bridge. The characterisation theorem builds toward the entire structure theory of symbolic systems and appears again in every classification result of the subject, because once a subshift is known to be a closed invariant set cut out by forbidden words, the conjugacy problem becomes a question about languages and codes rather than about points. The foundational reason both halves hold is the same compactness-plus-locality principle: a finite alphabet makes $A^{Z}$ compact, and the discrete target turns continuity into a finite window of dependence, so global maps are local rules. This is exactly the bridge from 38.01.01: the doubling map seen through binary coding is the one-sided full shift, and conjugacies of the doubling map are sliding-block codes of the shift. The Curtis-Hedlund-Lyndon theorem generalises the elementary observation that the shift commutes with itself, and it is dual to the forbidden-word characterisation — one describes the objects (subshifts as languages), the other the morphisms (codes as local rules) of the category of symbolic systems. The central insight is that symbolic dynamics is the combinatorics of finite words made into a topological dynamical system, and putting these together gives the working definition of "the same symbolic system": a conjugacy is an invertible sliding-block code, and the entire conjugacy theory of the next units rests on this identification.

Exercises Intermediate+

Exercise 4 (medium, symbolic).

Show that the shift $σ$ on the full shift $A^{Z}$ is expansive: there is a constant $c > 0$ such that for any two distinct points $x \neq = y$ there is some $n \in Z$ with $d (σ^{n} x, σ^{n} y) \geq c$ .

Hint

If $x \neq = y$ they disagree at some coordinate $k$ ; apply $σ^{k}$ to move that disagreement to coordinate $0$ .

Answer

Take $c = 1$ . If $x \neq = y$ , there is an index $k$ with $x_{k} \neq = y_{k}$ . Then $(σ^{k} x)_{0} = x_{k} \neq = y_{k} = (σ^{k} y)_{0}$ , so $σ^{k} x$ and $σ^{k} y$ disagree at coordinate $0$ , whence $d (σ^{k} x, σ^{k} y) = 2^{- 0} = 1 \geq c$ . Thus distinct orbits are separated by a fixed amount at some time, which is expansiveness with constant $1$ . (Expansiveness is the symbolic-dynamics signature: the shift sees every coordinate eventually, so no two distinct sequences shadow each other forever.) Rubric: full credit for moving the disagreement to coordinate $0$ and concluding $d = 1$ .

Exercise 5 (medium, short-answer).

Prove that the full shift $A^{Z}$ has dense periodic points: the periodic points of $σ$ are dense in $A^{Z}$ .

Hint

Given a point $x$ and a central window, periodically repeat the window to build a periodic point that agrees with $x$ on it.

Answer

Let $x \in A^{Z}$ and $N \geq 0$ . Let $w = x_{- N} x_{- N + 1} \dots x_{N}$ , a word of length $2 N + 1$ . Define $y \in A^{Z}$ to be the bi-infinite periodic repetition of $w$ , with the central copy placed on $[- N, N]$ ; then $σ^{2 N + 1} y = y$ , so $y$ is periodic, and $y_{j} = x_{j}$ for $∣ j ∣ \leq N$ , so $d (y, x) \leq 2^{- (N + 1)}$ . As $N \to \infty$ these periodic points converge to $x$ . Since $x$ was arbitrary, the periodic points are dense. (The same construction works inside any subshift that contains the periodic repetition of each of its allowed central blocks — for SFTs this holds once the block extends both ways.) Rubric: full credit for the periodic-repetition construction and the metric estimate.

Exercise 6 (medium, short-answer).

Let $T$ be the $0/1$ transition matrix of the golden-mean shift on $A = {0, 1}$ , so $T = (1110)$ (rows/columns indexed $0, 1$ ; $T_{ab} = 1$ iff $ab$ is allowed). Show that the number of allowed words of length $n$ equals the sum of the entries of $T^{n - 1}$ , and connect this to 37.05.02.

Hint

An allowed word of length $n$ is a path of length $n - 1$ in the directed graph with adjacency matrix $T$ ; count paths by powers of $T$ .

Answer

An allowed word $a_{0} a_{1} \dots a_{n - 1}$ is exactly a walk $a_{0} \to a_{1} \to \dots \to a_{n - 1}$ in the graph whose adjacency matrix is $T$ , since each step requires $T_{a_{i} a_{i + 1}} = 1$ . The number of walks of length $n - 1$ from $a$ to $b$ is $(T^{n - 1})_{ab}$ , so the total number of allowed length- $n$ words is $\sum_{a, b} (T^{n - 1})_{ab} = 1^{⊤} T^{n - 1} 1$ . For the golden-mean $T$ this gives the Fibonacci counts, and the growth rate is the Perron eigenvalue $φ = \frac{1 + 5}{2}$ , whose logarithm is the topological entropy. This is the $0/1$ analogue of 37.05.02: there the stochastic matrix's powers $P^{n}$ count probability-weighted paths and its support graph governs irreducibility and period; here the same support graph governs which symbolic words exist, with the Perron-Frobenius eigenvalue measuring complexity instead of mixing rate. Rubric: full credit for the walk-counting bijection and the Perron-eigenvalue / entropy connection.

Exercise 7 (hard, short-answer).

Prove that the even subshift $X_{even} \subseteq {0, 1}^{Z}$ — the set of sequences in which every maximal block of $0$ s flanked by $1$ s has even length — is not a subshift of finite type, but is sofic.

Hint

For the SFT impossibility, suppose forbidden words have length $\leq M$ and exhibit an allowed-looking but illegal point. For sofic, present a finite labelled graph (two states) whose label-sequences are exactly $X_{even}$ .

Answer

Not SFT. Suppose $X_{even} = X_{F}$ with every word of $F$ of length $\leq M$ . Consider $x = \dots 1 0^{2 M + 1} 1 \dots$ (a single odd block of $0$ s of length $2 M + 1$ between two ones, all other symbols chosen legally). Every subword of $x$ of length $\leq M$ also occurs in some genuinely even-block point — a window of length $\leq M$ can never see both flanking $1$ s of the long odd block, so it is consistent with an even configuration — hence no word of $F$ occurs in $x$ , giving $x \in X_{F}$ . But $x \in / X_{even}$ because it has an odd $0$ -block. This contradiction shows no finite $F$ works. Sofic. Take the labelled graph with two states ${e, o}$ (even/odd parity of the current $0$ -run since the last $1$ ): edges $e 1 e$ , $e 0 o$ , $o 0 e$ , and the $1$ -edge permitted only from $e$ ( $e 1 e$ ), forbidding a $1$ from the odd state. The bi-infinite label sequences of walks on this graph are exactly $X_{even}$ , presenting it as the image of the underlying SFT (the edge shift) under the label map, a sliding-block code. Hence $X_{even}$ is sofic but not of finite type. Rubric: full credit for the long-odd-block contradiction and the explicit two-state presentation.

Exercise 8 (hard, short-answer).

Let $α \in (0, 1)$ be irrational and code the rotation $R_{α} (t) = t + α mod 1$ on the circle by the partition $I_{0} = [0, 1 - α)$ , $I_{1} = [1 - α, 1)$ , setting $c (t)_{n} = 1 [R_{α}^{n} (t) \in I_{1}]$ . Show the orbit closure $X_{α} = \overline{{σ^{n} c (t) : n \in Z}}$ is a subshift in which exactly $n + 1$ words of length $n$ occur (a Sturmian subshift), and explain why it is minimal.

Hint

The number of length- $n$ words equals the number of arcs into which the $n$ partition-boundary preimages cut the circle; $n$ irrational points plus the original boundary give $n + 1$ arcs. Minimality follows from minimality of an irrational rotation.

Answer

A length- $n$ word of the coding $c (t)$ is determined by which side of the partition the points $t, R_{α} t, \dots, R_{α}^{n - 1} t$ fall on, i.e. by the cell of the circle cut out by the $n$ boundary preimages $R_{α}^{- j} (1 - α)$ , $j = 0, \dots, n - 1$ (together with the boundary $0$ ). These $n$ points are distinct (irrationality of $α$ ), so they partition the circle into exactly $n$ arcs; including the partition point $1 - α$ 's own preimage bookkeeping, the count of distinct length- $n$ codings is $n + 1$ . A subshift with word-complexity $p (n) = n + 1$ is by definition Sturmian — the minimal complexity of any non-eventually-periodic sequence (Morse-Hedlund: $p (n) \leq n$ for some $n$ forces eventual periodicity). The orbit closure $X_{α}$ is closed and shift-invariant, hence a subshift. Minimality: an irrational rotation is minimal (every orbit dense), and the coding semiconjugates $(S^{1}, R_{α})$ onto $(X_{α}, σ)$ off the countable set of boundary-hitting orbits; density of every rotation orbit transports to density of every shift orbit in $X_{α}$ , so $X_{α}$ has no proper non-empty closed invariant subset. Rubric: full credit for the $n + 1$ arc-count, the Sturmian definition, and the minimality-from-rotation argument.

Advanced results Master

Theorem (the full shift is a Cantor set; $σ$ is the model expansive system). For a finite alphabet $A$ with $∣ A ∣ \geq 2$ , the full shift $A^{Z}$ with the shift metric is a compact, perfect, totally disconnected metric space — a Cantor set — and the shift $σ$ is a homeomorphism that is expansive with constant $1$ , has $∣ A ∣^{n}$ points of period dividing $n$ , dense periodic points, and a dense orbit (topological transitivity), hence is chaotic in the sense of Devaney. (See ^{[Lind-Marcus 1995 Ch. 6]}, ^{[Kitchens 1998 Ch. 1]}.)

Compactness is Tychonoff applied to the finite discrete factors; perfectness is the observation that every cylinder contains at least two points once $∣ A ∣ \geq 2$ , so no point is isolated; total disconnectedness follows from the clopen cylinder basis, since any two points are separated by a clopen set. The standard topological characterisation of the Cantor set as the unique non-empty compact, perfect, totally disconnected, metrizable space identifies $A^{Z}$ with the middle-thirds Cantor set as a topological space. The dynamical content lies entirely in $σ$ : expansiveness says the symbol sequence is a complete invariant of the orbit, dense periodic points come from periodic repetition of central blocks, and a transitive point is built by concatenating an enumeration of all finite words. Every expansive homeomorphism of a Cantor set is, by a theorem of Hedlund-type coding, a subshift, so the full shift and its subshifts exhaust the expansive Cantor systems up to conjugacy.

Theorem (subshifts of finite type and the topological Markov chain). A subshift $X$ is of finite type iff, after recoding to a higher block alphabet, $X$ is a vertex/edge shift of a finite directed graph; equivalently $X$ is described by a $0/1$ transition matrix $T$ . The topological entropy is $h (X) = lo g λ_{T}$ , where $λ_{T}$ is the Perron eigenvalue (spectral radius) of $T$ , and the number of period- $n$ points is $tr (T^{n})$ . (Lind-Marcus 1995 ^{[Lind-Marcus 1995 Ch. 4]}.)

The recoding to length- $N$ blocks turns any SFT with forbidden words of length $\leq N$ into a Markov ( $1$ -step) SFT on the alphabet of allowed $(N - 1)$ -blocks, so finite type is exactly "memory of bounded length". The transition matrix $T$ is the $0/1$ shadow of the stochastic matrix in 37.05.02: irreducibility of $T$ (strong connectedness of its graph) makes the SFT topologically transitive, and the period of $T$ (the gcd of its cycle lengths) is the symbolic period; a primitive $T$ gives a mixing SFT. The Perron-Frobenius eigenvalue $λ_{T}$ governs growth of the word count exactly as it governs the convergence rate of the stochastic chain, and $tr (T^{n}) = \sum_{i} λ_{i}^{n}$ counts period- $n$ points through the matrix's whole spectrum, the zeta function $ζ_{σ} (t) = exp \sum_{n} \frac{tr ( T ^{n} )}{n} t^{n} = det (I - tT)^{- 1}$ being rational.

Theorem (sofic shifts and the Krieger cover). The sofic shifts are exactly the factors of subshifts of finite type under sliding-block codes; equivalently they are the sets of label-sequences of finite labelled graphs. Every irreducible sofic shift has a unique minimal deterministic presentation, the Krieger (future) cover. Sofic but non-SFT shifts exist, the even shift being the canonical example. (Lind-Marcus 1995 ^{[Lind-Marcus 1995 §3.2, Ch. 3]}.)

A sofic shift records a regular language of allowed words in the sense of automata theory — the connection that makes symbolic dynamics and finite-state machines two views of one subject — while an SFT records the special regular languages defined by a finite list of forbidden factors. The Krieger cover is the minimal automaton recognising the language read backwards-deterministically; its existence and uniqueness make the sofic class as tractable as the SFT class for entropy and zeta-function computations, even though the even shift shows the SFT-defining property of bounded memory genuinely fails.

Theorem (Sturmian subshifts and the Morse-Hedlund complexity bound). For a bi-infinite sequence $x$ over a finite alphabet, let $p_{x} (n) = ∣ L_{n} (\overline{O (x)}) ∣$ be its word complexity. If $p_{x} (n) \leq n$ for some $n$ , then $x$ is eventually periodic. The aperiodic sequences of minimal complexity satisfy $p_{x} (n) = n + 1$ for all $n$ ; these are the Sturmian sequences, realised as codings of irrational circle rotations by a two-interval partition, and their orbit closures are minimal subshifts. (Morse-Hedlund 1938/1940 ^{[Morse-Hedlund 1938]}.)

The complexity function $p_{x}$ is non-decreasing, and the dichotomy " $p_{x} (n) \leq n$ once" versus " $p_{x} (n) \geq n + 1$ always" is sharp: periodicity is exactly bounded complexity, while $p_{x} (n) = n + 1$ is the slimmest possible aperiodic growth. Sturmian sequences are simultaneously the mechanical words $⌊(n + 1) α + ρ ⌋ - ⌊ n α + ρ ⌋$ , the cutting sequences of lines of irrational slope across the integer grid, and the symbolic codings of rotations — three faces of one minimal system, the symbolic counterpart of the irrational rotation that served as the model minimal system in 38.01.01.

Synthesis. The four theorems are one architecture seen at four resolutions. The central insight is that a symbolic dynamical system is its language: the forbidden-word characterisation makes a subshift a closed invariant set, the Curtis-Hedlund-Lyndon theorem makes its morphisms local rules, and putting these together the entire category of symbolic systems is the combinatorics of finite words promoted to topological dynamics. This is exactly the bridge from 38.01.01: the doubling map, the horseshoe, and the hyperbolic toral automorphism all reduce to shifts by symbolic coding, so the Cantor-set full shift is the universal model of chaotic recurrence, and its subshifts catalogue the possible chaotic behaviours.

The finite-type and sofic theory is dual to the automata-theoretic hierarchy — SFTs are the bounded-memory languages, sofic shifts the regular languages — and the foundational reason the Perron-Frobenius eigenvalue governs both entropy here and mixing in 37.05.02 is that the $0/1$ transition matrix is the support shadow of the stochastic matrix, so topological and measured Markov dynamics share one combinatorial skeleton. The Sturmian shifts generalise the minimal irrational rotation into the symbolic world and sit at the opposite extreme from the full shift: minimal complexity against maximal, a single low-entropy minimal system against the universal positive-entropy model, both read off from the same word-complexity invariant. The bridge to the conjugacy theory of the next units is the recognition that a topological conjugacy of subshifts is an invertible sliding-block code, so the classification of symbolic systems is the classification of languages up to recoding — the central insight that organises everything downstream.

Full proof set Master

Proposition 1 (the shift metric induces the product topology). On $A^{Z}$ with $A$ finite discrete, the metric $d (x, y) = 2^{- m i n {∣ n ∣ : x_{n} \neq = y_{n}}}$ induces the product topology, and the cylinder sets are a clopen basis.

Proof. A basic open set of the product topology fixes finitely many coordinates, hence contains a cylinder $[w]_{- N} \cap \dots$ specifying $x_{j}$ for $∣ j ∣ \leq N$ ; this cylinder equals the metric ball ${y : d (x, y) \leq 2^{- (N + 1)}} = {y : y_{j} = x_{j} for ∣ j ∣ \leq N}$ , which is therefore open in the metric. Conversely each metric ball is such a cylinder, so the two topologies have the same basis and coincide. Each cylinder is open (just shown) and closed (its complement is the finite union of the other cylinders specifying the same coordinate block, each open), hence clopen. $□$

Proposition 2 (the shift is a homeomorphism; expansiveness). On the two-sided full shift, $σ$ is a homeomorphism, and $σ$ is expansive with constant $1$ .

Proof. The inverse is $(σ^{- 1} x)_{n} = x_{n - 1}$ , manifestly two-sided inverse to $σ$ . Continuity of $σ$ and $σ^{- 1}$ : if $x, y$ agree on $[- (N + 1), N + 1]$ then $σ x, σ y$ agree on $[- N, N]$ (a single index of slack at each end suffices), so $σ$ is $1$ -Lipschitz up to the factor $2$ and in particular continuous; the same for $σ^{- 1}$ . Expansiveness: if $x \neq = y$ choose $k$ with $x_{k} \neq = y_{k}$ ; then $(σ^{k} x)_{0} \neq = (σ^{k} y)_{0}$ gives $d (σ^{k} x, σ^{k} y) = 1$ . $□$

Proposition 3 (a sliding-block code is exactly a continuous shift-commuting map — the local half). Every sliding-block code $ϕ : X \to Y$ is continuous and satisfies $ϕ \circ σ = σ \circ ϕ$ .

Proof. Shift-commutation: with window $[- m, m]$ and block map $Φ$ , $(ϕ σ x)_{n} = Φ ((σ x)_{n - m} \dots (σ x)_{n + m}) = Φ (x_{n + 1 - m} \dots x_{n + 1 + m}) = (ϕ x)_{n + 1} = (σ ϕ x)_{n}$ . Continuity: each output coordinate $(ϕ x)_{n}$ depends only on $x_{n - m}, \dots, x_{n + m}$ , so if $x, x^{'}$ agree on $[- (N + m), N + m]$ then $ϕ x, ϕ x^{'}$ agree on $[- N, N]$ , giving $d (x, x^{'}) \leq 2^{- (N + m + 1)} \Rightarrow d (ϕ x, ϕ x^{'}) \leq 2^{- (N + 1)}$ . $□$

Proposition 4 (continuous shift-commuting maps are local — the global half of Curtis-Hedlund-Lyndon). If $ϕ : X \to Y$ is continuous and $ϕ \circ σ = σ \circ ϕ$ , then $ϕ$ is a sliding-block code.

Proof. The zero-coordinate evaluation $Ψ (x) = (ϕ x)_{0}$ is continuous into the discrete finite set $B$ , and $X$ is compact, so $Ψ$ is uniformly continuous: there is $m$ with $d (x, x^{'}) < 2^{- m + 1}$ (agreement on $[- m, m]$ ) forcing $Ψ (x) = Ψ (x^{'})$ , since distinct symbols are at distance $\geq 1$ in the discrete target. Hence $Ψ (x)$ is a function $Φ$ of the window $x_{- m} \dots x_{m}$ alone. By shift-commutation, $(ϕ x)_{n} = (σ^{n} ϕ x)_{0} = (ϕ σ^{n} x)_{0} = Ψ (σ^{n} x) = Φ (x_{n - m} \dots x_{n + m})$ , so $ϕ$ is the sliding-block code of $Φ$ with window $[- m, m]$ . $□$

Proposition 5 (forbidden-word characterisation; closed invariant equals avoidance set). A subset $X \subseteq A^{Z}$ is closed and shift-invariant iff $X = X_{F}$ for $\mathcal{F} = A^ \setminus \mathcal{L}(X)$.*

Proof. If $X = X_{F}$ then $X$ is closed (complement of the open set $⋃_{w \in F} ⋃_{i} [w]_{i}$ ) and invariant (avoidance is shift-stable). Conversely, for closed invariant $X$ put $F = A^{*} ∖ L (X)$ . Then $X \subseteq X_{F}$ since words occurring in $X$ lie in $L (X)$ . For $X_{F} \subseteq X$ : given $x \in X_{F}$ , each central block $x_{- N} \dots x_{N} \in L (X)$ occurs in some point of $X$ ; shift-invariance recentres it to give $z^{(N)} \in X$ agreeing with $x$ on $[- N, N]$ , so $z^{(N)} \to x$ and closedness yields $x \in X$ . $□$

Proposition 6 (period-point count of an SFT). For a subshift of finite type with $0/1$ transition matrix $T$ (after recoding to a $1$ -step presentation), the number of points $x$ with $σ^{n} x = x$ equals $tr (T^{n})$ , and the topological entropy is $lo g λ_{T}$ with $λ_{T}$ the Perron eigenvalue of $T$ .

Proof. A point of period $n$ is a periodic bi-infinite sequence $\overline{a_{0} a_{1} \dots a_{n - 1}}$ with $T_{a_{i} a_{i + 1}} = 1$ (indices mod $n$ ); these are exactly the closed walks of length $n$ in the graph of $T$ , and the number of closed walks of length $n$ at vertex $i$ is $(T^{n})_{ii}$ , so the total is $\sum_{i} (T^{n})_{ii} = tr (T^{n})$ . For entropy, the number of allowed length- $n$ words is $1^{⊤} T^{n - 1} 1$ , which grows like $λ_{T}^{n}$ by Perron-Frobenius (for irreducible $T$ ), so $h (X) = lim_{n} \frac{1}{n} lo g (# L_{n} (X)) = lo g λ_{T}$ . $□$

Connections Master

Dynamical systems, orbits, and limit sets 38.01.01. Symbolic dynamics is the construction promised in the bridge of the foundational unit: the doubling map is conjugate (off the dyadic rationals) to the one-sided full shift, the Smale horseshoe is conjugate to the two-sided full shift on two symbols, and the cat map admits a Markov-partition coding into a subshift of finite type. The orbit, limit-set, and topological-conjugacy apparatus defined there specialises to the shift, and the present unit supplies the combinatorial models — full shift, SFT, sofic, Sturmian — that classify the recurrent behaviour catalogued abstractly there.
Class structure, irreducibility, and periodicity of Markov chains 37.05.02. The $0/1$ transition matrix of a subshift of finite type is the topological shadow of the stochastic transition matrix studied there: communication classes, irreducibility, and the gcd-of-cycle-lengths period transfer verbatim from the stochastic matrix to its support graph, with topological transitivity replacing irreducibility and the mixing SFT corresponding to a primitive matrix. Where the probabilistic theory weights paths by probability and extracts a stationary distribution, the symbolic theory counts paths and extracts the Perron-eigenvalue entropy; both are read off from the same directed graph.
Metric space 02.01.05. The entire setting is metric: the shift metric $d (x, y) = 2^{- m i n {∣ n ∣ : x_{n} \neq = y_{n}}}$ , the completeness and compactness that make subshifts well-behaved, expansiveness measured by a separation constant, and the uniform-continuity argument that powers the Curtis-Hedlund-Lyndon theorem are all metric-space facts imported from there, the compactness of $A^{Z}$ being the single most-used hypothesis of the unit.
Topological space 02.01.01. The product (cylinder) topology, the clopen cylinder basis, total disconnectedness, and the Cantor-set characterisation of the full shift are the topological substrate; the identification of $A^{Z}$ as the unique compact perfect totally-disconnected metrizable space rests on the point-set topology developed there, and shift-invariant closed sets are the topological objects this unit studies dynamically.

Historical & philosophical context Master

Symbolic dynamics begins with Jacques Hadamard's 1898 coding of geodesics on negatively curved surfaces by their sequence of crossings, but the subject is named and founded in the 1938 paper Symbolic dynamics of Marston Morse and Gustav Hedlund (American Journal of Mathematics 60) ^{[Morse-Hedlund 1938]}, which introduced the sequence space, the shift, and the systematic use of forbidden and admissible words; their 1940 sequel established the Sturmian sequences as the minimal-complexity aperiodic codings of rotations. The motivation was geodesic flows on surfaces of negative curvature, where a symbolic coding converts the flow into a shift and makes its recurrence properties combinatorial.

The structural theory of continuous shift-commuting maps is due to Gustav Hedlund, whose 1969 paper Endomorphisms and automorphisms of the shift dynamical system (Mathematical Systems Theory 3) ^{[Hedlund 1969]} proved that these maps are exactly the sliding-block codes — the theorem now bearing the names of Morton Curtis, Hedlund, and Roger Lyndon — and thereby identified the endomorphisms of the full shift with cellular automata, founding their algebraic theory. The subject was reorganised around coding theory and the conjugacy problem by Roy Adler, Brian Marcus, and others, and the canonical modern reference is the 1995 textbook of Douglas Lind and Brian Marcus, An Introduction to Symbolic Dynamics and Coding (Cambridge) ^{[Lind-Marcus 1995]}, which organises the field around shift spaces, sliding-block codes, subshifts of finite type, sofic shifts, and the still-open conjugacy and isomorphism problems; Bruce Kitchens' 1998 Symbolic Dynamics ^{[Kitchens 1998]} extends the treatment to one-sided and countable-state shifts. Rufus Bowen's Markov partitions for Axiom A diffeomorphisms (1970s) made symbolic dynamics the standard tool for studying hyperbolic systems, completing the program Morse and Hedlund began.

Bibliography Master

@book{LindMarcus1995,
  author    = {Lind, Douglas and Marcus, Brian},
  title     = {An Introduction to Symbolic Dynamics and Coding},
  publisher = {Cambridge University Press},
  year      = {1995}
}

@book{BrinStuck2002sym,
  author    = {Brin, Michael and Stuck, Garrett},
  title     = {Introduction to Dynamical Systems},
  publisher = {Cambridge University Press},
  year      = {2002}
}

@article{MorseHedlund1938,
  author  = {Morse, Marston and Hedlund, Gustav A.},
  title   = {Symbolic dynamics},
  journal = {American Journal of Mathematics},
  volume  = {60},
  year    = {1938},
  pages   = {815--866}
}

@article{Hedlund1969,
  author  = {Hedlund, Gustav A.},
  title   = {Endomorphisms and automorphisms of the shift dynamical system},
  journal = {Mathematical Systems Theory},
  volume  = {3},
  year    = {1969},
  pages   = {320--375}
}

@book{Kitchens1998,
  author    = {Kitchens, Bruce P.},
  title     = {Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts},
  publisher = {Springer-Verlag},
  series    = {Universitext},
  year      = {1998}
}

@article{MorseHedlund1940,
  author  = {Morse, Marston and Hedlund, Gustav A.},
  title   = {Symbolic dynamics II. {S}turmian trajectories},
  journal = {American Journal of Mathematics},
  volume  = {62},
  year    = {1940},
  pages   = {1--42}
}

Prerequisites

38.01.01
02.01.05
02.01.01

Tier anchors

beginner: Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 1 (the language of blocks and the golden-mean / even shift pictures); 3Blue1Brown *Chaos* visual essays for the binary-coding intuition behind the full shift
intermediate: Brin-Stuck 2002 *Introduction to Dynamical Systems* (Cambridge University Press) Ch. 3 §3.1–§3.3 (the full shift, subshifts, subshifts of finite type, the Curtis-Hedlund-Lyndon theorem); Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge) Ch. 1–2 and §6.2
master: Lind-Marcus 1995 *An Introduction to Symbolic Dynamics and Coding* (Cambridge University Press) Ch. 1–6 (shift spaces, languages, sliding-block codes, sofic shifts, the conjugacy theory); Brin-Stuck 2002 *Introduction to Dynamical Systems* (Cambridge) Ch. 3; Kitchens 1998 *Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts* (Springer Universitext); Hedlund 1969 *Endomorphisms and automorphisms of the shift dynamical system* (Math. Systems Theory 3) — the originating paper for cellular automata as shift-commuting maps

References

Lind, Marcus 1995 — An Introduction to Symbolic Dynamics and Coding · Ch. 1 (full shifts, shift spaces, languages and forbidden words), Ch. 2 (sliding-block codes and the Curtis-Hedlund-Lyndon theorem), Ch. 6 (the conjugacy problem, state splitting); Cambridge University Press 1995
Brin, Stuck 2002 — Introduction to Dynamical Systems · Ch. 3 §3.1–§3.3 (symbolic dynamics, the full shift and its metric and topology, subshifts, subshifts of finite type, topological Markov chains, the Curtis-Hedlund-Lyndon theorem); Cambridge University Press 2002
Hedlund 1969 — Endomorphisms and automorphisms of the shift dynamical system · Mathematical Systems Theory 3 (1969) 320–375; the originating systematic study of continuous shift-commuting maps (sliding-block codes), proving what is now the Curtis-Hedlund-Lyndon theorem and launching the algebraic theory of cellular automata
Kitchens 1998 — Symbolic Dynamics: One-sided, Two-sided and Countable State Markov Shifts · Springer Universitext 1998, Ch. 1–2 (shift spaces, subshifts of finite type, sofic shifts, the metric and topology on sequence space)
Morse, Hedlund 1938 — Symbolic dynamics · American Journal of Mathematics 60 (1938) 815–866; the founding paper of symbolic dynamics, introducing the sequence space, the shift, and the coding of geodesic flows; Sturmian sequences appear in the 1940 sequel

Estimated time

beginner: 18m
intermediate: 46m
master: 84m