Friday, July 6, 2007

48) John Horton Conway's game of life

back to top back to best labs summary contents


John Horton Conway's game of life

And now for an example of the amazing patterns we can get from mathematics with a simple set of rules, but carried out over and over again on the same system, similar to the physical systems we described that also go through cycles. This is an example of a cellular automaton, invented by the mathematician John Horton Conway. It is one of the earliest examples that brought the idea of cellular automata into the mainstream of thought.

draw a square grid like a checker board.

Each square has only two states: on or off, which you can denote by an 'X' or a blank square. Note that each square is surrounded by a neighborhood of 8 other squares. this will be the limit of perception, of interaction between the cells. each affects only the cell it is touching.

here are the simple rules of interaction. they are based on the idea of birth and crowding forming both positive and negative feedback loops.

If an X is surrounded by four or more X's (crowded) or only 1 or none (lonely) it dies the next generation.

If a blank square is surrounded by exactly 3 X's, a new X is born there in the next generation.


Here is an example of how it's done: draw a grid of 6 x 6 squares and start with four X's in a row and one X above the last in the row, one row of squares away


first look across each row, at the empty squares next to the x's and for each one, count how many x's are neighboring it. If any have exactly 3 neighboring x's put a dot inside.


I'll count the neighbors for some of the empty squares for you:



squares 1,2,3,4 have only 1 neighboring x each. Square 5 has two neighbors to the right. square 6 has 3 neighbors, the two above and one to the lower right of it. square 7 has 4 neighbors. square 8 has two neighbors above it, and square 9 has 3 neighbors above it.

Put in the dots for the empty squares with 3 neighbors and fill in the rest. It will look like this:




Now look at each X, if it has too many or two few neighboring x's circle it. The top x has 0 neighbors, the two x's on the ends of the line have only 1 neighbor each, so we circle the three of them:



now we can remove the circled X's and replace the dots with new x's:



that's one cycle.




Do it again:



note that the two inner x's (which i circled) had 5 neighbors and 4 neighbors. more than 3 so we circle them.



replacing:



that's the 2nd cycle.




Again:



This time no empty cells have exactly 3 x's for neighbors.



that's the 3rd cycle.








4th cycle. Now no empty cell has 3 neighbors and the two x's have only one neighbor each. they will be erased and the game is done, all empty cells. so the original conway life form died off.


Let's try some more. With a little practice this becomes easy to do:








i drew 2 cycles. you figure out yourself with the dots and circles if i did it correctly. notice in the last life form that all x's have 2 neighbors and no empy cells have 3. so that life form is stable forever. finished.

Here's another:



This is a surprising one! the second cycle is a repeat of the beginning life form. so this one will keep flipping back and forth forever. It's called blinker. Did you guess that such a behavior was possible with our simple rules? We will call that behavior periodic. So what behaviors do we have so far? the life form can die out, it can remain stable, or it can be periodic.

Try



you will have to figure out how large to make the grid as you work. Now try making up some patterns on your own.


Well, can we find some other kinds of behaviors? First try this one:



stable again right? Lets add one more X to that pattern in two different ways. so they are only slightly different. At this point would you venture to predict what happens to these two patterns?



Each looks like the last example with just ONE extra X added. do you think the outcome of two patterns is similar if they start out similar? Can you predict for me which would last the longest? Which would spread the most?


Well? What happens to A? Remember, you'll have to expand your grid as the thing grows. Surprise! it tumbles off the edge of your paper. A third kind of behavior! What to call it? Depending on the point of view: either relative to the center of the moving life form or relative a fixed grid we can call it periodic or I'm not sure what! And B? What a mess! How far did you get? Actually, it takes about a thousand cycles before it settles down to an assortment of blinkers and stuff.

Lots more is possible, for instance I can make two huge puffing gliders that bounce back and forth between three posts made out of blocks and every time they collide at the middle post they shoot off a tumbler like A. A never ending stream is produced. This particular colony thus keeps growing. That's a fourth kind of behavior! Growth.

And of course you can watch 'primer' which produces a never ending steam of gliders spaced out like the prime numbers! this colony keeps growing, but produces an increasingly complex pattern. that's a fifth kind of behavior! Call it creativity? Chaos?

Here's where you find 'primer':

http://www.ibiblio.org/lifepatterns/

click on the 'enjoy life' applet at the upper left hand corner.

in the applet click "open" choose 'primer'. hit ok

now use your mouse to stretch the window as big as possible

now click speed and make it 15 frames per second, 1 generation per frame

then hit "go"

you can use the window bars in the frame to move around and watch the crazy machine. in the lower right hand corner is a growing sieve of Eratosthenes! it's wacky.

(Warning: the website might have changed since i wrote this and you will have to hunt around for the correct webpage and applet.)


Could you have imagined all this?

You can use the applet to experiment with a lot more patterns. You can click on the other links in the site to find out more about what's been discovered about this little system.

You can experiment with changing the basic rules of life and death of cells, you can even change the size of the neighborhood! use your imagination.

1 comment:

Mandy said...

People should read this.