beanz Magazine

Conway’s Game of Life

Maia Valenzuela on Flickr

Can we make a computer using only three simple rules?

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

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

John Conway explains game of life

Also In The April 2019 Issue

Use SketchUp to create this fascinating mathematical pattern that appears everywhere in nature.

Learn about the STEAM star’s amazing journey onto Mythbusters Junior and beyond.

What’s the best way to choose a classroom lunch? Or the best way to elect a leader? The answer isn’t so simple.

Keep your passwords at the tip of your fingers, or maybe at the back of your eyes!

Bring your coding skills and your desserts to new levels in this simple Python coding activity.

Learn about the shiny new technology that allows us to be connected like never before.

Squares, checkerboards, and hollow boxes… what pattens can you imagine in Python?

A fun, DIY electronics project that’ll keep you from bumping around in the dark!

Use your favourite block language to animate this fascinatingly odd game.

Can we make a computer using only three simple rules?

How science and tech led to an exciting discovery in one of the most dangerous areas of space.

How did video games become popular before the internet? It’s all about shareware, floppy disks, and human cleverness!

Links from the bottom of all the April 2019 articles, collected in one place for you to print, share, or bookmark.

Interesting stories about science and technology for April 2019.