Tuesday, March 14, 2006

Cellular automaton puzzle

Here are the cells of a 1D cellular automaton:


+--+--+--+--+
|a0|a1|a2|a3| ...
+--+--+--+--+


Instead of a finite number of states the ai are integers.

Here's the update rule:

a0 <- a1
ai <- (i-1)*left+(i+1)*right, i>0

where left and right refer to the cells to the left or right of ai.

We start it in this state:

+--+--+--+--+--+--+--+
| 1| 0| 1| 0| 0| 0| 0| ... all zeroes
+--+--+--+--+--+--+--+


What is the significance of the numbers that appear in the leftmost cell?

If you can't figure it out the answer is here. (Though it might be easier to work it out for yourself than read that paper!)

I think this may actually be useful. I've spent quite a bit of time recently writing code to do the sorts of things that these automata do - but these automata may do it better.

No comments:

Blog Archive