subshift

In symbolic dynamics, a subshift X over a finite alphabet A is a closed, shift-invariant subset of the full shift A^Z. The full shift consists of all bi-infinite sequences x = (x_n)_{n∈Z} with x_n ∈ A, equipped with the product topology, and the shift map σ: (x_n) → (x_{n+1}). A subset X is a subshift if it is invariant under σ and closed.

The language L(X) of a subshift X is the set of all finite blocks that occur in some x ∈ X. Equivalently, given a set F of forbidden blocks, X(F) = {x ∈ A^Z : no block from F appears in x} defines a subshift, and X = X(L(X)).

Subshifts of finite type (SFT) are those for which F can be chosen finite; equivalently they admit a presentation by a finite directed graph (an edge shift), where admissible bi-infinite sequences correspond to bi-infinite walks. Sofic shifts are images of SFTs under sliding block maps and can also be described by finite labeled graphs.

Examples include the full shift A^Z, the Golden Mean shift over {0,1} which forbids the block 11, and the even shift over {0,1} consisting of binary sequences in which the number of zeros between consecutive 1s is always even.

Subshifts are closed and invariant under the shift map; the restriction of σ to X is a homeomorphism. Important notions include the topological entropy, which measures the exponential growth rate of admissible blocks, and dynamical properties such as mixing or transitivity, as well as notions of factors and conjugacies.

Subshifts provide a compact, combinatorial framework for coding more general systems and are a central object of study in symbolic dynamics and ergodic theory.