I recently downloaded John Conway’s simulation ‘Life’ to my Palm Pilot, and a few questions have arisen from its entertainment.
There are monostable shapes that always stay the same form, and there are bistable shapes that switch between two. Is there any way to construct shapes of higher stability that are stationary?
I found a pattern that travels diagonally in three different shapes. Is there a way to construct one that will travel horizontally or vertically without losing its original shape?
Is there any way to backtrack reliably and find what produced a given shape?
Is ‘Life’ a chaotic program? A few ground rules can produce an incredibly complex pattern, and either die or resolve. However, a single cell can mean the difference between life or death, and there is often no way to tell which will result from the move.
That is indeed what I’m talking about. Is there some way you could post the shape, or do you know what it is?
Darn. Are you sure? I found an interesting nonsymmetric figure that leads to some really cool shapes, and I’d like to see what made it. Hmmm… The only way I can think of that might work is reversing the usual rules, but in that case, how can a cell that was born last round with three neighbors and a cell that’s had three neighbors for a while be differentiated?
That may well be the best description of chaotic systems I’ve ever seen/heard.
Just out of curiosity, ultrafilter, how do you know these things? Did you work with ‘Life’ for a while, or are you proving them mathematically given the (strictly speaking eighteen) rules?
Exactly. Life is an example of a non-reversible cellular automaton. There may be reversible ones out there, but they would behave differently.
Thank you.
Playing around & reading, mostly. I haven’t formally argued that Life is non-reversible, but it’s obvious.
I’ve been a little hesitant to get involved with the details because the proper context for studying this is the theory of dynamical systems, which is some pretty advanced stuff. Later, but not now.
You can find a lot of information by googling on “cellular automata”. There’s a halfway decent introduction here.
The horizontal walker shape that I’ve seen is fairly complex, and spews out stuff to the top and bottom while it travels. The diagonal gliders are simple enough that they spontaneously form frequently.
The only way to backtrack would be to have a program that remembered previous states. At the time Life was first invented, this wasn’t practical, but now with gobs of memory for cheap, it would be easy to do. I don’t know if it has been done, but since just about everything that can be done has been already somewhere, you probably just have to look.
The shape CurtC describes sounds like a Puffer Train (look at the bottom of the linked page).
I suspect that there’s huge amounts of stuff out there on this subject since at the time, a significant fraction of the computing power of the country was devoted to running Life. There must be a large community of folks who did far more stuff with the game than one could imagine. I limited my own dabbling to writing a “screen saver” type program in VAX Fortran that ran on VT220 terminals. It was quite pleasing at the time.
Are there are other rules for Life that also generate “interesting” results? I seem to recall that there are, but can’t recall any details.
If you colour the emergent pattens according to various rules (eg. green for squares that haven’t changed for two iterations, blue for squares that are unchanged after the last three, red after four, etc.,) do you get even more interesting patterns?
Are there higher dimensional versions of Life? Are they “interesting” too?
If I remember correctly, the “horizontal glider” looks something like this:
X
X
X X
XXXXX
(that one will move to the left) Actually, there are a few odds and ends of other squares in the repeating pattern, but this one will lead to them. I also remember that there are some trivial variations on this that also work… I think you can change the length of the “tail” by a few squares. Try that one, and if it doesn’t work I’ll look it up on my other computer.
On your first question, I’ve seen repeaters which have periods of 2, 3, 4, 7, and 8, and of course one can construct higher order repeaters by having two separated patterns in your playing area (for instance, if you had a period-7 repeater and a period-8 repeater separated far enough that they didn’t interfere, the total pattern would be a period-56 repeater).
There is also a formation called a “glider gun”, which repeats regularly but also spits out diagonal gliders as it does so (three per cycle, I think). You could probably set up a system of glider guns shooting at a common target which would have a very long period.
Another interesting type of pattern to play around with is a Methuselah. This is a pattern which starts off simple, but goes for a great many rounds and a great deal of complexity before finally retiring into a repeater and some gliders. The simplest Methuselah is the “r pentomino”
XX
XX
X
, which, if memory serves, goes for over five thousand cycles before retiring.
One variant is called Highlife. The rules are identical to the original Life except that a cell will grow if six of its neighbors are alive, as well as if three of it’s neighbors are alive. This variant is mainly considered interesting because of some formations known as “Sawtooth mills”, simple designs where the population moves back and forth between exponential growth and finite size.
There are some other rule sets that produce visually striking results, but none with just the two-dimensional grid that have the great variety of possible results that make Life so intriguing. One odd set of rules is that any cell with an odd number of neighbors lives, while any cell with an even number of nieghbors dies. Under these rules, any pattern replicates itself an infinite number of times.
This depends on what you mean by chaotic. Can it be said to have sensitive dependance if the set of states is discrete? Are there “strange attractors”? I don’t think so to the first, and I doubt it to the second.
I’m not sure what you’re asking. Can you construct a stationary pattern which oscillates between three or more iterations? If that’s the question, then most definitely.
If you mean, “without losing its original shape” to mean eventually returning to its original shape, yes. If you mean keeping one shape the entire time, I don’t think so.
Indeed. Sorta. I had a program once which let you rewind to the beginning of your simulation and step through it, or jump directly to any generation you wanted. Can’t remember what it was called though.
Asked by someone else: “Are there other rules which produce interesting results?”
Indeed there are. The above-mentioned program also allowed you to change the rules (select which numbers of cells would spawn or kill new cells in the next generation). I don’t recall which specifically were cool. I do remember that one set produced amazing maze-looking designs that would expand rapidly. I remember that it looked a lot like those slow motion films of someone disturbing a super-cooled bowl of water, where it crystalizes rapidly outward from one point. Another set of rules produced some interesting shapes which acted a bit like (non-sentient) amoebas.
Almost. The second picture on the link I posted is the “nine-bit” spaceship – your picture plus an extra dot in the upper-right (in yours) corner.
Some days I feel totally invisible, you know?
Within a given simulation, this is trivial. The question was more whether given the state after n iterations, could you find the initial state. The answer is definitively “no”.
[QUOTEIndeed there are. The above-mentioned program also allowed you to change the rules (select which numbers of cells would spawn or kill new cells in the next generation). I don’t recall which specifically were cool. I do remember that one set produced amazing maze-looking designs that would expand rapidly. I remember that it looked a lot like those slow motion films of someone disturbing a super-cooled bowl of water, where it crystalizes rapidly outward from one point. Another set of rules produced some interesting shapes which acted a bit like (non-sentient) amoebas.[/QUOTE]
Diffusion-Limited Aggregations, it souds like. Lots of this sort of thing you can find in A New Kind of Science, but the amount of psychoceramics you have to wade through might be prohibitive.
To definitively answer the first question: minor7flat5’s page also has a list of oscillators, many of which have period higher than two. For period three, example, here’s the smallest one:
XX
X
X
X X
X XXXX
X
And here’s my favourite (it formed “naturally” on a screen saver I had once, and I thought it was cool):
XXX XXX
X X X X
X X X X
X X X X
XXX XXX
XXX XXX
X X X X
X X X X
X X X X
XXX XXX