Dimension and memory limits

[BorjaEst]

Taking into account a rule is a dtype="uint8" (generating a maximum of 256 possible states), the following combinations produce the following rule sizes:

• ndim=1, r=1, states=2 --> rule.shape==[2]**3**1 => 8B rule size (elementary)
• ndim=1, r=1, states=3 --> rule.shape==[3]**3**1 => 27B rule size (ternary, r1)
• ndim=1, r=2, states=2 --> rule.shape==[2]**5**1 => 243B rule size
• ndim=2, r=1, states=2 --> rule.shape==[2]**3**2 => 512B rule size (2dim, r1)
• ndim=2, r=1, states=3 --> rule.shape==[3]**3**2 => 19.22kB rule size
• ndim=2, r=2, states=2 --> rule.shape==[2]**5**2 => 33.55MB rule size
• ndim=3, r=1, states=2 --> rule.shape==[2]**3**3 => 128.0MB rule size (3dim, r1)
• ndim=4, r=1, states=2 --> rule.shape==[2]**3**4 => 2.42YB rule size(4dim, r1)

Therefore although theorically possible, technically is impossible to map currently every rule using the current structure.

[BorjaEst]

One of the targets of this library is the posibility to explore all the rules available on a space. Therefore, the typical solution of sum(neighbours) is not suitable here. For example, in elementary case, rules such 250 might not be explored on this way, as
[0,0,1] evolves in 1, but [0,1,0] evolves in 0.

However, there might be a way to better express rules and reduce the size of the expresion by using simetry. See Reflections and complements from elementary automata. This simerties probably multiply geometrically with dimensions.

[BorjaEst]

Following Journal of Statistical Physics, Vol. 38. Nos. 5/6. 1985 , the following number of possible rules apply for a 2 dimension 9-neighbor(Moore, r=1) CA with 2 possible states:

• General: [2]*9 --> 2**512 ~= 10**154 rules
• Rotationally symmetric: [?]*? --> 2**140 ~= 10**42 rules
• Reflection symmetric: [?]*? --> 2**288 ~= 10**87 rules
• Completely symmetric: [?]*? --> 2**102 ~= 10**30 rules
• Outer totalistic: [2,9] --> 2**18 ~= 10**5 rules
• Totalistic: [9] --> 2**9 == 512 rules

The case of rotatinally symmetric seems to cover all cases so it might be the most relevant for this package.

[BorjaEst]

All rules have a inversed equivalent. For example, in elementary CA rule 255 is inverse equivalent to rule 0. However note this does not reduce the number of rules to half due to the fact that some are symetric, therefore the inverse are themselves. For elementary CA such rules are:

{15, 23, 43, 51, 77, 85, 105, 113, 142, 150, 170, 178, 204, 212, 232, 240}  # len(): 16

The total of unique rules (removing inversed equivalents) are 136 for elementary CA.