Does Conway's game of life admit a notion of energy?

Question

(I am not sure if this is a mathematics or physics question so I am not sure where to post it. I am posting it here because the chief subject is an unreal universe that is purely a subject of mathematical theoretical analysis, but there are quite obvious and connections to the study of the real-life physics in our own universe.)

This is something I have wondered about. Conway's game of life provides a fictional universe where that it seems that many highly complex behaviors are possible (including what could arguably be considered to some extent a form of life, i.e. self-replicating information processing systems) but objects are also subject interestingly to extreme instability and rapid entropization, in that a small perturbation of an ordered system, such as the addition or removal of a single "cell" or filled grid square, will cause rapid disintegration of that system.

And this naturally invites comparisons with our own real-life universe: in this one, fortuitously, vanishingly small perturbations of systems do not generally lead to catastrophic entropy increases, but there is still a tendency toward increasing entropy in some way, and it seems thus that the CGoL universe could be thought of as perhaps in some regards having a "more aggressive" version of the 2nd law of thermodynamics.

However, in other regards, it appears to strongly violate the laws of thermodynamics that work in our universe: machines or life forms generally will run forever without any changes, and you can even create infinite streams of "matter" such as with a glider gun. It would seem that, in particular, energy is not conserved, and what we call as "perpetual motion" is possible in the CGoL universe but is not possible in our own.

But I wonder why this is, from a viewpoint of the mathematical structures of the two, in particular regarding the constraints on perpetual motion we know of in our universe. In particular, the typical retort as to why a perpetual motion machine is impossible is some variation on the first and second laws of thermodynamics (not sure what a "third law of thermodynamics" machine would be - I'd presume that's a machine that could refrigerate something to exactly absolute zero, then obtain 100% efficiency by using it as a cold bath). The typical reason it is asserted the first law is inviolate is Noether's theorem: dynamics is symmetric in temporal translation, meaning that, for a given configuration of particles, their future history does not depend on whether that configuration is created now or created (say) ten thousand years from now.

But Conway's universe also has this temporal translation symmetry property. The rules have no explicit time dependence. They are a discrete-time dynamical system (DTDS), sure, but the temporal symmetry group is maximal, so arbitrary time translations can be accessed (a counterexample would be a universe where that behavior is one way for even generation numbers and another for odd generation numbers), and thus you can propagate a quantity along a streamline in phase space, so I am not sure why that the same ways you could argue for Noether in our universe wouldn't still go through for the most part.

Is this correct? Does the temporal translation symmetry of Conway's universe give rise to a conserved quantity, that we might be able to call an "energy"? If so, how does or does not the ready and easy appearance of perpetual motion machines jive with its conservation? Moreover, could this also imply that if, say, hypothetically and someday a loophole were found in our universe that could permit what anyone else might call as perpetual motion, it would not necessarily imply a Noether temporal symmetry failure, but perhaps just a suitable redefinition or expansion of the idea of energy? And if not, why not?

By the way, here are some observations on what a possible "energy" function might have to look like.

• One interesting property of Conway patterns is that they can not only expand perpetually, as in the glider gun, but they can also disappear completely. If we are to assume a conserved energy functional for a particular pattern, it would stand to reason that any pattern that eventually dies completely must have energy equal to that of the vacuum (presumably, we could just set this to 0 conways).
• It would be nice if, at least under some suitable well-defined circumstances, energies are additive, i.e. if we put two patterns next to each other on a suitable grid and they do not interact with each other, the total energy in the grid should be equal to the sum of energies of the two patterns. Note that non-interactivity is vital: we could imagine a couple of patterns that, by themselves, have a positive energy, but when suitably composed even if not immediately overlapping, would result in a pattern that disappears completely, and thus the composition must have energy equal to the vacuum energy.
• Presumably, the smallest stable pattern, which is 3 cells in a horizontal or vertical bar (technically it's not "stable" in the strictest sense because it oscillates between horizontal and vertical orientation, but I'd call it stable because it never dies and moreover it maintains its shape), should have the least positive energy, but it's also possible this may contend with the square (4 cells) because, while it has one more cell, it doesn't move.

Does such an energy function exist? If so, but it is not unique, what further conditions could potentially single out a unique one? If it does not exist, which conditions should we relax and/or replace, and with what? And what would such energy functions suggest when applied to the situations that would seem like violations of conservation by the standards of the real-life universe, like the glider gun? Note that I'd also personally be inclined to think the above conditions are too restrictive in some ways because it's ostensibly still trying to assume or salvage a connection between energy and cell count and if anything we should take the existence of guns, patterns with changing cell count, and so forth as a big red flag suggesting "don't even bother" with that approach. However, then we need a different strategy for trying to find useful axioms.

