Computing At School

Conway's Game of Life
(Notes for teachers of computing)
The "game of life" described and demonstrated here and here illustrates
an unusual kind of programming language, running on an unusual kind of computer.

This web site has an excellent applet (using java) with which you (or your
pupils) can play (top left of page):

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

You can change the number of squares, zoom in or out, paint an initial
configuration with the mouse (by clicking or dragging) start, vary the speed,
stop/clear etc.

Another, possibly simpler and easier one is http://www.bitstorm.org/gameoflife/

You can introduce the idea that the 'game' is a special kind of computer, and
the programming language to run it is the language of black patterns on the
white display, or bits in a 2-D bitarray (possibly an infinite bitarray).

And the peculiar thing about this language is that when goes through one 'step'
starting with a program it produces another program, which, in turn can produce
another program, etc.

Unlike the bits in the bitarray memory of a von Neumann computer, which, in
principle (via use of bits representing addresses) can influence any other part
of the computer, the bits in the conway/life machine can only influence their
neighbours directly, though chains of such influence can eventually have
arbitrarily distant effects.

A task for learners is try to find out how to make initial patterns that go on
changing for a long time, without ending in either a stationary pattern or a
pattern that just alternates between two states.

Don't forget to click on stop even when the board appears to have stopped: the
program need not know that it has stopped. (Why not?)

Other tasks include trying to make big patterns that will 'wipe the board clean'
in as few steps as possible, or patterns that will end up with large densely
packed regions, etc.

This can be done experimentally, but it may be possible for some experimenters
to notice 'theorems' about the life world, so that they not only demonstrate
what happens but prove that it must happen.

E.g. what can you conclude if the intial configuration has two, or three, or
four, or ... etc... dots in a diagonal line, with no gaps. (Make it run slowly
to work out what's happening.)

Does it make a difference if the diagonal has gaps in it?

What if you start with a horizontal row of contiguous dots: one, two, thred,
etc. How does the length of the line affect the result?

What happens if the rows consist of alternating black and white squares? Why?

What are the requirements for the initial system to produce a 'glider' a pattern
that goes on moving indefinitely?

Is it possible to make a glider that moves round in a circular path?

What's the smallest initial configuration you can make that goes on changing for
at least a thousand steps?

Can you prove there isn't a smaller one?

And many more.

Could there be a 3-D version of the game of life, in a 3-D rectangular grid?
What kinds of behaviours could it produce?

Is it possible that biological evolution has produced something like a 3-D game
of life in which the programming elements are molecules and the computer is the
physical world?

This is a wonderful domain in which to demonstrate that almost everything
written about the nature of computation in textbooks for beginners is wrong, or
to be more precise: what's written merely discusses a special subset of
computations, and a special subset of programming languages, reflecting what the
authors happen to have learnt.

Suggestions for improvement are welcome.