46
$\begingroup$

(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?

$\endgroup$
2
  • 5
    $\begingroup$ Would you like to consider other cellular automata like Critters? Critters conserves mass/energy if one defines mass to be the number of on cells and equates mass with energy. Critters is a time-reversible cellular automata, so it also satisfies a second law of thermodynamics, but unlike most reversible cellular automata, Critters can run for millions of generations with no drastic entropy increase. dmishin.github.io/js-revca/index.html $\endgroup$ Jul 17, 2022 at 9:18
  • $\begingroup$ @Joseph Van Name: That's very cool, actually. Are there any examples of complex "machinery" built in it? Do you then need to provide them with some kind of "fuel" to keep them going, e.g. can a spaceship gun be built, but it must process or convert some raw material (say a long train of still lifes or something) and only runs until that material is exhausted? $\endgroup$ Jul 19, 2022 at 2:57

3 Answers 3

46
$\begingroup$

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.

$\endgroup$
11
  • 2
    $\begingroup$ I cannot access this paper, does it contain mathematical theorems, and could you quote some relevant ones? $\endgroup$
    – Ville Salo
    Jul 17, 2022 at 7:21
  • 2
    $\begingroup$ Mainly, I was wondering what "it is not possible to define a locally conserved energy functional" means exactly. $\endgroup$
    – Ville Salo
    Jul 17, 2022 at 7:26
  • 3
    $\begingroup$ @The_Sympathizer --- indeed, the discretization is not the main obstacle to an application of Noether's theorem to the Game of LIfe, it's the absence of a Lagrangian. $\endgroup$ Jul 17, 2022 at 7:53
  • 3
    $\begingroup$ @VilleSalo a "locally conserved functional" relates changes in that functional on some compact region to a current through the boundaries; a formal definition is in Additive conserved quantities in discrete-time lattice dynamical systems --- I do not know of a proof that the Game of Life lacks such a functional, the paper I cite in the post states this without proof. $\endgroup$ Jul 17, 2022 at 10:25
  • 2
    $\begingroup$ I just would've thought that's much beyond what we currently know, so I was surprised. Doesn't this rule out things like immortal creatures that survive in every context? $\endgroup$
    – Ville Salo
    Jul 17, 2022 at 11:11
27
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I think this is really nice. It certainly makes sense to call this a form of energy - and note that in the example of the "Critters" cellular automaton this becomes the actual conserved cell count, so arguably generalizes such. And it makes intuitive sense too, to think that a glider gun contains an infinite amount of potential energy. It's just that, as you say, it's not useful for doing CGoL "physics". $\endgroup$ Jul 19, 2022 at 7:33
17
$\begingroup$

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 self-enforcing 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

$\endgroup$
3
  • 3
    $\begingroup$ Technically, superstable patterns in the sense of the linked post (AIUI) don't have to be orphans, so their number on the lattice could increase over time. Assuming any existed, that is (which I personally suspect not to be the case for Conway's Game of Life, even if proving that seems quite difficult indeed). The number of superstable orphan patterns would indeed be an additive conserved quantity, though. $\endgroup$ Jul 17, 2022 at 20:06
  • 1
    $\begingroup$ @IlmariKaronen: Oops, you are probably right, I admit I didn't (re)read the post. Actually, a superstable orphan pattern can only appear on the first step, so wouldn't give a conserved quantity, with the usual meaning of an orphan. But I know what you mean, a superstable pattern that additionally has the property of our pattern above. $\endgroup$
    – Ville Salo
    Jul 18, 2022 at 7:08
  • $\begingroup$ (Actually I see that your answer defines superstable orphans exactly as patterns that can neither be destroyed nor created) $\endgroup$
    – Ville Salo
    Jul 18, 2022 at 12:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.