Conway’s Game of Life

Introduction

Game of Life is a fascinating thought game/board game/computer algorithm with simple rules having profound consequences. It was invented in 1970 by the Cambridge mathematician John Conway and popularized by a series of articles in "Scientific American" by Martin Gardner. After 50 years of its original publication, thousands are still not just playing it but conducting actual research and asking philosophical questions.

The Rules

Conway’s game of life starts with an infinite grid of squares. Each square has 8 touching neighbors. Each cell can be in two states: dead or alive. Initially, all the cells are dead cells. We then fill in some of the squares, which we define as ‘alive’ cells.

A configuration on the board is a generation. We have a simple set of rules we will apply to all the cells at once, which creates a new board configuration(generation). Those simple rules are:

1. Any live cell with fewer than two live neighbors dies, as if by underpopulation.
2. Any live cell with two or three live neighbors lives on to the next generation.
3. Any live cell with more than three live neighbors dies, as if by overpopulation.
4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction.

Let’s see an example:

Blinker

Here, we have three generations starting with generation 1. Let’s evaluate the transmission from generation 1 to generation 2.

• Cell ‘a’ is dead. Since it does not have exactly 3 live neighbors (rule 4), it remains dead.
• Cell ‘b’ is also dead. Since it has 3 live neighbors (rule 4), it becomes alive.
• Cell ‘c’ is alive. Since it has fewer than 2 live neighbors (rule 1), it dies of underpopulation.
• Cell ‘d’ is alive. Since it has 2 live neighbors (rule 2), it lives on to the next generation.

Similarly, generations continue. In this particular example, you can see that the pattern repeats every two generations. Such patterns are called oscillators. In particular, this pattern is called a ‘Blinker,’ which is a type of oscillator.

Classification

Since the publication of ‘Game of Life’ in Scientific American by Martin Gardner, sufficient interest was aroused by the game’s simplicity and unpredictability. There were a handful of patterns or organisms that frequently developed during the course of the game. Some of the major ones were,

• Still Lifes: In Conway’s Game of Life, still life is a pattern that does not change from one generation to the next. The most common still life (i.e., that most likely to be generated from a random initial state) is the block. The second most common still life is the hive (or beehive).

Block

Hive

• Oscillators: An oscillator is a pattern that repeats itself after a fixed number of generations (known as its period). One of the fascinating oscillators is ‘Dinner Table,’ discovered by Robert Wainwright. It is a period-12 oscillator where it seems like dinner is being passed among four individuals around the table.

Dinner Table

• Spaceships: A spaceship is a finite pattern that returns to its initial state after several generations but in a different location. The four smallest spaceships in life, the glider, lightweight spaceship, middleweight spaceship, and heavyweight spaceship, were all found by hand in 1970.
  Gliders were probably the most unexpected characteristic of Conway’s Game of Life and, in the end, the one responsible for its great complexity and utility. Conway quickly realized that gliders were the substitute for von Neumann’s wires as the mechanism for transporting information from one place to another in the Life field.

Glider

You will find that the population constantly undergoes unusual, sometimes beautiful, and always unexpected change. In a few cases, society eventually dies out. Most starting patterns reach stable states, i.e., they become still lifes or oscillate forever.
After discovering gliders, in the hope of discovering more interesting configurations, Conway announced a $50 prize to anyone who would find an initial configuration whose population goes to infinity. One way to solve it would be to discover a pattern that would keep adding gliders to the field. MIT professor Bill Gosper captured the prize when he invented the ‘Glider Gun.’ As the name suggests, glider guns generate a continuous stream of glider objects.

Glider Gun

Logic Gates

Patterns within the Game of Life can be much more complex than illustrated in the above examples and can even be organized to perform functional operations. Streams of gliders can be considered as signals to perform computational procedures such as logic gates (AND, OR, NOT) as well as simple memory counters.

To implement a logic gate, we need:

• Input electric pulse -> Gliders
• Wires to transmit input -> Gliders’ movement trajectory
• Process input and compute a boolean result -> Glider collisions
• Output -> Collision of gliders with immobile patterns

Gliders destroy each other when they collide with each other. The following figure shows how gliders disappear when they are involved in a 90⁰ binary collision.

Glider Collision

To design an effective circuit, we need to stop a stream of gliders somehow to prevent the gliders from polluting the computational space. There are compact, stable patterns called eaters that consume gliders and recover back to their original form.

Eater

As we can see from the figure below, the eater consumes the glider and goes back to its original form in 5 generations.

Eater consuming glider

NOT Gate

Since NOT is a unary operator, its implementation is the simplest one. We only need an input component, a gun, and an output. The stream from the gun will activate the output.

NOT Gate ( A — 0, Output 1)

In the figure above, we can see that the input signal is false so that the gun can activate the output. The result is true.

NOT Gate (A — 1, Output — 0)

In the figure above, we can see that the input signal is true, which does not allow the gun to activate the output. The result is false.

AND Gate

AND gate requires two input components, an output, and a Gun. Here, we use the glider stream generated from glider A as an output.

AND Gate (A — 1, B — 0, Output — 0)

Here, A is True, and B is false: Gun stops the signal from A. So, A cannot activate the output. The result is False.

AND Gate (A — 1, B — 1, Output — 1)

Here, A is true, B is true: B stops the gun’s stream, which allows A’s stream to activate the output. The result is True.

AND Gate (A — 0, B — 1, Output — 0)

Here, A is false, B is True: Since A is false, it cannot activate the output. The result is False.

OR Gate

The OR Gate is slightly more complex. Like an AND gate, it requires two input components and an output. However, now we need two guns, one parallel to the input and one perpendicular. The parallel gun will be the one that activates the output.

