Life Thermodynamics

For general discussion about Conway's Game of Life.
Post Reply
User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Life Thermodynamics

Post by Macbi » January 11th, 2018, 5:02 pm

I thought it might be nice to have a thread to discuss the "thermodynamics" of Life. What can we say about how random life patterns behave on average?

I'll start us off. I've been thinking about how the initial density of a soup influences the final contents after it has stabilized. Let's work on tori to avoid bothersome edge effects. Experimental results show that the final population of the universe is maximised when the initial density is somewhere around 0.37. As the initial density tends towards 0 or 1 the final density tends towards 0, because the cells die from having too few or too many neighbours.

This means that for any p < 0.37 there's a q > 0.37 such that the two universes evolve to the same average final densities. What would be interesting to know is if despite having similar densities these two universes can nevertheless be distinguished by looking at the frequencies with which particular objects appear in them.

I don't know what the answer is in general, but I can say something about the case where p is very small and q is very close to 1.

The result of soups with very low density is known as Sparse Life. Lets fix a size of torus and let p tend to 0. Eventually most of our soups will be totally empty, and only a very few will contain a single object. Because p is very small, p^2 is very small compared to p, p^3 is very small compared to p^2, and so on. So almost all objects that appear will be those that have predecessors with the minimal possible number of cells. In Life all patterns with only 1 or 2 cells die out, so we'll look at patterns with 3-cell predecessors. These turn out to be just the blinker and the preblock. Each blinker has two possible predecessors (itself and its successor). Each block can form from 4 different preblocks. So the nonempty universes will contain either blocks or blinkers, with blocks being twice as likely. The average final density will be (4*4)p^3 + (2*3)p^3 = 22p^3.

One can then do the same analysis as q tends to 1 (let's call it Dense Life). In a universe of all live cells, the next generation is all dead. So again all universes will end up empty unless enough dead cells happen to appear close enough to each other in the initial configuration that some cells aren't overpopulated. A cell needs at least 5 dead neighbours to be alive in the next generation. If we want 3 live cells in the next generation then at least two of them must not be orthogonally adjacent. But cells that aren't orthogonally adjacent can share at most 3 neighbours. So at least these 3 neighbours and two other cells on either side must be dead, bringing us to seven dead cells in all. By my count the blinker has 24 7-cell predecessors, and the preblock doesn't have any. The average final density will be (24*3)(1-q)^7 = 72(1-q)^7.

So we've discovered two things: the relation between p and q is that 22p^3 = 72(1-q)^7, and the two universes can totally be distinguished! One has twice as many blocks as blinkers, and the other has no blocks at all.

User avatar
Majestas32
Posts: 549
Joined: November 20th, 2017, 12:22 pm
Location: 'Merica

Re: Life Thermodynamics

Post by Majestas32 » January 11th, 2018, 9:25 pm

I tested this on 1% and 89% 1000x1000 tori in Golly (similar 20~30 avg. fin. pop.) and did confirm that blinkers were more common than blocks in the dense case and vice versa in the sparse case.
This will be much more accurate in, say, a 0.2% 50000x50000 tori case with fewer traffic lights and R pentominoes messing up the stats.

This will actually be pretty interesting comparing with B3/S238 tho for the dense case (edit: it behaves similarly to a medium density soup in dense life. Similarly to one of those agar explosion things)
Searching:
b2-a5k6n7cs12-i3ij4k5j8
b2-a3c7cs12-i

Currently looking for help searching these rules.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Life Thermodynamics

Post by NickGotts » January 12th, 2018, 8:39 am

dvgrn kindly drew this thread to my attention. I've done quite a bit of work on Sparse Life, and published a few papers and book chapters on it (details on my website nickgotts.weebly.com - contact me if you're interested in copies of some of these). I don't know of any previous work on Dense Life and I've never got round to it myself. I've always worked on Sparse Life in infinite fields, although many of the same findings would apply to toroidal fields as initial density approaches zero, but the product of initial density and number of cells approaches infinity (assuming the field is of more or less equal diameter in both directions).

Once you look at infinite grids, every possible pattern will occur initially at a density dependent on the number of "on" cells for Sparse Life, and for Dense Life, the density after 1 step would of course be dependent on the number of "off" cells necessary to produce each pattern. Analysis in both cases needs to distinguish the "short term" - any exact number of steps from the start; the "long term" - what patterns will continue to be present forever; and most interesting to me, the "medium term" - what can be said about the grid in "eras" defined in terms of the initial density, e.g. after ~N steps, where N = 1/d, or ~N^2 steps, or ~N^3/2, etc.

Another thermodynamic possibility I've thought of is to start with a completely empty grid (or a completely full one), but introduce a small uncertainty in the rules - so, for example, an "off" cell surrounded by "off" cells might spontaneously turn on with a very low probability. Unless you can somehow connect a hardware randomiser to Golly or some similar program, experiments have to use a pseudorandom mechanism - I have defined a CA in Golly that in effect links Life to a chaotic multi-state CA, with one rarely-occuring state of the latter triggering an "error" in the corresponding Life cell. But I've only carried out a few experiments on small toroidal grids.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Life Thermodynamics

