---
tag: N35QM9G83G
kind: statement
role: theorem
name: Curtis–Hedlund–Lyndon theorem
msc: [37B10, 37B15]
uses: [A1XE59ZHNM, 0P27W9RW0G, 0Z57EC6YX3]
about: [5QXNC6NTVN, A1XE59ZHNM]
sources:
  - url: https://en.wikipedia.org/wiki/Curtis%E2%80%93Hedlund%E2%80%93Lyndon_theorem
same_as:
  wikidata: Q5195996
  wikipedia: Curtis–Hedlund–Lyndon theorem
---

## Statement

Let $A$ be a finite set and let $d \ge 1$.
Give $A^{\Z^d}$ the [[product topology|0Z57EC6YX3]] of the discrete topologies.
For $v \in \Z^d$ let $\sigma_v \colon A^{\Z^d} \to A^{\Z^d}$ be the shift $\sigma_v(x)_u = x_{u + v}$.
Let $F \colon A^{\Z^d} \to A^{\Z^d}$ be a map.
Then the following are equivalent:

1. $F$ is [[continuous|0P27W9RW0G]] and $F \circ \sigma_v = \sigma_v \circ F$ for all $v \in \Z^d$.
2. There are a finite set $N \subseteq \Z^d$ and a map $f \colon A^N \to A$ such that $F(x)_u = f\big((x_{u + n})_{n \in N}\big)$ for all $x$ and all $u \in \Z^d$.

## Remarks

Condition 2 says that $F$ is a [[cellular automaton|5QXNC6NTVN]] with neighbourhood $N$ and local rule $f$.
For 2 implies 1, the value $F(x)_u$ depends only on finitely many coordinates of $x$, which gives continuity.
The same rule is used at every site, which gives commutation with shifts.
For 1 implies 2, the space $A^{\Z^d}$ is compact, so $F$ is uniformly continuous.
Hence $F(x)_0$ is determined by the coordinates $x_n$ with $n$ in some finite set $N$, and this defines $f$.
Commutation with the shifts then gives the formula at every site $u$.
Compactness is essential: over an infinite alphabet there are continuous shift-commuting maps that are not given by a finite rule.
The same statement holds for maps between [[shift spaces|A1XE59ZHNM]], where condition 2 says that $F$ is a sliding block code.

## Explanations

### L1 human

A cellular automaton updates every cell of a grid by looking at a few neighbours and applying a fixed rule.
Such a map treats all positions alike and changes only a little when the input changes far away.
The theorem says that these two properties characterise cellular automata.
So one can define cellular automata either by rules or by topology.

### L2 human

The theorem lets one treat a cellular automaton as an endomorphism of the dynamical system $(A^{\Z^d}, \sigma)$.
It shows, for instance, that the inverse of a bijective cellular automaton is again a cellular automaton.
A continuous bijection of a compact space onto a Hausdorff space has a continuous inverse, and that inverse commutes with the shifts.
In one dimension the theorem identifies the conjugacies between shift spaces with invertible sliding block codes.
It is a basic tool in the classification of [[subshifts of finite type|624XDXX8FN]].