OR (A — 1, B — 0, Output — 1)

Here, A is True, B is False: A stops the perpendicular stream of gliders and lets the parallel gun activate the output. The result is True.

OR (A — 1, B — 1, Output — 1)

Here, A and B both are True: Here, B stops the perpendicular stream of gliders and lets A and parallel gun continue the stream, which activates the output. The Result is True.

OR (A — 0, B — 0, Output — 0)

Here, A and B both are False: Here, parallel and perpendicular gun streams collide, which prevents the parallel gun from activating the output. The result is False.

Turing Machine

These properties imply that the Game of Life is theoretically equivalent to a ‘Universal Turing Machine’; that is, ‘Turing complete.’ A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory). If somebody says, “my new thing is Turing Complete” that means in principle (although often not in practice), it could be used to solve any computation problem. Let’s understand the basic concept of the Turing Machine.

A Turing machine is a hypothetical machine thought of by the mathematician Alan Turing.

Above is a straightforward representation of a Turing Machine. It consists of a stream of infinitely-long tape with 1s,0s, and spaces. The machine looks at each square and performs the task described by the program book, telling it to do whatever transformations and translations. Eventually, the machine gets to a halting state and what’s left is hopefully our solution. It is a simple process, but it is the essence of computation. Whatever any computer can do, it could, in theory, be done by that system (looking at 1s and 0s at a tape).

Paul Rendell completed the Turing machine's construction in Conway’s Game of Life on April 2, 2000.

Turing Machine

The example constructed has a finite state machine of 3 states ({S0, S1, S2}) and uses 3 symbols ({‘0’,’1',’2'}). The program implemented doubles the length of a string of one of these symbols on the tape.

Later on February 10, 2010, the Turing machine was extended into a universal Turing machine capable of simulating every other Turing machine.

Other Insane Achievements

Nicolas Loizeau’s 8-bit programmable computer

An even bigger result was achieved by Nicolas Loizeau in 2016 when he crafted an 8-bit programmable computer. It supports eight variables and thirteen instructions — write, goto, move, jumpif, print, add, or, and, xor, not, flat, sign, and increment. He was able to compute the Fibonacci sequence using this 8-bit programmable computer.

Digital Clock

As an entry to the Code Gold Stack Exchange coding challenge, user ‘twe4ked’ created a digital clock in Game of Life using gliders and lightweight spaceships.

Digital Clock

Life Inside Life

One of the most insane things is that you can simulate Life inside Life itself.

Life in Life

Free Will

According to Daniel C. Dennett in his paper ‘Real Patterns.’

In my opinion, every philosophy student should be held responsible for an intimate acquaintance with the Game of Life. It should be considered an essential tool in every thought-experimenter’s kit, a prodigiously versatile generator of philosophically important examples and thought experiments of admirable clarity and vividness.

Let’s combine the Game of Life rules into a single fundamental rule to make the point more dramatic.

Each cell, in order to determine what to do in the next instant, counts how many of its eight neighbors is ON at the present instant. If the answer is exactly two, the cell stays in its present state (ON or OFF) in the next instant. If the answer is exactly three, the cell is ON in the next instant whatever its current state. Under all other conditions the cell is OFF.

The entire physics of Game of Life is captured in this single rule. Given the state description of this world at an instant, we can perfectly predict the future instants by the simple application of one law of physics. There are no backdoors, no hidden variables; everything is directly and completely visible.

As we saw the evolution of simple patterns into the universal Turing machine, programmable computers, and digital clocks. Dennett regards this as an accurate “toy model” of his view of the workings of the universe; he claims that the relation of these complex two-dimensional dot patterns to the underlying simple rules is essentially the same as the relation of all processes in the universe, including human action, to the underlying mechanistic laws governing subatomic events.

Bill Gosper, the MIT professor, imagined a supercomputer dedicated to Life. In his hypothetical world of computer Darwinism, only the fittest cells would survive against impossible mathematical odds. After billions of generations, he theorized, the computer might create intelligent lifeforms.

By understanding The Game of Life, we gain a powerful intuition about several philosophical questions, including the question of consciousness, the possibility of strong AI, and the presence, or lack thereof, of free will. What if human consciousness was not magic but rather a result of many, many things happening all at once. According to Dennett, consciousness is an illusion of vast parallel processing of information. In an aptly titled book Free Will, Sam Harris takes a hard-lined neuroscientific approach to bluntly suggest that we have no free will. According to Sam Harris,

Free will is an illusion. Our wills are simply not of our own making. Thoughts and intentions emerge from background causes of which we are unaware and over which we exert no conscious control. We do not have the freedom we think we have.

He cites experiments proving that the human brain often contains information about decisions several seconds before decisions are consciously made. The suggestion that we have no free will is a radical and perhaps discomforting conclusion, but not one without intuitive understanding. If we try to imaging our vast, operating human brain inside The Game of life, we can predict with absolute certainty exactly how the brain will progress during each iteration, and we can trace every action taken by the brain.

Conclusion

It’s important to recognize that the Game of Life might be a little rule-based simulation. But it sure is fun to think about the profound implications of the game. It's also motivating and awe-inspiring to see so many talented people working together to solve thought-provoking problems in Game of Life.

Sadly on the 11th of April 2020, we lost John Horton Conway. According to Persi Diaconis, a mathematician at Stanford University, “John Conway is a genius. And the thing about John is he’ll think about anything.… He has a real sense of whimsy. You can’t put him in a mathematical box.”

As Paul Lockhart said in The Mathematician’s Lament,

We are all born into this world, and at some point we will die and that will be that. In the meantime, let’s enjoy our minds and the wonderful and ridiculous things we can do with them. I don’t know about you, but I’m here to have fun.