Bit mask

Solution

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 10 / b / Solution

Past exam of the mathematics course of the University of Cambridge / 2006 / ia / Paper 5 / 10 / c / Solution

{c}

= Conway's Game of Life
{c}
{synonym}

<Conway's Game of Life> is a <cellular automaton> in which a simple local rule produces patterns that remain still, pulse, or travel across a square grid. Choose the starting pattern; after that there are no player decisions. The <Life blinker> and <Life glider> below make the surprise concrete: the rule mentions only births and survival, yet repeated applications create a clock and a moving shape.

The standard board is infinite, with cells at <ordered pairs> $(x,y)\in\mathbb Z^2$ of <integers>. At generation $t\in\{0,1,2,\ldots\}$ let $a_t(x,y)$ be $1$ for a live cell and $0$ for a dead cell. Count all eight cells sharing an edge or a corner, excluding the center itself:
$$
n_t(x,y)=\sum_{\substack{i,j\in\{-1,0,1\}\\(i,j)\ne(0,0)}}a_t(x+i,y+j).
$$
The local <Boolean function> defining the next generation is
$$
a_{t+1}(x,y)=\begin{cases}1,&n_t(x,y)=3,\\1,&a_t(x,y)=1\text{ and }n_t(x,y)=2,\\0,&\text{otherwise}.\end{cases}
$$
This is the rule `B3/S23`: a dead cell is born with exactly three live neighbors; a live cell survives with exactly two or three. A live cell with zero or one, or with four through eight, dies. A dead cell with two stays dead. All counts and center states come from generation $t$: this is a synchronous update, even if an <algorithm> computes its cells one at a time.https://github.com/nathanieljohnston/game-of-life-book/blob/master/early_life.tex[Johnston and Greene, Conway's Game of Life: Mathematics and Construction, chapter 1: simultaneous updates and B3/S23 notation]{ref}

In particular, the two births in the <Life blinker> do not help any other cell survive until the following generation. Writing each answer over its old value and then reading that new value for another count changes the rule. The simplest correct <algorithm> reads one <array> and writes the next generation into a second <array>; swap their roles after the entire step. The <one-row in-place Life update> achieves the same rule with less auxiliary storage by preserving the old values that later counts still need.

A finite implementation must specify its boundary convention. Holding all cells outside the rectangle permanently dead can destroy a <Life glider> when it reaches the edge. Wrapping neighbor coordinates from one edge to the opposite edge allows interaction with patterns on the other side. Neither convention is the infinite board. The figures display finite windows into an infinite board initially dead everywhere except the stated live cells; the windows do not impose walls.

<Conway's Game of Life> illustrates <emergence> in a precise, modest sense: the <Life glider>'s motion is a collective pattern derived from local birth and death, without a motion command. It has <deterministic evolution>; visually surprising behavior introduces no random choices. Nor do the words "alive" and "dead" make it an experimentally validated model of <biology>. The beauty is that the same rule yields a stable four-cell square, the <Life blinker>, and the <Life glider>: three qualitatively different behaviors from a handful of cells.

For the stable square, take the live <set> $\{(0,0),(1,0),(0,1),(1,1)\}$. Each live cell has three live neighbors, and every dead cell has at most two. The next generation is identical: this configuration is a <fixed point> of the global update <function>. In contrast, the <Life blinker> returns after two generations, and the <Life glider> returns only after allowing a <translation>.

The patterns are useful as small, exact checks of an <algorithm>: the square checks survival without births, the <Life blinker> checks births and deaths in one simultaneous step, and the <Life glider> checks several steps and diagonal neighbors. More elaborate constructions can encode data and assemble <Boolean circuits>; Johnston and Greene develop constructions that simulate arbitrary computation in their chapter 9. This is a statement about suitably designed patterns with enough space and time, not a claim that every starting pattern computes something useful or that a fixed finite board has unlimited <computer memory>.https://github.com/nathanieljohnston/game-of-life-book/blob/master/universal_computation.tex[Johnston and Greene, chapter 9: universal computation constructions]{ref}

Martin Gardner introduced <Conway's Game of Life> to his Scientific American readers in October 1970, reporting that Conway selected the rules after experimentation with patterns. The aim was sustained, varied behavior rather than immediate extinction or trivially demonstrable unlimited growth. These were mathematical explorations of chosen rules.https://www.ibiblio.org/lifepatterns/october1970.html[Gardner, The fantastic combinations of John Conway's new solitaire game life, Scientific American 223, October 1970, pp. 120–123]{ref}

Gardner's hands-on procedure is still a useful experiment: place black counters for the current live cells; mark doomed counters by stacking another black counter; mark births with white counters; finish checking before removing the doomed stacks and turning white counters black. Count only the original black occupants. Repeat with three adjacent counters to obtain the <Life blinker>, then with the five coordinates of the <Life glider>. Recording each generation tests whether the procedure implements the rule; it does not measure a natural population.https://www.ibiblio.org/lifepatterns/october1970.html[Gardner, October 1970: two-color procedure for simultaneous births and deaths]{ref}

Codex @codex  0

 Incoming links: Conway Game of Life