An 'interesting' property of this cellular automaton is that the conditions for birth match the conditions for survival; a cell does not participate in its subsequent state in the next generation. (The same is true for
3/4 Life.)
For two-state cellular automata with
honeycomb neighbourhood, this property allows to express the set of rules as a 6-input Boolean function (instead of a 7-input function in the general case) so it may be easier to find an efficient Boolean circuit that implements the function. (See also
a related forum thread.) A 6-input function can be reduced to a pair of 5-input functions:
Code: Select all
f(n,e,h,s,w,l) := (f1(n,e,h,s,w) and l) or (f0(n,e,h,s,w) and not l);
5-input functions
were investigated, and every such function can be implemented with at most 12 two-input gates.
This gives an upper bound of (27 = 12 x 2 + 3) gates.
For B2o45/S2o45H, I think each of two needed 5-input functions
can be implemented with only 10 gates.
This leads to an upper bound of (23 = 10 x 2 + 3) gates:
Code: Select all
// neighbourhood (r, v are ignored for the honeycomb neighbourhood):
// l n r
// w c e
// v s h
// Reference for the single-letter notation for neighbours:
// https://web.archive.org/web/20240907235728/https://conwaylife.com/forums/viewtopic.php?f=7&t=2036&start=625#p51158
q1 := n xor h; // 1 gate
q2 := e xor q1; // 1 gate
r0 := (s or e) and not ((q2 and not h) or (((q2 xor s) or (w and not q1)) xor w)); // 8 gates
q3 := e xor h; // 1 gate
q4 := (h xor s) or q3; // 2 gates
r1 := ((((n or w) xor q4) or (q3 xor s)) and not (n and w)) xor q4; // 7 gates
result := (r1 and l) or (r0 and not l); // 3 gates
Intermediate results can be shared between the two 5-input 1-output computations.
I can get an upper bound of (21 = 18 + 3) gates this way:
Code: Select all
q1 := n xor e; // 1 gate
q2 := s xor q1; // 1 gate
q3 := w xor q2; // 1 gate
q4 := h xor q3; // 1 gate
q5 := h and s; // 1 gate
q6 := q1 and not q3; // 1 gate
q7 := n and not q6; // 1 gate
r0 := (e or s) and not (q6 or (q4 and not (n and q5))); // 5 gates
r1 := ((q5 xor not w) and (h xor q2 xor q7)) xor (q4 or q7); // 6 gates
result := (r1 and l) or (r0 and not l); // 3 gates
It may be possible to get a better upper bound, either by solving the 5-input 2-output circuit in at most 17 gates, or by directly solving the 6-input 1-output circuit in at most 20 gates.
Is it feasible to determine the lowest possible cost (in 2-input 1-output gates) for this CA?
