Nand expressions
If one allows a depth of at most 2n any n-input Boolean function can be obtained just by combining 2-input Nand functions. (See page 807.) (Note that unless one introduces an explicit copy operation—or adds variables as in the previous note—there is no way to use the same intermediate result multiple times without recomputing it.)
The pictures below show the distributions of numbers of Nand operations needed for all 22n n-input Boolean functions. For n = 2, the largest number of such operations is 6, achieved by Nor; for n = 3, it is 14, achieved by Xor (rule 150); for n = 4, it is 27, achieved by rule 5737, which is Not[Xor[##]] & except when all inputs are True. The average number of operations needed when n = 2, 3, 4 is about {2.875, 6.09, 12.23}.
The maximum depths for the expressions of minimal size are respectively 4, 6 and 7, always achieved among others for the function taking the most Nand operations. The total numbers of functions involving successive depths are: n = 2: {2, 3, 5, 6}, n = 3: {3, 6, 22, 99, 72, 54}, n = 4: {4, 10, 64, 923, 9663, 54622, 250}, corresponding to averages {2.9, 4.5, 5.8}.
The following generates explicit lists of n-input Boolean functions requiring successively larger numbers of Nand operations:
Map[FromDigits[#, 2] &, NestWhile[Append[#, Complement[Flatten[Table[Outer[1 - Times[##] &, #〚i〛, #〚-i〛, 1], {i, Length[#]}], 2], Flatten[#, 1]]] &, {1 - Transpose[IntegerDigits[Range[2n] - 1, 2, n]]}, Length[Flatten[#, 1]] < 22n &], {2}]
The results for 2-step cellular automaton evolution in the main text were found by a recursive procedure. First, expressions containing progressively more Nand operations were enumerated, and those for functions that had not been seen before were kept. It then turned out that this made it possible to get to expressions at least half as large as any needed, so that it could be assumed that remaining expressions could be decomposed as f[##] ⊼ g[##] &, where f had already been found. The pictures below show some more results obtained in this way.