MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Does this 2D cellular automaton have a known name and history?

  • n colors (numbered 1 to n), assigned randomly at the start.
  • For each generation, every cell that has at least one neighbour cell with a color that is one higher changes its color to that "next higher" color. Additionally, the "lowest" color is considered "next higher" to the highest one.
  • Emergent behaviour shows up best around n=16, disappears for much higher or much lower n

I have it implemented on my website so you can see it in action.

I saw this ages ago and always remembered it as a great example of emergent behaviour, but can't remember what it was called, and couldn't find it on Wikipedia or Wolfram Mathworld.

share|cite|improve this question
Sounds familiar but I can't quite place it off the top of my head. Places to look would be the chapters on cellular automata in Gale's "Tracking the automatic ant", and of course Gardner's books and perhaps Hofstadter's collections from Sci Am. – Alon Amit Apr 5 '10 at 22:39
up vote 10 down vote accepted

Cyclic cellular automaton

share|cite|improve this answer
So obvious when you know it... Thanks! – Michael Borgwardt Apr 5 '10 at 23:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.