Post by Macbi » January 12th, 2018, 5:53 pm

Majestas32 wrote:I tested this on 1% and 89% 1000x1000 tori in Golly (similar 20~30 avg. fin. pop.) and did confirm that blinkers were more common than blocks in the dense case and vice versa in the sparse case.
Thanks for testing this! I did actually try it myself, but as you say there were lots of R-pentominos (I guess 0.88 can hardly be called "close to 1") so I didn't bother collecting statistics. It's interesting that the debris can nevertheless be distinguished.
This will be much more accurate in, say, a 0.2% 50000x50000 tori case with fewer traffic lights and R pentominoes messing up the stats.
I think collecting the statistics will get pretty slow because the pattern being simulated is so big and interesting patterns so rare. And I think my post essentially contains a mathematical proof, so it doesn't really need empirical verification!
This will actually be pretty interesting comparing with B3/S238 tho for the dense case (edit: it behaves similarly to a medium density soup in dense life. Similarly to one of those agar explosion things)
I suspect 99% density acts pretty similarly to 50% density in B3/S238.
NickGotts wrote:dvgrn kindly drew this thread to my attention. I've done quite a bit of work on Sparse Life, and published a few papers and book chapters on it (details on my website nickgotts.weebly.com - contact me if you're interested in copies of some of these). I don't know of any previous work on Dense Life and I've never got round to it myself. I've always worked on Sparse Life in infinite fields, although many of the same findings would apply to toroidal fields as initial density approaches zero, but the product of initial density and number of cells approaches infinity (assuming the field is of more or less equal diameter in both directions).


Once you look at infinite grids, every possible pattern will occur initially at a density dependent on the number of "on" cells for Sparse Life, and for Dense Life, the density after 1 step would of course be dependent on the number of "off" cells necessary to produce each pattern. Analysis in both cases needs to distinguish the "short term" - any exact number of steps from the start; the "long term" - what patterns will continue to be present forever; and most interesting to me, the "medium term" - what can be said about the grid in "eras" defined in terms of the initial density, e.g. after ~N steps, where N = 1/d, or ~N^2 steps, or ~N^3/2, etc.
Your work on Sparse Life is amazing! I've got access to your papers through my university but thanks for the offer.

I guess Dense Life will turn out to have the same general characteristics as Sparse Life (i.e. there will be some minimum number of cells leading to a switch-engine) but it will be much harder to say anything because the number of cells needed to produce interesting patterns will be a little bit too large for our computers to handle. So I guess the effort:interest ratio is pretty bad.

I mentioned tori because I wanted to think about the density at stabilization, and infinite universes don't ever stabilise. (There's a memorable piece of speculative fiction about someone discovering a Life pattern that replicates invulnerably, eventually swallowing up almost all infinite grids. Does anyone have the link to this?) I suppose everything I said applies equally well to infinite grids in what you call the "short term".
Another thermodynamic possibility I've thought of is to start with a completely empty grid (or a completely full one), but introduce a small uncertainty in the rules - so, for example, an "off" cell surrounded by "off" cells might spontaneously turn on with a very low probability. Unless you can somehow connect a hardware randomiser to Golly or some similar program, experiments have to use a pseudorandom mechanism - I have defined a CA in Golly that in effect links Life to a chaotic multi-state CA, with one rarely-occuring state of the latter triggering an "error" in the corresponding Life cell. But I've only carried out a few experiments on small toroidal grids.
This sounds interesting. I wonder if it would be possible to make an error-resistant spaceship, oscillator or still life? I'm imagining two universal constructors next to each other, each of them wired so that any error causes its complete destruction and a signal to be sent to the other one to begin reassembly. (Or on the other hand I suppose the block already works if you only care about on -> off errors.)

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Life Thermodynamics

Post by NickGotts » January 15th, 2018, 10:54 am

Your work on Sparse Life is amazing!
Thanks for the compliment!

After a longish break, I've just restarted some Sparse Life related work, and hope to post about it soon. My first goal is to do a complete search of all patterns up to 10 cells (Paul Callahan checked all up to 9 cells some 20 years ago, but apart from the benefit of replicating that using different language and code, I want to find all 10-cell infinite-growth patterns, and confirm (or refute) my belief that none will show superlinear growth of cell number or cumulative image (i.e. the total number of cells entering the on state at some point). The latter is important because it affects the expected time to collisions with original blocks and blinkers.
I mentioned tori because I wanted to think about the density at stabilization, and infinite universes don't ever stabilise.
However, it's possible they approach stabilisation at some density as time approaches infinity. Not that I've any idea how to determine whether that's the case.

NickGotts
Posts: 101
Joined: November 10th, 2011, 6:20 pm

