The game is designed around the following simple rules:

1) Any live cell with fewer than two live neighbors dies, as if caused by underpopulation.

2) Any live cell with more than three live neighbors dies, as if by overcrowding.

These are stable patterns that do not change and can be used to build critical solid parts of complex patterns. These patterns stay in one state which enables them to store information or act as solid bumpers to stop other patterns or keep other unstable patterns stable. Examples of still life include:

1)

2)

3)

4)

These patterns are more complex and change over a specific number of ticks. They repeat their pattern infinitely. The basic oscillators have periods of two or three ticks, but complex oscillators have been discovered with periods of twenty or more ticks. These oscillators are very useful for setting off other reactions of bumping stable patterns to set off a chain reaction of instability. The most common period-2 oscillators include:

1)

2)

3)

4)

A spaceship is a pattern that moves, returning to the same configuration but shifted after a finite number of generations. The glider is an example of a simple spaceship and its generations each consist of five live cells. The glider has a period of four and moves diagonally one cell every four generations. It moves at one-quarter the speed of light.

Other examples of simple spaceships include lightweight, medium weight, and heavyweight spaceships. They each move in a straight line at half the speed of light.

Guns are repeating patterns which produce a spaceship after a finite number of generations. The simplest gun, called the

Since 1970 researchers and freelance experimenters have discovered hundreds of new patterns and have built thousands of intricate machines and devices using these and other simple parts.

Theoretically the many different possibilities of these four simple rules allow the development of any kind of computing. A Turing machine has been implemented in Conway's Game of Life. There are hundreds of other amazing patterns.

1)

Conway’s efforts to realize this dream began in 1965. That year, he assembled a team of graduate students at Cambridge with the express goal of designing a simple but universal automated machine. Conway referred to these machines as ‘mindless games’ and over the course of three years, Conway and his students came up with hundreds of games. Although the Game of Life is the most popular product to come out of this project, Conway got closer to his dream through other machines.

One of these machines is called

You start with the following 14 fractions and the input 2. The machine then multiplies each fraction by 2 until the product is an integer. The first product is 15. The machine then takes this integer and repeat the process, multiplying each fraction by 15 until the new product also results in an integer. By the 19th iteration, the machine produces a 4, by the 69th an 8 and by the 219th a 32. Conway, in other words, could program the Fractran to churn out the prime powers of 2.

Yet, despite its apparent simplicity, the Fractran has obvious defects. The shortness of the program is offset by the length of the computations. Getting to the hundredth prime in Conway’s program, for instance, takes a million operations. Thus, even with Fractran under his belt, Conway continued to invent mindless games, looking to make one that was less cumbersome and even more elegant.

And it is this obsession with simplicity that paved the way to Life. By 1970, Conway and his team and had been working on cellular automation for eighteen months and had tinkered with a myriad of rule-sets to design a machine that would produce configurations that grew, but not too quickly. Near the end of the process, however, Conway had cut back on his ambitions and settled on a two dimensional machine instead. At some point he’d even given up on the idea of a two-state machine.

Actresses and Bishops, for example, is a two dimensional, three-state predecessor to the Game of Life. Cells are not only full or empty but are also gendered. In this version, two bishops and an actress, or two actresses and a bishop, are needed for procreation. The former arrangement produces a baby actress while the latter results in a baby bishop. But if a cell is not in contact with at least one other cell of the opposite sex, it dies of sexual frustration.

Conway soon realized that gender was superfluous and abolished the rule. Then, he added the overpopulation rule and arrived at Life.

What followed after its creation was an effort to make a

By 1972 Conway had his abandoned formal work with Life with many questions still unanswered. Importantly, he had asserted, but not proven, that Life was universal. Advances in computing power and a sustained interest from the mathematical community resulted in a steady stream of discoveries.

Garden of Eden configurations, those which cannot be produced by any preceding configuration, are still a source of excitement for Life enthusiasts. The first of these configurations was found in 1971 by Roger banks, a discovery that set off a race to finding the smallest possible Garden of Eden. What makes the task particularly difficult is that determining whether a Garden of Eden exists is an undecidable problem. That is, there is no algorithm that can generate these types of configurations. The smallest one was discovered only recently, in 2011, and consists of 56 cells that fit in a 10x10 square.

