Trying to explain this clearly is harder work than programming it.
Combinations CAs can have between 2 and 10 maximum states per rule. 2 states means the cells can be either on or off. 3 states mean cells have 1 dead state and 2 living states.
The CAs are governed by a rule string.
The rule string needs to be states^2 characters in length. For 2 state rules the rule string will need 4 characters, for 4 states the rule string needs 16 characters, for 10 states the rule string needs 100 characters.
For 2 states the rule string characters are in base 2, so binary values of either 1 or 0. For 3 states the rule string is base 3, so the characters are all between 0 and 2. For 10 states the rule string is base 10, so the characters are all between 0 and 9.
An example 2 state rule is 0110 which creates the following;
An example 3 state rule could be 012120200 that creates the following result;
An example 10 state rule could be
which gives this result;
Number of possible rules
When you have a maximum of 2 states, the rule string has 4 digits of either 0 or 1. The maximum rule string is 1111, which converts to 15 in binary. That gives you 16 possible rules (0000 is also counted) for state 2.
Increasing to 3 states has a 9 digit rule string with base 3 digits. 222222222 is the maximum base 3 number which translates to 19682, so there are 19683 possible 3 state CA rules.
4 states is 16 characters. 3333333333333333 is 4,294,967,295 in decimal, so 4,294,967,296 possible 4 state rules.
10 states is 100 characters. No need for decimal conversion as base 10 is decimal. So 1 with 100 zeros after it possible rules. That may as well be an infinite space to look for rules within.
How the cells are updated
Each cell in the CA is updated by taking into account 2 cells from the previous step. These 2 cells are converted into a decimal value that is used as an index in a rule string to give the new cell state. I bet that makes loads of sense! Let me try and explain.
An example with a 2 state CA using rule 0110, so cells can only be either state 0 or state 1.
If the first step is a single center cell, then the values would look like;
Cell at ? looks at the cell above it and the cell next to it. These are 00. 00 converted to decimal is 0. So we look at the 0th entry in the rule string, so the cell value becomes 0.
Same for the next 3 cells
Then we get to the next ? cell
This cell has the cell above it and next to it as 01. 01 converts to decimal 1, so we look at the 1th (second) digit in the rule string. The second digit in the rule is a 1, so the new cell becomes a 1.
The next ? cell now has 10 above it. This converts to a 2 in decimal, so we look at the third rule digit. Again it is a 1.
The rest of the row has 00 above them, so they get set to 0.
If you continue this process, you get the following result;
Brick wall neighborhood
This CA also uses the brick wall neighborhood idea for selecting neighborhoods. See here for an animation of brick wall. Basically you shift the neighbor locations being checked every other line.
For the Combinations Cellular Automata in this post this means the location of the 2 neighbor cells changes every line.
For even lines you use the cell directly above and to the right. For example, in this next diagram the ? cell would use the 3 and 4 locations.
For odd lines you use the cell to the left and the cell above. This would be the 2 and 3 neighbor cells.
Rule 002200121 behaves similar to Wolfram’s Rule 30. During bulk runs of rules I have seen other results that also look like this one.
Another result that has been observed to occur are these “counting triangles” rules. The splitting of bifurcation like structure on the right hand side is like a binary counter. This is rule 010221200.
Rule 200122011 also gives a binary counter structure.
More example images
See my flickr gallery for more example results.
Combinations Cellular Automata are now included in Visions of Chaos.