How can I prove that Game of Life's evolution function is continuous?

Question

Conway's Game of Life is a cellular automaton, but also a discrete dynamical system. In all the papers, books, notes I have read on it, it is never never never shown that its evolution function is continuous. I tried to show it myself, thinking it was trivial, but it reveals to be more challenging than I thought. Here is what I did so far:

Since we work in an infinite orthogonal grid, I denote the space we work with as $S^{\mathbb{Z}^2}$, where $S=\{0,1\}$ with $0$ standing for a dead cell and $1$ for one alive. Therefore a point $x \in S^{\mathbb{Z}^2}$ would be an infinite $2-$dimensional sequence of zeros and ones.

Next, I defined a distance on this space, by saying $d(x,y)=0$ if $x=y$ and otherwise $d(x,y)=2^{-k}$ where $k$ is the largest integer such that $x_{[-k,k]^2}=y_{[-k,k]^2}$ i.e two points $x,y$ are close if they agree on a square $\{-k,\dots,k\}^2$. I already managed to prove that $S^{\mathbb{Z}^2}$ is a compact metric space.

Where I am now stuck, is that I have no clue how to apply the definition of continuity on Game of Life.. Here is the definition: Let $(X,d)$ be a metric space. A map $f: X \mapsto X$ is called continous if for every $x\in X$ and $\epsilon > 0$ there exists a $\delta >0$ such that: $$ d(x,y)<\delta \implies d(f(x),f(y))<\epsilon $$

And I know the evolution function is continuous. According to a famous theorem of Hedlund, a map $f: S^{\mathbb{Z}^2} \mapsto S^{\mathbb{Z}^2}$ is a cellular automaton if and only if the map is continuous and commutes with the shift map $\sigma$.

If you have any tips,ideas or hints.. would be highly appreciated! I am quite curious to know how to get there now, Thanks !

Answer 1

Let $N = \{-1,0,1\}^2$ denote the neighborhood of the cell at the origin and, for any set $S \subset \mathbb Z^2$ of cell coordinates, let the Minkowski sum $$S + N = \{(i+a,j+b) : (i,j) \in S, (a, b) \in N \}$$ denote the combined neighborhood of all the cells in $S$. Then $$x_{S+N} = y_{S+N} \implies f(x)_{S} = f(y)_{S}.$$

Since, in particular, $[-k,k]^2 + N = [-k-1,k+1]^2$, it follows that $$x_{[-k-1,k+1]^2} = y_{[-k-1,k+1]^2} \implies f(x)_{[-k,k]^2} = f(y)_{[-k,k]^2},$$ and thus that $$d(x,y) \le 2^{-k-1} \implies d(f(x),f(y)) \le 2^{-k}.$$ Therefore, for any $\epsilon > 0$, $$d(x,y) < \frac\epsilon2 \implies d(f(x),f(y)) < \epsilon.$$

Note that this proof does not depend on the specific evolution rule of Conway's Game of Life in any way, except for the fact that the evolution of each cell is solely determined by the states of the cells in its neighborhood. The same proof applies just as well to any other deterministic cellular automaton defined on the 3×3 cell Moore neighborhood, and can be straighforwardly generalized to any deterministic cellular automaton defined on any finite neighborhood.

Answer 2

It seemed that the $\epsilon-\delta$ definition was not indeed the best approach, based on Dan's remark I found these lecture notes where they give a full answer of my question.

If anyone else will need it in the futur, here is the link. The theorem answering this question can be found on page $106$. These lecture notes were extremely helpful as they define everything and it is the first time that I see a review on cellular automata where they combine topology and symbolic dynamics in order to describe Game of Life and CA in general.