-- you have earned Featured Contributor Badge

Your exceptional post has been selected for our editorial column Staff Picks http://wolfr.am/StaffPicks and Your Profile is now distinguished by a Featured Contributor Badge and is displayed on the Featured Contributor Board. Thank you, keep it coming, and consider contributing to the The Notebook Archive!

As an answer to Vitaliy's question, you can use the CellularAutomaton function, but there is subtle issue with the boundary conditions. In the Diagonal CA, you start with a single gray cell (value 1 out of 1,2, or 0) and when you need a new boundary cell it is always white (or 0). In the CellularAutomaton function, if the rule sends white cells to white (or quiescent) then it is the same, but otherwise the boundary cells are not necessarily going to be white (or 0). Because of this the evolutions are not the same in general.

But when the rule is quiescent then they are the same. One other difference should be mentioned, that Ed's rule numbering is backwards from the usual conventions. So Ed's rule 420 = 0 1 2 0 1 2 0 = CellularAutomaton 588 = 0 2 1 0 2 1 0, which is quiescent. The rule type is a second order CA because it depends on the previous diagonal and the diagonal before that. Here is an implementation as a radius 1/2 rule.

    hist=CellularAutomaton[{588, {3, {{1, 0}, {1, 1}}}, 1/2, 2},  
PadLeft[{{1}}, {2, 32}, 0, {0, 31}], 30];
    Graphics[MapIndexed[If[#2[[1]] < #2[[2]], Nothing, 
{GrayLevel[1 - #/2], Rectangle[{#2[[2]], 30 - #2[[1]] + #2[[2]]}]}] &, hist, {2}]]

(I'd post an image, but something strange happened with the interface.)

Todd, how would the 3D diagonal CA be set up? It seems obvious that we should find out if a "1D" cellular automaton can build a menger sponge.

The 3D case is more complicated to render, and the choice of rendering determines where the offsets go with the weighting. Please forgive me for posting a guess.

    ArrayPlot[CellularAutomaton[{114, {2, 
{{{1, 0}, {0, 0}}, {{1, 0}, {1, 1}}, {{1,1}, {0, 1}}}}, 
{1/2, 1/2}, 3}, {{{{1}}, {{0}}, {{0}}}, 0}, {{{30}}}]]

Not a completely random guess. Look at this graphic, showing the diagonal sheets. It is clearly an order 3 rule. Each sheet is a square lattice (but at a funny angle), and the first and second step back each have three cells, being the closest 3 in the parallelogram. Some combination with one 1 and 3 1's and 3 1's for weights will be correct.

Graphics[MapIndexed[{Hue[Mod[#2[[1]]/5, 1]], Point[#]} &, 
  Select[Union[#.{{1, 1}, {-1, 0}, {0, -1}}] & /@ 
    SortBy[MaximalBy[GatherBy[Tuples[Range[5], 3], #.{1, 1, 1} &], 
      Length, 3], #[[1]].{1, 1, 1} &]

This is one of the reversible rules? 214R ?

It's a second order rule, and there are a few ways of doing that. In general the rule is a list of length four where the last number is the order of the rule.

The best implementation is to convert to a four color rule and then take it Mod[_,2] Going to four colors encodes the previous state. There are more details in my conference presentation from NKS 2007 which was about 37R. Using the general method of going from second order to first order leads to a faster implementation in CellularAutomaton.

RevTo4ColorRule[rn_] := 
 FromDigits[
  FromDigits[{Mod[#[[2]], 2], 
      Mod[Reverse[IntegerDigits[rn, 2, 8]][[
         FromDigits[Mod[#, 2], 2] + 1]] + Quotient[#[[2]], 2], 2]}, 
     2] & /@ Tuples[{3, 2, 1, 0}, 3], 4] 

Yes, that's a good way too. You can't go wrong with powers of two.