Take the 2-minute tour ×

I was recently reading about artificial life and came across the statement, "Conway’s Game of Life demonstrates enough complexity to be classified as a universal machine." I only had a rough understanding of what a universal machine is, and Wikipedia only brought me as close to understanding as Wikipedia ever does. I wonder if anyone could shed some light on this very sexy statement?

Conway's Game of Life seems, to me, to be a lovely distraction with some tremendous implications: I can't make the leap between that and calculator? Is that even the leap that I should be making?

share|improve this question

6 Answers 6

up vote 19 down vote accepted

You can build a Turing machine out of Conway's life - although it would be pretty horrendous.

The key is in gliders (and related patterns) - these move (slowly) along the playing field, so can represent streams of bits (the presence of a glider for a 1 and the absence for a 0). Other patterns can be built to take in two streams of gliders (at right angles) and emit another stream of bits corresponding to the AND/OR/etc of the original two streams.

EDIT: There's more on this on the LogiCell web site.

share|improve this answer

Paul Rendell implemented a Turing machine in Life. Gliders represent signals, and interactions between them are gates and logic that together can create larger components which implement the Turing machine.

Basically, any automatic machinery that can implement AND, OR, and NOT can be combined together in complex enough ways to be Turing-complete. It's not a useful way to compute, but it meets the criteria.

share|improve this answer
This Paul Rendell guy just blew my mind. –  Ziggy Dec 27 '08 at 13:39
Wow. Just... wow... –  Adam Davis Mar 3 '09 at 22:54
"It takes 11040 generations for one cycle." LOL –  Adam Davis Mar 3 '09 at 22:54
WTFFFFFFFFFFFFFFFFFFF –  gn22 Dec 18 '09 at 23:02

Oh, it gets better: Wolfram's Simplest Known Turing Machine. Wang Tiles.

share|improve this answer

I highly recommend the book The Recursive Universe by Poundstone. Out of print, but you can probably find a copy, perhaps in a good library. It's almost all about the power of Conway's Life, and the things that can exist in a universe with that set of natural laws, including self-reproducing entities and IIRC, Darwinian evolution.

share|improve this answer

Conway's "Life" can be taken even further: It's not only possible to build a Life pattern that implements a Universal Turing Machine, but also a Von Neumann "Universal Constructor:" http://conwaylife.com/wiki/Universal_constructor

Since a "Universal Constructor" can be programmed to construct any pattern of cells, including a copy of itself, Coway's "Life" is therefore capable of "self-replication," not just Universal Computation.

share|improve this answer

And Paul Chapman actually build a universal turing machine with game of life: http://www.igblan.free-online.co.uk/igblan/ca/ by building a "Universal Minsky Register Machine".

The pattern is constructed on a lattice of 30x30 squares. Lightweight Spaceships (LWSSs) are used to communicate between components, which have P60 logic (except for Registers - see below). A LWSS takes 60 generations to cross a lattice square. Every 60 generations, therefore, any inter-component LWSS (pulse) is in the same position relative to the square it's in, allowing for rotation


share|improve this answer

Your Answer