Re: Life Thermodynamics

Post by NickGotts » January 15th, 2018, 11:00 am

A point about tori. On a square torus, low densities can leave gliders buzzing round the torus forever. However, if there's any difference between x and y dimensions, a glider will sweep out multiple diagonals before returning to its starting point, and hence is more likely to hit something. It's also possible to give the torus a twist in one dimension, which would mean *WSSs do the same.

User avatar
dvgrn
Moderator
Posts: 10612
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Life Thermodynamics

Post by dvgrn » January 15th, 2018, 11:19 am

Macbi wrote:(There's a memorable piece of speculative fiction about someone discovering a Life pattern that replicates invulnerably, eventually swallowing up almost all infinite grids. Does anyone have the link to this?)
NickGotts wrote:
I mentioned tori because I wanted to think about the density at stabilization, and infinite universes don't ever stabilise.
However, it's possible they approach stabilisation at some density as time approaches infinity. Not that I've any idea how to determine whether that's the case.
Well, it's easy -- just observe any very old Life universe with any kind of random initial conditions. They're all full of IceNine.

... I didn't bother to correct Calcyman when he reposted that quote, but the alternate-universe oscilloscope wasn't a program I wrote. It was a black rectangular box three inches thick, a foot high and 2.25 feet long with a display on the side, and some sliders and knobs for tuning the display to different universes. Rented it from the Outsiders.

See, nobody has time to run an infinite Life universe long enough to see anything -- you have to look at the ones already out there that have been around for 14.8 billion years. Unfortunately they're all pretty boring, being all full of the same quasicrystalline replicator, so I didn't argue when the Outsiders came by to repossess the oscilloscope.

User avatar
Macbi
Posts: 903
Joined: March 29th, 2009, 4:58 am

Re: Life Thermodynamics

Post by Macbi » January 17th, 2018, 6:53 am

dvgrn wrote:Well, it's easy -- just observe any very old Life universe with any kind of random initial conditions. They're all full of IceNine.
Heh, c/137. Makes sense.


I've been working on some stuff to do with how long it takes soups to stabilize, but before I get to that here's some more stuff about soup density.

Out of the 2^9 = 512 possible neighbourhoods for a cell, there are 140 that lead to that cell being alive. Of these 84 have three cells and 56 have four cells. So if we create a soup of density p then the expected density after one generation is 84 p^3 (1-p)^6 + 56 p^4 (1-p)^5. This simplifies to give 28 p^3 (1-p)^5 (3-p).

This doesn't let us say anything about density in generation 2 and up, because the cells in generation 1 won't be independent from their neighbours. But we can still say some interesting things.

We can find the maximum of the function p -> 28 p^3 (1-p)^5 (3-p) for p between 0 and 1. This turns out to be at p = (14 - sqrt 115)/9 = 0.3640, giving a generation 1 density of 0.3704. This suggests that a "maximally active" soup would start with a density of around 0.3640 (I vaguely remember that this is what apgsearch uses). I also find it interesting that the density goes up from 0.3640 to 0.3704. Final ash density tends to be around 0.0287, so we should eventually end up on a downward trajectory.

The function p -> 28 p^3 (1-p)^5 (3-p) has fixed points at p = 0, 0.1925 and 0.3702. The fixed points at 0 and 0.3702 are stable, and the one at 0.1925 is unstable. This tells us what would happen if we were to randomly permute the cells of a pattern after every generation. If the starting density is inside the range from 0.1925 to 0.5643 then the density will tend to 0.3702, otherwise it will tend to 0.

For the next step up we can look at what the density will be after two generations. We do this by running every 5 by 5 pattern and seeing if the middle cell is alive in generation 2. The density after two steps will then be given by the sum as n ranges from 0 to 25 of c_n p^n (1-p)^(25-n) where c_n is the number of 5 by 5 predecessors with population n.

It turns out that these coefficients are as follows

Code: Select all

0  0
1  0
2  0
3  22
4  1092
5  10902
6  52808
7  159532
8  352308
9  662834
10 1136852
11 1653846
12 1844296
13 1487120
14 813480
15 273548
16 49756
17 3962
18 72
19 0
20 0
21 0
22 0
23 0
24 0
25 0
I won't bore you with the multiplied out polynomial because I can't see anything interesting about it. But we can plot the function:
densities.png
densities.png (20.44 KiB) Viewed 5524 times
The maximum of the new function is at (0.3802, 0.3167), so the optimal starting density is a tad higher, and the density is no longer increasing after two generations. The only fixed point is at 0; every other starting density becomes smaller.

One could continue this approach to higher generations, but I don't have the computing power to evolve all 7 by 7 patterns for three generations. I think Knuth might have a way to calculate these polynomials without simulating every pattern, by using Binary Decision Diagrams, but I don't have access to a copy of TAOCP at the moment. It would be interesting if the values for which maximum density was achieved tended to a limit.

Post Reply