"No method of computation carried out by a mechanical process can be more powerful than a Turing machine."

Therefore, as the Game of Life is Turing complete, it is one of the most powerful models of computation. In other words, no mechanical form of computation can solve a problem that a Turing machine or cellular automata cannot solve, given sufficient time and space.
The following reasons lead researchers to determine the Game of Life has all the computational capability of Turing Machines, meaning it is 1) Turing Machines have the ability to

3) The cellular formation of a “glider” can interact with other cellular automata to construct logic gates like AND, OR, and NOT. Therefore, it is possible to build a pattern of cellular automata that acts like a

We present here two examples of 1-Dimensional Game of Life. The first is called Rule 30. First, some terminologies. Let 0 represent a dead cell and 1 represent a live cell. For instance 101 represents a cell that is currently dead but is flanked by two live neighbors. Then the next state of the cellular automata, given the current pattern, is determined by the following pattern:

111: 0, 110: 0, 101: 0, 100: 1, 011: 1, 010: 1, 001: 1, 000: 0

Rule 90 is another variant of Life, and it is essentially based on the XOR-function. The next state of a cell at position i is determined by the states of its adjacent cells at position i-1 and position i+1. Explicitly, let x and y represent the states of the cells at position i-1 and position i+1 at the current time-step; note that x and y can each only be 0 or 1. Then, the next state of the cell at position i is given by x XOR y.

1. Supports a glider gun.

2. Exhibits bounded growth

First it is useful to introduce some terminologies. Let w and x be the minimum and maximum number of adjacent cells that need to be alive to sustain a cell that is currently alive in the next stage, and y and z be the minimum and maximum number of adjacent cells that need to be alive to make a cell that is currently dead alive in the next stage respectively. Then, given any dimension k, we can represent the rules governing any variation of Life succinctly as wxyz. For instance, Conway’s Game of Life is governed by the rule 2333.

In a 1987 paper, the researcher Carter Bays found that the only 3D Life variants that can be said to valid are 4555 and 5766. Comparing the Game of Life to these two variants, Bays made many interesting findings. For instance, he found that Life 5766 contains many initial configurations whose expansions are identical to their analogues’ expansions in the Game of Life. Take the following pattern in Life 5766 for example. Projecting it onto 2D forms a pattern that resembles the glider in the Game of Life:

Cellular automata yield a surprisingly diverse range of practical applications. We focus here on one particular example of a real-life application of cellular automata – the design of a public-key cryptosystem.

A public-key cryptosystem is a cryptographic protocol that relies on two keys – an enciphering key E, which is made public, and a deciphering key D, which is kept private. Such a system should contain two important properties:

Suppose now each block contains N bits and represents m elements of S. To satisfy the security requirement, we require an invertible function which maps Sm to Sm that satisfies the following conditions:

The complexity of cellular automata lends itself nicely to applications in cryptography. In particular, cellular automaton rules that are invertible are prime candidates for the invertible function we require to construct a public-key cryptosystem. To succinctly represent the rules whilst preserving a large neighborhood-size, we can associate the ground set S with a mathematical structure such as a field or a ring. This way, addition and multiplication are well defined on S, and we can thus represent cellular automaton rules as polynomial functions.

Here is a sketch of how a cellular automaton cryptosystem might work. Let the ground set be a field. The enciphering key, E, is a composition of inhomogeneous and time-varying linear invertible rules which is made public (the observant reader might note that the fact that the rules are inhomogeneous and time-varying distinguishes the resulting cellular automaton from elementary cellular automata). The deciphering key, D, is the set of individual rules in the composite enciphering function.

The crucial factor that enables such a cellular automaton cryptosystem to work is the fact that it is extremely computationally expensive to unravel the original state from the cipher state without prior knowledge of the individual rules used in the composite enciphering function. This guarantees the security of the system.

Signing a message in our cryptosystem works in exactly the same way as signing a message in the RSA cryptosystem. All the sender has to do is to apply the secret decryption key D to her name and then include that coded signature at the end of her message. This way, when the receiver receives the message, he can simply use the public key E to decipher the coded signature and see if the name matches the presumed sender.

Callahan, Paul. "What Is the Game of Life?" Math.com. Web. 9 Sept. 2015.

