Why can Conway’s Game of Life be classified as a universal machine?

Question

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?

Totally

Answer 1

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.

Lymanlymann

people have made turing machines in conwayś game of life, theyre just very, very, very, very, very, very, very big. millions to billions of active cells – Countable

Answer 2

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.

Eozoic

"It takes 11040 generations for one cycle." LOL – Nolanolan

@Totally some people built a RISC instruction-set computer in GoL, and wrote tetris with it codegolf.stackexchange.com/questions/11880/… – Microcircuit

Simply amazing. Mind = blown. – Geosphere

@noɥʇʎԀʎzɐɹƆ Yes, I remember seeing that challenge and I was absolutely mindblown – Centavo

You only need a single implementation of NAND or NOR, and you have everything ;) – Nanci

Answer 3

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.

Besotted

This was picked up by Greg Egan in his fantastic science fiction novel /Permutation City/. I consider this book to be a must-read for anyone who is interested in computational meaning of consciousness, social implications of mind uploading, or cellular automata. It's great that a major plot point rests on the existence of such universal constructors. – Ectomy

Answer 4

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.

Sora

Just checked and is back in print - both physical and kindle versions available. Just buying the kindle version now, thanks for the recommendation. – Whenever

Answer 5

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

.

Laveen