Monday, February 08, 2021

[sbmboewn] Moore neighborhood differentiating edges from corners

consider cellular automata using the Moore neighborhood but treating diagonal neighbors separate from orthogonal neighbors.

we keep the biologically inspired totalistic rule structure from Conway's Game Of Life.  both births and staying alive happen only in Goldilocks zones between isolation and overcrowding.  we count the number of possibilities of Goldilocks zones.

for each neighbor type (orthogonal or diagonal), the count can range from 0 to 4, so 5 possibilities.  for each neighbor type, these are the possible rules satisfying the Goldilocks restriction, where 1 indicates being in the Goldilocks zone:

00000 00001 00010 00011 00100 00110 00111 01000 01100 01110 01111 10000 11000 11100 11110 11111

these are bit strings that do not contain the subsequence 101 (NB: subsequence not substring).  equivalently, the regular expression 0*1*0*.  there are 16 possibilities (a triangular number plus 1).  this is less than the 2^5 = 32 possibilities without the Goldilocks restriction.

considering both neighbor types together yields a 5x5 Boolean grid.  we want the 1D Goldilocks constraint to be true along each row and column of the grid.  a computer program finds 89630 = 2*5*8963 Goldilocks rule possibilities encodable in a 5x5 grid.  this is less than the 16^5 = 2^20 =1048576 from repeating the 1D result 5 times, and much less than the 32^5 = 2^5^2 = 2^25 = 33554432 ways to fill a 5x5 grid without restrictions.  the computer program ran through the 16^5 possibilities of rows (straightforward brute force) and tested each one for whether it satisfied the Goldilocks restriction on columns.  it could have have been further optimized.

if we require that a dead cell completely surrounded by dead cells must remain dead, there remain 71054 = 2*35527 rule possibilities.  adding no additional constraints to staying alive, the product is 6368570020.  some rules might be interesting.  one is identical to Conway's Game Of Life.

future work: the birth Goldilocks range of neighbor populations must be a subset of the staying-alive Goldilocks range.

No comments :