The Game of Life is a cellular automaton devised by the british mathematician John Horton Conway in 1970. It was popularised by Martin Gardner in his October 1970 column of "Mathematical Games" in the "Scientific American" magazine [6]. The article garnered more response than any other of his previous articles in the magazine, including Gardners famous article on Hexaflexagons.
A notable property of the special rule set used by Conway's "Game of Life" is it's Turing completeness. The Turing completeness is a property that describes that a programming language, a simulation or a logical system is in principle suitable to solve every computing problem. The programming of the "Game of Life" would be done with patterns, which then interact with each other in the simulation. LifeWiki has a large archive of such patterns for Game of Life. A selection of those is implemented in the applet shown below.
What is a Cellular Automaton?
A Cellular automaton is a discrete model that consists of a regular grid of cells wherein each cell is in a finite state. The inital state of the cellular automate is selected by assigning a state to each cell. The simulation then progresses in discreet time steps. The state of a cell at timestep t depends only on the state of nearby cells at timestep t-1 and a set of rules specific to the automate.
Rules of the Game of Life
In the Game of Life each grid cell can have either one of two states: dead or alive. The Game of Life is controlled by four simple rules which are applied to each grid cell in the simulation domain:
A live cell dies if it has fewer than two live neighbors.
A live cell with two or three live neighbors lives on to the next generation.
A live cell with more than three live neighbors dies.
A dead cell will be brought back to live if it has exactly three live neighbors.
Merrill Sherman/Quanta Magazine
Boundary Conditions
Cellular automata often use a toroidal topology of the simulation domain. This means that opposing edges of the grid are connected. The rightmost column is the neighbor of the leftmost column and the topmost row is the neighbor of the bottommost row and vice versa. This allows the unrestricted transfer of state information across the boundaries.
Opposing edges of the grid are connected to form a toroidal topology of the simulation domain
Cells beyond the grid boundary are always treated as if they were dead.
Another type of boundary condition treats nonexisting cells as if they all had the same state. In the Game of Life this would mean that nonexisting cells are treated as if they were dead (as opposed to the second state "alive"). The advantage of this boundary condition in the Game of Life is that it prevents gliders from wrapping around the edges of the simulation domain. This will prevent the destruction of a glider gun by the gliders it produces (see text below below for details about what gliders are).
https://beltoforion.de/en/game_of_life/
John Horton Conway FRS (26 December 1937 – 11 April 2020) was an English mathematician. He was active in the theory of finite groups, knot theory, number theory, combinatorial game theory and coding theory. He also made contributions to many branches of recreational mathematics, most notably the invention of the cellular automaton called the Game of Life.
https://en.wikipedia.org/wiki/John_Horton_Conway
Origins
Conway was interested in a problem presented in the 1940s by renowned mathematician John von Neumann, who tried to find a hypothetical machine that could build copies of itself and succeeded when he found a mathematical model for such a machine with very complicated rules on a rectangular grid. The Game of Life emerged as Conway's successful attempt to simplify von Neumann's ideas.
The game made its first public appearance in the October 1970 issue of Scientific American, in Martin Gardner's "Mathematical Games" column, under the title of The fantastic combinations of John Conway's new solitaire game "life". From a theoretical point of view, it is interesting because it has the power of a universal Turing machine: that is, anything that can be computed algorithmically can be computed within Conway's Game of Life. Gardner wrote:
" The game made Conway instantly famous, but it also opened up a whole new field of mathematical research, the field of cellular automata ... Because of Life's analogies with the rise, fall and alterations of a society of living organisms, it belongs to a growing class of what are called 'simulation games' (games that resemble real life processes) "
https://conwaylife.com/wiki/Conway's%20Game%20of%20Life
The Game of Life (an example of a cellular automaton) is played on an infinite two-dimensional rectangular grid of cells. Each cell can be either alive or dead. The status of each cell changes each turn of the game (also called a generation) depending on the statuses of that cell's 8 neighbors. Neighbors of a cell are cells that touch that cell, either horizontal, vertical, or diagonal from that cell.
The initial pattern is the first generation. The second generation evolves from applying the rules simultaneously to every cell on the game board, i.e. births and deaths happen simultaneously. Afterwards, the rules are iteratively applied to create future generations. For each generation of the game, a cell's status in the next generation is determined by a set of rules. These simple rules are as follows:
If the cell is alive, then it stays alive if it has either 2 or 3 live neighbors
If the cell is dead, then it springs to life only in the case that it has 3 live neighbors
There are, of course, as many variations to these rules as there are different combinations of numbers to use for determining when cells live or die. Conway tried many of these different variants before settling on these specific rules. Some of these variations cause the populations to quickly die out, and others expand without limit to fill up the entire universe, or some large portion thereof. The rules above are very close to the boundary between these two regions of rules, and knowing what we know about other chaotic systems, you might expect to find the most complex and interesting patterns at this boundary, where the opposing forces of runaway expansion and death carefully balance each other. Conway carefully examined various rule combinations according to the following three criteria:
There should be no initial pattern for which there is a simple proof that the population can grow without limit.
There should be initial patterns that apparently do grow without limit.
There should be simple initial patterns that grow and change for a considerable period of time before coming to an end in the following possible ways:
Fading away completely (from overcrowding or from becoming too sparse)
Settling into a stable configuration that remains unchanged thereafter, or entering an oscillating phase in which they repeat an endless cycle of two or more periods.
Example Patterns
Using the provided game board(s) and rules as outline above, the students can investigate the evolution of the simplest patterns. They should verify that any single living cell or any pair of living cells will die during the next iteration.
Some possible triomino patterns (and their evolution) to check:
Here are some tetromino patterns (NOTE: The students can do maybe one or two of these on the game board and the rest on the computer):
Some example still lifes:
Square
Boat
Loaf
Ship
The following pattern is called a "glider." The students should follow its evolution on the game board to see that the pattern repeats every 4 generations, but translated up and to the left one square. A glider will keep on moving forever across the plane.
Another pattern similar to the glider is called the "lightweight space ship." It too slowly and steadily moves across the grid.
Early on (without the use of computers), Conway found that the F-pentomino (or R-pentomino) did not evolve into a stable pattern after a few iterations. In fact, it doesn't stabilize until generation 1103.
The F-pentomino stabilizes (meaning future iterations are easy to predict) after 1,103 iterations. The class of patterns which start off small but take a very long time to become periodic and predictable are called Methuselahs. The students should use the computer programs to view the evolution of this pattern and see how/where it becomes stable. The "acorn" is another example of a Methuselah that becomes predictable only after 5206 generations.
Alan Hensel compiled a fairly large list of other common patterns and names for them, available at radicaleye.com/lifepage/picgloss/picgloss.html.
Activity - Two-Player Game of Life
To call Conway's Game of Life a game is to stretch the meaning of the word "game", but there is an fun adaptation that can produce a competitive and strategic activity for multiple players.
The modification made is that now the live cells come in two colors (one associated with each player). When a new cell comes to life, the cell takes on the color of the majority of its neighbors. (Since there must be three neighbors in order for a cell to come to life, there cannot be a tie. There must be a majority)
Players alternate turns. On a player's turn, he or she must kill one enemy cell and must change one empty cell to a cell of their own color. They are allowed to create a new cell at the location in which they killed an enemy cell.
After a player's turn, the Life cells go through one generation, and the play moves to the next player. There is always exactly one generation of evolution between separate players' actions.
The initial board configuration should be decided beforehand and be symmetric. A player is eliminated when they have no cells remaining of their color.
This variant of life can well be adapted to multiple players. However, with more than two players, it is possible that a newborn cell will have three neighbors belonging to three separate players. In that case, the newborn cell is neutral, and does not belong to anyone.
https://pi.math.cornell.edu/~lipa/mec/lesson6.html
Many patterns in the Game of Life eventually become a combination of still lifes, oscillators, and spaceships; other patterns may be called chaotic. A pattern may stay chaotic for a very long time until it eventually settles to such a combination.
The Game of Life is
undecidable
In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether an arbitrary program eventually halts when run.
, which means that given an initial pattern and a later pattern, no algorithm exists that can tell whether the later pattern is ever going to appear. Given that the Game of Life is Turing-complete, this is a corollary of the
halting problem
In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. The problem comes up often in discussions of computability since it demonstrates that some functions are mathematically definable but not computable.
: the problem of determining whether a given program will finish running or continue to run forever from an initial input.
Conway's Game of Life: Mathematics and Construction by Nathaniel Johnson and Dave Greene provides a linear exposition of the questions, results, and techniques behind the game. It functions as a companion to the website where one can download the ebook.
The material requires no formal background and is appropriate for its target audience of early undergraduate students. A few topics such as counting, number theory, and algorithm analysis appear, but generally at an elementary level and the key concepts are briefly reviewed in the appendices. There are proofs, but they are generally careful deductions using few mathematical tools. It is a perfect topic to hand to a curious undergraduate mathematics or computer science student and let them go.
There are a lot of objects that need names and the vocabulary can be a bit overwhelming. Many of the names are descriptive – gliders, volcanoes, sparks – but there are also Snarks, Sir Robins, and David Hilberts to navigate. This is the reality of the subject and not a complaint about the book. There is no glossary, but the index is good and there are additional resources online.
One needs to be able to zoom in and out in real-time as the configurations evolve to see how small-scale changes impact large-scale behavior. The authors do a fine job of using color diagrams with consistent coloring and iconography – indeed, the book is visually impressive independent of the content – but there is no substitute for going to the website and noodling with it there. The ebook can be downloaded at the website (for free, with optional donation), allowing for the two to be used in parallel easily. There are also a few print-on-demand options.
The book is organized into three parts, each with four chapters. The first part, “Classical Topics,” covers the fundamental structures and their properties. “Circuitry and Logic” examines techniques for putting these structures together into circuits that exhibit more elaborate and precise behaviors. Finally, “Constructions” develops how these circuits can establish some more general properties of the Game of Life itself: universal computation, wherein we can simulate a universal computer, and universal construction, which establishes a sense in which the Game of Life can create and position its own components. Chapters close with notes and plenty of exercises. There are appendices with some mathematical preliminaries, technical details, and selected exercise solutions. Further material is available on the website, which has plenty of tools for simulating the game, finding specific results, and identifying new investigations that a newcomer could engage in almost immediately.
https://maa.org/book-reviews/conways-game-of-life-mathematics-and-construction/