(Note, clearly there's always a trivial energy function, given by assigning the same value to every pattern. That's also clearly not what we want, but I'm not sure how to eliminate it.)

It's also important to note the many differences between the symmetries of the Conway universe's dynamics and those of what we know so far about the dynamics of our own. For one, the Conway universe's symmetries are discrete, as I mentioned above. That may, alone, be enough to provide complete explaining power as to how that time translation can sit alongside infinite glider guns, but I am not sure. For another, some key symmetries that are present in ours are lacking: for one, rotational symmetry is not present except in the simple four-fold way. For another, boost symmetry is not present for any reasonable notion of boost - that is to say, the Conway universe admits a preferred, absolute rest frame: namely, the one in which a 2x2 square stays put. It seems to me any of these might frustrate or at least require a radical rethinking of what "energy" would have to mean. Perhaps these differences wholly and irrevocably sabotage the idea of energy?

Answer 1

Q: Does the temporal translation symmetry of Conway's universe give rise to a conserved quantity, that we might be able to call an "energy"?

As noticed in the earliest studies of Conway's Game of Life, it has no local conservation law --- it is not possible to define a locally conserved energy functional.

The dynamics does have temporal translation symmetry, but Noether's theorem (which ties a symmetry to a conservation law) does not apply firstly because the dynamics is discretized in space and time, and secondly because the dynamics is not based on a Lagrangian. So even a generalization along the lines of SmoothLife would not be sufficient to apply Noether's theorem.

Answer 2

Conserved quantities like energy are characteristic of time-reversible dynamical systems. Conway's Game of Life is a dissipative, non-time-reversible system, and thus not likely to have any nontrivial conservation laws.

In fact, I can't even think of any nontrivial invariant boolean properties preserved by the CGoL update rule:

• "There are live cells" is not an invariant property, since patterns can die.
• "There are finitely many live cells" is not an invariant property, since even infinite patterns can die.
• "There are exactly four live cells arranged in a 2x2 block" is not an invariant property, since other patterns can turn into a block.
• "This pattern oscillates with a period of $n$ steps" is not an invariant property, since non-oscillating patterns can evolve into oscillators.
• "There is no Garden of Eden pattern" is not an invariant, since a GoE can be present in the first generation (but will never be present in any later one).
• "There is no orphan pattern" is also not an invariant, since even orphans can die if disrupted from the outside.

In principle, a cellular automaton rule could have non-trivial invariants, such as a "superstable orphan" pattern that can neither be formed unless it is already present on the lattice nor destroyed if it is. But as far as I know, no such patterns exist in Conway's Game of Life (nor would they seem to be quite what you're looking for, even if they did exist).

