Conway’s Game of Life

Yesterday I had the opportunity to make a rare visit to the Richfield campus of the Minnesota School of Business. There, I made many interesting connections and I would like to share some of the fruit that was born from one of those meetings.

Father Daniel Huston has been teaching mathematics there for many years and as is our custom when he and I chance to meet one another, we discussed math. But what I want to tell you about is what he showed me on his personal handheld computer. He called it Conway’s Game of Life.

I have seen things like it before, but never thought much about them. But this time Father Daniel made me take notice. He would run his finger across the screen and immediately, patterns would emerge and transform seemingly randomly. However, as Father Daniel explained, there is order in the chaos.

Conway’s Game of Life, as I have since learned, has been a passionate pursuit of many mathematicians and computer scientists for decades. It was devised by a British mathematician, John Horton Conway in 1970 as an implementation of what we call cellular automata. The ‘game’ is a grid of coordinates or locations on the screen and each location can be either alive (black) or dead (white). Each turn, the life and death of each location is calculated by looking at the eight nearest neighbors of that location. If the location has exactly three live neighbors, then that location will be alive next turn. If however, there are fewer than three, the location will die as if from under-population. If there are more than three, the location will die as if from over-population. Chaotic randomness ensues and sometimes the system all dies out. The game is begun with an initial state and in Father Daniel’s implementation, that initial state is created by dragging your finger across the touch-screen. Over time, the system may settle into a static state or pulsating state. In some rare cases, it results in infinite growth.

For decades, researchers have studied this system. They tried to find different kinds of growth (i.e. life) and found many amazing patterns. One celebrated such pattern is shown here, Gospers’ Glider Gun (thank you Wikipedia). This pattern is cool because it shows that it is possible to have infinite growth. This “gun” if left undisturbed will continue to “shoot” off rounds perpetually and these rounds will travel forever.

I know I am about 40 years too late but I see many interesting programming projects that I wish I had done and that I wish I could assign to students. Given that so many researchers have been working for so long on Conway’s Game of Life, I can assume that there is not much else I could add. In fact, I had some immediate ideas regarding color change, rules variations, array size, and encoding schemes and found that others have already thought of these things and more and had written many papers and implemented many interesting programs about this already.

In fact, researchers have shown that Conway’s Game of Life is a system that has the property of being Turing Complete. This proof shows that anything that can be computed can be computed with Conway’s Game of Life.

I may not be able to do original research with this system anytime soon, but I want our students and instructors to be aware of it. Conway’s Game of Life is an implementation of a very simple and interesting algorithm that has inspired many programming projects and will likely inspire many more. I hope that many of you will take on the challenge of writing your own implementations of this and similar systems to polish and prove your creative, programming and graphics skills.