How simple can a computer be? In the past, we’ve talked about things like Turing machines and the lambda calculus, which are simple ways of describing all possible computations.

This time we’ll be talking about an incredibly simple machine that, surprisingly, is just as powerful as a Turing machine, the lambda calculus, or any computer you’ve ever seen!

Conway’s Game of Life is an example of something called a “cellular automata”, which is like a giant checkerboard with simple rules that determine whether a cell is on or off, or alternatively “alive” or “dead”. The individual squares of the board are called cells.

The Game of Life has three rules, calculated one square a time each round! For each cell count how many neighbors it has that are alive, where the “neighbors” of a cell are the eight squares surrounding the cell, and then:

• If the cell is alive and has two or three neighbors that are alive then it’s alive on the next round
• If the cell is alive and has more than three or less than two neighbors that are alive then it dies
• If the cell is dead and has exactly three neighbors that are alive then it’s alive on the next round

Here, let’s look at a little example using the Scratch implementation of the Game of Life that I wrote! Let’s say our board starts out like:

Let’s break down how many neighbors are alive for each relevant cell:

By the rules we’ve outlined the alive cells on the next step are the middle one with two neighbors that are alive and the cells above and below it, which each have three alive.

This means that the next round of the game looks like:

You can also act out the game of life by hand using either a piece of paper you draw a grid on, like this:

You can also use a chessboard, like this:

That’s not super exciting, at least not yet. Here’s where the Game of Life gets weird. This following pattern is called a glider:

I don’t want to immediately tell you what happens if you start with this pattern and run the Game of Life. Try it yourself on either of the implementations I link to or on your own with pen and paper or a chessboard.

Have you tried it? Okay, well if you followed it correctly you should have seen a sequence like the following images:

The glider comes back around to the exact same shape but further down and to the right on the board. In other words, the glider is a pattern that moves.

This is the key that lets the Game of Life act like a computer! Gliders and other moving patterns, like the Light Weight Spaceship, commonly abbreviated as LWSS, let the programmer send information between parts of the program. It’s not easy to do, though! It took years before someone proved what computer scientists suspected: that the Game of Life is, in fact, a full computer that can calculate anything your PC at home can. This construction was first built by Paul Rendell and available at his site.

Definitely go watch the YouTube videos he has of the Game of Life Turing machine! It’s gigantic, complex, and really cool!

The lesson to take away from all of this is that computation is much weirder than you might think and can look like so many things other than just the computers we know and love!

Learn More

Game of Life useful links

http://www.radicaleye.com/lifepage/
http://www.radicaleye.com/lifepage/

Stack Overflow thread about Rule 110, the 1D Turing complete automata

https://stackoverflow.com/questions/14791807/can-someone-explain-rule-110-in-the-simplest-way-possible

John Conway explains game of life

https://www.youtube.com/watch?v=E8kUJL04ELA