There are, of course, trivial invariants based on the eventual evolution of the pattern under the iterated CGoL update rule, such as "this pattern will eventually die." (Incidentally, I'm also pretty sure that this property, and others like it, are computationally undecidable — it should be possible to construct a pattern in CGoL that will simulate a Turing machine and die out if and only if the machine halts.) But a conserved property that can only be calculated by simulating the system for an unbounded number of steps is hardly useful for doing physics with.

---

That said, if that's not a problem for you, it is in fact possible to define an additive conserved quantity for Conway's Game of Life (or, indeed, for any cellular automaton or similar system) that satisfies all the properties listed in your question:

Theorem: Let $E: \{0,1\}^{\mathbb Z^2} \to \mathbb R \cup \{-\infty, +\infty\}$ be an arbitrary additive function assigning an "instant energy" to a particular lattice state (for example, $E(L)$ could simply count the number of live cells on the lattice $L$) and define $$E_\infty(L) = \lim_{n \to \infty} \frac1n \sum_{k=0}^n E(S^{(k)}(L)),$$ where $S^{(k)}(L)$ denotes the lattice state obtained by evolving the lattice state $L$ by $k$ generations under the CGoL rule. Then $E_\infty$, where defined, is an additive conserved quantity. Specifically:

• By definition, $E_\infty$ is conserved, as it only depends on the long term average limit of $E$ as time tends to infinity. In particular, it's not hard to show that if $E_\infty(L)$ is defined, then $E_\infty(S^{(k)}(L)) = E_\infty(L)$ for any finite $k$.

• If $E$ is additive for non-interacting patterns, then $E_\infty$ is also additive for patterns that never interact as they evolve. In particular, if the operator $\oplus$ denotes some method of merging two lattice states into one, such that $E(A \oplus B) = E(A) + E(B)$ whenever both expressions are well defined, and if $L_1$ and $L_2$ are two lattice states such that $S^{(k)}(L_1 \oplus L_2) = S^{(k)}(L_1) \oplus S^{(k)}(L_2)$ for all $k \ge 0$ (i.e. if the evolutions of $L_1$ and $L_2$ do not interact when combined using $\oplus$), then $E_\infty(L_1 \oplus L_2) = E_\infty(L_1) + E_\infty(L_2)$.

The price to pay for these seemingly convenient properties is that the "eventual average energy" functional $E_\infty$ also has a couple of awkward features:

• $E_\infty$ can be infinite for finite patterns if they grow without bound, as plenty of patterns in CGoL do. (This alone isn't a particularly awful feature, as things go, but it's worth noting for completeness.)

• $E_\infty$ can be undefined if the long term average of $E$ never converges to a (finite or infinite) limit. In particular, I believe there are sawtooth patterns whose long-term average live cell count never converges.

• As noted above, the value of $E_\infty$ (or even whether the limit exists or not) can be computationally undecidable: it should be possible to construct a (family of) pattern(s) encoding an arbitrary Turing machine and its input, such that $E_\infty$ for the resulting pattern depends on whether or not the encoded Turing machine ever halts.

• Also, while $E_\infty$ is additive for never-interacting patterns as defined above, it is not an "additive conserved quantity of range $\alpha$" as defined e.g. by Hattori & Takesue (1991). In particular, the "patterns will never interact" requirement for additivity means that $E_\infty$ cannot be defined as a sum of "local energies" for each cell on the lattice, where the "local energy" of a cell only depends on the states of a bounded number of nearby cells.

Is this definition useful for anything? I'm not sure. On one hand, it does let you assign an "energy" to simple patterns like still lifes, oscillators and spaceships, and have it be additive as long as those patterns never interact. You can even assign an energy to any random soup that eventually decays to a finite amount of non-interacting ash. On the other hand, there's no general way to determine the energy of an arbitrary pattern (or even to determine whether it's defined or not) other than by simulating it until it settles into a collection of non-interacting parts whose population growth is predictable. Some patterns never do, and for some you may never be able to tell if they do or not.

Answer 3

I think the question of existence of additive conserved quantities for Game of Life is not within reach of known methods. As pointed out by Ilmari Karonen, if there exist no such quantities, then there do not exist "superstable patterns" in the terminology of this MO post. This is (one version of) a well-known open problem. On the other hand, I am not aware of a conserved quantity.

I'll phrase a recent result of myself and Ilkka Törmä in the spirit of conserved quantities, namely we do know something slightly nontrivial about "nonincreasing additive quantities".

Let $X \subset A^{\mathbb{Z}^d}$ be a pointed subshift, i.e. a closed shift-invariant set where we have picked a special zero point $z = 0^{\mathbb{Z}^d}$. Let $f : X \to X$ be a cellular automaton, i.e. a shift-invariant continuous function satisfying $f(z) = z$. We can define an (additive) quantity as a continuous function $g : X \to \mathbb{R}$ such that $G(x) = \sum_{\vec v \in \mathbb{Z}^d} g(\sigma^{\vec v}(x)) < \infty$ for all finite-support $x \in X$ (i.e. all $x$ with $\{\vec v \in \mathbb{Z}^2 \;|\; x_{\vec v} \neq 0 \} < \infty$), where $\sigma^{\vec v}$ is the shift by vector $\vec v$. (In what follows, the quantities $g$ considered depend on only finitely many coordinates, and the finite-sum condition holds if and only if $g(z) = 0$.) A nonincreasing quantity is $g$ such that we have $G(f(x)) \leq G(x)$ for all $x \in X$.

Now, consider $f$ the Game of Life. It is not surjective on the full shift $Y = \{0,1\}^{\mathbb{Z}^2}$, so it trivially has nonincreasing conserved quantities: the number of copies of a particular orphan in a region can only decrease, indeed this count immediately drops to $0$ when you apply the rule.

A slightly more interesting question is, what happens if we restrict to the limit set $X = \bigcap_n f^{n}(Y)$, the set of configurations that admit an infinite chain of preimages? (One might hope that $f$ is even bijective on $X$, but this is not the case).

Now, it follows from a recent result of myself and Ilkka Törmä that Game of Life restricted to its limit set does still have nonincreasing quantities. Namely, we proved in [1] that the pattern

cannot be produced by the life rule from any pattern other than itself. But it can be easily extended to a finite-support configuration fixed under $f$ (which is then in the limit set $X$). So the map $g$ that counts the number of appearances of this pattern is a nonincreasing additive quantity for $X$. It is, unfortunately, not conserved, as it is easy to destroy this pattern from the outside.

[1]: Ville Salo and Ilkka Törmä. What Can Oracles Teach Us About the Ultimate Fate of Life? ICALP 2022: 131:1-131:20