CMPS272, Winter 2007, Section 01: Rule150

Rule 150 is a 1-dimensional 2-state cellular automata which updates the state of each cell at time t+1 with the xor of the cell and its neighbors at time t.

This leads to some interesting properties, for one thing, as the wolfram page states, the cellular automata is additive : namely the evolution of the CA for the sum (modulo 2) of two starting states is the sum (modulo 2) of the evolutions of each start state independently.

Another property of Rule 150, which makes it unique even among "additive" cellular automata, is the (easily proven) fact that for any integer k, the cellular automata after 2^k steps will be a copy of the start state shifted left by 2^k added (modulo 2) with a copy of the start state shifted right by 2^k. This makes it fairly easy to analyze the max cycle time for cellular automata of this form. If the world is a 1-dimensional torus with 2^l states, then any start state will repeat after 2^l iterations.

I think (although I have not proven it) that if the discrete log (base 2) of 1 modulo the world size is p, then the maximum cycle size will be at most p.

-- MichaelSchuresko? - 09 Jan 2007