Let $\mathcal{A} = \{0, 1, \ldots, k-1\}$ be a finite alphabet of $k$ symbols. The full shift space on $\mathcal{A}$ is:

$\Sigma_k = \mathcal{A}^{\mathbb{Z}} = \{s = (\ldots, s_{-1}, s_0, s_1, s_2, \ldots) : s_i \in \mathcal{A}\}$

the space of bi-infinite sequences. Endowed with the product topology (generated by cylinder sets), $\Sigma_k$ becomes a compact, metrizable space. The shift map $\sigma: \Sigma_k \to \Sigma_k$ is defined by:

$(\sigma(s))_n = s_{n+1}$

shifting all indices by one position.

A subshift of finite type (SFT) is a subset $\Sigma_A \subset \Sigma_k$ defined by forbidden blocks. Given a $k \times k$ transition matrix $A$ with entries $A_{ij} \in \{0,1\}$, the SFT is:

$\Sigma_A = \{s \in \Sigma_k : A_{s_n s_{n+1}} = 1 \text{ for all } n\}$

Only transitions allowed by $A$ appear in sequences. The shift $\sigma$ restricted to $\Sigma_A$ yields a dynamical system $(\Sigma_A, \sigma)$.

SFTs model Markov processes and encode constraints from geometric dynamics (e.g., horseshoe map partitions).

For a dynamical system $(X, f)$, choose a partition $\mathcal{P} = \{P_0, P_1, \ldots, P_{k-1}\}$ of $X$ into disjoint pieces. Define the symbolic coding $\phi: X \to \Sigma_k$ by:

$\phi(x)_n = i \quad \text{if} \quad f^n(x) \in P_i$

The sequence $\phi(x)$ records which partition element each iterate visits. If the partition is well-chosen (Markov partition), $\phi$ is a homeomorphism onto a subshift, conjugating $f$ to $\sigma$.