Sunday, July 12, 2009

Book Review: The Recursive Universe

The Recursive Universe by William Poundstone

What a delightful book! I was made aware of it by Cosma Shalizi's commentary that I linked to in the A New Kind of Science post. It sounded interesting so I bought a used copy. I'm happy I did so!

The book takes the novel approach of using Conway's Game of Life to discuss complexity theory, specifically how simple rules can manifest into complex systems. Particular emphasis is placed on Von Neumann's interest in self-reproducing machines and cellular automata.

The book is structured in chapter pairs with the first discussing a particular aspect of complexity theory and the second showing how Conway's Life can provide deeper insight. A brief summary of the chapter pairs are:

ChaptersTheme
1 & 2introduction to complexity, reductionism, information theory, and the Game of Life
3 & 4entropy, Szilard's thesis on information and entropy, and the limits of empirical knowledge.
5 & 6information, structure, meaning, and unlimited growth
7 & 8recursion, the challenges of predicting complex systems using recursive calculations, and self-reproduction.
9 & 10the evolution of the cosmos and random Life initial states
11 & 13self-reproduction, the information theory of life, and Life computers.

Before reading this book I had a cursory knowledge of the Game of Life but I was unaware of the sophisticated constructs possible. The Life computers presented in Chapter 12 are fascinating and I can't imagine how much time was required to design them.

I was also unaware of how much attention Life received when it was first created; it seems that many of the bright minds of the time spent considerable time playing the game. I found the historical aspects of this interesting as well but then I have a fondness for computing of this era.

While discussing this book with others I was surprised to find out that an acquaintance of mine was on Gosper's team at MIT that discovered the first Glider Gun. I always enjoy it when I find a personal connection like this to a period of history before "my time".

While looking for additional materials to augment the book I found the following useful references:

  • Two excerpts (part 1 and part 2) of a BBC documentary featuring interviews with Conway.
  • A Game of Life news website
  • Golly, a feature rich cross platform Life implementation
  • Hashlife, an algorithm devised by Gosper that uses quadtrees to efficiently represent deterministic Life constructs.

All in all an entertaining book that is also very thought provoking. I only wish I had copious amounts of spare time to play the Game of Life myself!