Thursday, March 11, 2010

The Game of Life: New Spaceship

The Game of Life is a cellular automaton developed by John Horton Conway in 1970. It consists of a grid, in which each grid square can be either alive or dead. The "game" proceeds in turns, in which each square is calculated to be either alive or dead based upon its neighbors. Conway's rules are as follows:

1. If a living cell has fewer than 2 (live) neighbors, it dies.
2. If a cell has 4 neighbors (or more) it dies.
3. If a living cell has 2 or 3 live neighbors, it survives the round.
4. If an empty cell has exactly 3 neighbors, a cell is created.

From these simple rules, great complexity can be generated. Conway's Game is even Turing complete, meaning that it is possible to build a computer inside of a (very large) Game of Life simulation using logic gates and "gliders."

Gliders and spaceships are special constructions in the Game of Life, which, typically, keep their general shape and move in a direction over time. Today, I believe, I discovered a new one.

I was using a extremely complex pre-programmed pattern and tossing random gliders at it. This spaceship emerged, and I luckily saved it.

This "spaceship" is more properly known as a "rake" because of how it sends out gliders while also moving forward. The cool think about this one, however, is that it sends out TWO streams of gliders at perpendicular angles, producing a V-shape. If it hasn't been discovered before, I think it should be called a "V-rake." I have not seen anything like this online, especially in a pattern so small. Some very cool patterns are able to be generated from these things, and I hope that, if this discovery is original, that the cellular automaton community benefits from it.

Here is one giant battleship I made using only the V-rake.

If interested, you should download Golly, the best cellular automaton simulator I have ever seen. Just reproduce the first picture in the program and have fun! Golly also comes with some samples impressive creations that will, I promise, blow your mind.

Because I'm not sure if this discovery is, in fact, novel, this post could either be a terrible introduction to cellular automata or a significant mathematical find-- the suspense is killing me.

After experimenting a little, I modified this raker/spaceship into a "puffer" or "steamer" which is a shapeship that, unlike a raker, leaves a messy trail of debris behind it. Pictures below.

No comments: