[Cellular automata with] two-cell neighborhoods

By having cells on successive steps be arranged like hexagons or staggered bricks, as in the pictures below, one can set up cellular automata in which the new color of each cell depends on the previous colors of two rather than three neighboring cells.

With k possible colors for each cell, there are a total of k^^{k}^^{2} possible rules of this type, each specified by a k^^{2}-digit number in base k (7743 for the rule shown above). For k=2, there are 16 possible rules, and the most complicated pattern obtained is nested like the rule 90 elementary cellular automaton. With k=3, there are 19,683 possible rules, 1734 of which are fundamentally inequivalent, and many more complicated patterns are seen, as in the pictures at the top of the next page.

With rule given by IntegerDigits[num,k,k^^{2}] a single step of evolution can be implemented as

CAStep[{k_,rule_},a_List]:=rule[[k^^{2}-RotateLeft[a]-k a]]