This source offers a brief overview of the game of Life including the rules, life patterns and background.

"Conway's Game of Life." Wikipedia. Wikimedia Foundation. Web. 09 Sept. 2015.

This source includes the Origins of the Game of Life as well the rules and examples of possible patterns.

Izhikevich, Eugene M. "Game of Life." Scholarpedia. Web. 9 Sept. 2015.

This source is an overview of the rules, history, patterns, variations and implications of the Game of Life.

Bellos, Alex. "The Game of Life: A Beginner's Guide." The Guardian. Web. 9 Sept. 2015.

Interview with John Conway about the origins of the Game of Life.

"What Is Life and Cellular Automata?" What Is Life and Cellular Automata? Web. 09 Sept. 2015.

Describes the history of the Game of Life as well as the rules of the game.

"Experiment Garden." Conway's Game of Life. Web. 09 Sept. 2015.

Description of the different types of Life patterns such as Still lives, Oscillators, Gliders and Spaceships.

Roberts, Siobhan. Genius at Play: The Curious Mind of John Horton Conway at Work. N.p.: Bloomsbury, 2015. Print.

A biography of Conway’s life. Provides insights into the process of creating Life, especially from a non-technical perspective.

Wainwright, Robert. Conway’s Game of Life: Early Personal Recollections. Game of Life Cellular Automata. Ed. Andrew Adamatzky. N.p.: Springer London, 2010. 11-16. Print.

A paper written by one of the early Life enthusiasts. It documents the author’s attempt to program Life and gives a detailed account of the circumstances that lead to the first discoveries of patterns.

Wolfram, Stephen. "Random Sequence Generation by Cellular Automata." Advances in Applied Mathematics 7 (1986): 123-169. Web. 9 Sept. 2015.

In this paper, Wolfram explores how 1-dimensional cellular automata can be used to generate random integer sequences.

Guan, Puhua. "Cellular Automaton Public-Key Cryptosystem." Complex Systems1 (1987): 51-57. Web. 9 Sept. 2015.

In this paper, Guan discusses how cellular automata can be used to design a public-key cryptosystem.

"Conway's Game of Life." Wikipedia. Wikimedia Foundation, n.d. Web. 09 Sept. 2015.

Gliders can interact with other objects to create useful elements, such as a counter. Similarly, one can build AND, OR, and NOT logic gates using gliders. It is possible to build a finite state machine connected to two counters. Therefore, interactions between cellular automata can lead to the construction of Turing Machines.

Gardner, Martin. "The Fantastic Combinations of John Conway's New Solitaire Game "life"." Scientific American Oct. 1970: 120-23. Web. 09 Sept. 2015.

Through this article, Gardner popularized Conway’s Game of Life. Gardner describes how the Game of Life opened the door to “a whole new field of mathematical research, the field of cellular automata.”

Kun, Jeremy. "Turing Machines and Conway's Dreams." Web log post. Math ∩ Programming. N.p., 30 June 2011. Web. 09 Sept. 2015.

Researchers were able to begin to understand that the Game of Life could be Turing-complete because the Game of Life can loop infinitely.

Rendell, Paul. Turing Machine Universality of the Game of Life. Thesis. University of the West of England, 2014. Print.

These sources by Dr. Paul Rendell at the University of the West of England’s Centre of Unconventional Computing detail the construction of a Turing Machine within the Game of Life.

"Rule 110." Wikipedia. Wikimedia Foundation, n.d. Web. 09 Sept. 2015.

A specific configuration of cellular automata called Rule 110 that is known to be be Turing complete. Matthew Cook proved Rule 110 to be capable of supporting universal computation.

"Rule 30." Wolfram MathWorld. Web. 9 Sept. 2015.

This page illustrates the mathematical details behind Rule 30, a variant of 1-Dimensional Life.

"Rule 90." Wolfram MathWorld. Web. 9 Sept. 2015.

This page illustrates the mathematical details behind Rule 90, a variant of 1-Dimensional Life.

Bays, Carter. "Candidates for the Game of Life in Three Dimensions." Complex Systems1 (1987): 373-400. Web. 9 Sept. 2015.

In this paper, Bays studies two particular 3-Dimensional Life, Life 4555 and Life 5766, which are well-behaved and display many similarities with Conway's Game of Life.