I've been avidly reading my copy of Game of Life Cellular Automata, a newly-published book edited by Andrew Adamatzky that contains 27 articles on Conway's Game of Life and related topics.

I've already posted about my own chapter, on an alternative system to Wolfram's for classifying life-like automata. Some other chapters that I found particularly interesting:

  • In The B36/S125 “2x2” Life-Like Cellular Automaton, Nathaniel Johnston discusses the 2x2 rule, so named because any pattern formed from 2x2 blocks of equal-valued cells maintains that structure as it develops, simulating a simpler CA in which each cell's value is a function of its four diagonal neighbors in the previous step. More generally, any pattern formed by 2kx2k blocks does the same thing, but slowed down by a factor of 2k. This leads to the construction of oscillators with very high periods, and there's some interesting number theory involved in calculating their periods.

  • Emmanuel Sapin's chapter, Gliders and Glider Guns Discovery in Cellular Automata, describes his searches for glider guns in life-like rules using a genetic algorithm that changes both the initial seed pattern and the rule itself as it performs the search. The surprise, to me, was that guns actually seem to be reasonably common: he found many of them, in many rules. Unfortunately his figures aren't annotated with the rules for the patterns they show, so it's a little difficult to go from them to a working pattern I could view in Golly.

  • Emergent Complexity in Conway’s Game of Life, by Nick Gotts, contradicts some of the points in my own article by showing that Life allows complex patterns, with emergent structure at multiple scales, to develop from much simpler starting conditions. In the first of the two types of system that he analyzes, the initial state is a pair of puffer trains, moving away from each other perpendicularly. The glider streams sent out by these trains bounce off the other train and each other in highly complex ways, setting up a macrostructure (a criss-crossing grid of lines formed by glider streams and trails of their debris) that is very different qualitatively from the microstructure (the interactions of individual gliders, oscillators, and other patterns). At even longer time scales, a mesostructure develops consisting of switch engine puffers created by certain unusual combinations of events; Gotts argues that the presence or absence of certain patterns of switch engines in this mesostructure can make it more or less likely for the same pattern to recur, leading to a sort of "autocatalysis" that resembles in some ways theories of the origin of biological life. The second system Gotts analyzes starts with an infinite field of cells in which each cell is randomly alive or dead, independently of the other cells, but with only a vanishingly small chance that each cell is alive; he then describes in a rigorous mathematical way the expected behavior of these fields over time scales that are polynomial in the inverse of this small probability. As he shows, at some time scale at most cubic in the inverse probability, the set of remaining live cells in these fields comes to be dominated by patterns with emerging behavior: patterns that grow at a linear or quadratic rate, synthesized by complicated sequences of collisions between much simpler objects such as gliders, blocks, and blinkers.

  • Three articles towards the end of the book, by Adam Goucher, Paul Rendell, and Martinez, Adamatzky, Morita, and Margenstern, discuss the construction of individual patterns of high complexity. Goucher describes a universal computer with a binary memory and a construction arm that can be used to program the computer to build a copy of itself; Rendell instead simulates arbitrary computations in Life using a universal Turing machine, with complicated sub-patterns representing the Turing machine's tape, finite state control, and read-write head. Martinez et al. show that even quickly-exploding rules like B2/S2345 can be used for computation: they find a still life in this rule that is immune to outside influences, and build wires and logic gates using this still life as an insulator.

Other chapters cover glider synthesis of Life still lifes; search strategies for finding dense still lifes; probabilistic, asynchronous, real-valued, spherical, Penrose-tiled, and quantum cellular automata based on Life; and even automated composition of music based on Life patterns.




Comments:

eternal_spring:
2010-09-02T19:24:29Z

How do you feel about the pattern Gemini?

Is it mentioned in the book? If not, do you feel its absence is unfortunate?

11011110:
2010-09-02T20:24:52Z

I'm very impressed with that pattern, paradoxically because of its simplicity compared to e.g. the pattern in Goucher's article, which uses the same constructor-arm but in a more complicated way. In Gemini, it seems that one doesn't need a lot of complicated logic circuits to control the constructor and get it to replicate; instead it just works by sending carefully timed streams of gliders to the right places.

It was discovered too late to make it into the book, though. It would have made a welcome addition to the book, and without it the book doesn't represent the complete state of the art on Life, but all books on active subjects of research have that issue.