I've been on a little Conway's Game of Life kick for the past couple weeks myself. Such a simple algorithm like this is great for learning a new programming language.
Nice share. It probably can't compete with a major Game of Life simulator such as Golly, but I agree that Conway's Game of Life is an excellent little programming project that is entertaining to implement in different languages.
So rarely are the theoretical aspects written about. At least this one mentions a Turing Machine in passing.
Think about that. We can build a Life pattern that looks for a counter-example to the Goldback Conjecture (GC). We can build a Life pattern such that if the GC is true, the pattern will grow forever, but if it's false, then the pattern self-destructs.
With our current knowledge in mathematics, no one can tell the eventual fate of the pattern. That's a pretty deep result, equivalent (sort-of) to the Halting Problem.
I wish someone had told me that when I was writing my first "Life" simulators in 1979.
Note: The GC says every even number from 4 onwards can be written as the sum of two primes. If you like you could use another unsolved problem, like the Collatz conjecture - http://en.wikipedia.org/wiki/Collatz_conjecture
Good point. The theoretical aspects of Conway's Game of Life are really eye opening. Interestingly I have found research material that hints that Conway designed the rules specifically so that it would not be possible to determine whether or not a pattern would grow indefinitely.
It is not possible to prove that there is a pattern which can grow endlessly.
Some of this will repeat earlier comments, but I'm including them here for completeness. I'm not an expert in this, so some of it might be wrong in the detail.
Firstly, there is a comparatively simple pattern that grows endlessly - the Gosper Glider Gun.
you'll see that he's a hacker's hacker. If you analyse the GGG you'll see that it can be broken down into smaller pieces, each of which is a small modification of something small and easy to understand. In essence, you can build a GGG from small components, and then optimise it, the entire process being like writing a computer program, perhaps in something like BrainFuck: http://en.wikipedia.org/wiki/Brainfuck
I might meet Gosper in March next year. I've made a note to ask him if that's actually what he did. From what I've read, it is.
The question about "growth in which it was not an oscillating reaction" is hard to pin down, and it's not clear what you mean. I would guess you mean something like:
A pseudo-periodic pattern is one which can be
divided into two areas, P and P'. Inside P the
pattern is periodic, and in P' the pattern is
comprised of units, each of which is periodic
under some isometry.
Well, using GGGs you can beat that definition too, because you can construct patterns that build GGGs at a distance, and then you can make a Turing Machine that computes the digits of pi, then you can build GGGs at distances that get further away by the amount that is a digit of pi, and then you have something that's still sort of predictable, and still isn't what you want, but still satisfies the above definition.
Part of the problem is making precise make precise what you mean. I suspect you're trying the equivalent of proving the existence of non-computable numbers, and then asking to show one. Counting arguments suggest that amorphous patterns that grow indefinitely exist, but they're the equivalent of uncomputable numbers. I can't show you one.
That's not quite right. Conway originally intended that no pattern could grow indefinitely, but a pattern was quickly found that could grow forever: the Gosper glider gun. http://en.wikipedia.org/wiki/Gun_%28cellular_automaton%29
I played a version once that shipped with an old windows game pack. Each turn, each player was allowed to add one cell of their color and remove one of their opponent's, after which the rules were applied. The goal was to eliminate all of your opponent's cells. I remember finding it fun at the time, but I haven't played it in years.
I recently started learning python, so I wrote an implementation using the pygame library. If you're interested, you can see it here: http://readysquid.com/blog/programming/conways-game-of-life/
Feel free to take the source and play with it if you'd like.