Under the constraint of rotational and mirror symmetry, the 24 squares within distance 2 (chess king moves) of a cell fall into 4 equivalence classes of 4 cells each and 1 equivalence class (the knight move) of 8 cells. Assuming a cell can only have 2 states, the sum of the living cells within an equivalence class can range from 0 to N, so N+1 possibilities. Therefore, we need a binary lookup table of 2*5^4*9 = 11250 entries to determine the next state. The extra factor of 2 is for the cell itself. There are 2^11250 possible rules.
How can we express (and count) the symmetry constraint if there are more than 2 states? I suspect the sum method is not the most general way of preserving symmetry even for 2 states.
I like this distance 2 neighborhood over the distance 1 neighborhood in Conway's Game Of Life because it provides more ways for signals to cross.
Symmetry is not necessarily a desirable feature. Without symmetry, there would be 2^2^25 = 2^33,554,432 possible rules.
We would somehow like to prune the uninteresting rules, e.g., all cells immediately die.
The motivation is for a Turing-complete hash function, but being able to specify an arbitrary (interesting) rule might give a tremendous advantage to FPGAs.
No comments :
Post a Comment