[uobifxdc] SipHash cellular automata

SipHash, being fast, would be a good hash function for a "random" cellular automata whose state transition function is a hash function.  Using a hash function saves exponential space compared to an explicit lookup table.  Because SipHash is a keyed hash function, it can generate 2^128 different rulesets, 2^128 different universes.  (Some of those rulesets might be identical to each other because we will typically truncate the output of SipHash, as described below.)

If we don't care about cryptographic security, we can consider decreasing the number of SipHash rounds and also consider the Halfsiphash variants.

Number of states can be any power of 2 up to 2^128, corresponding to the output size of SipHash.  For example, we could have 2^24 states corresponding to 24-bit color, depicting cells as pixels with different colors.  Or somewhat fewer states, maybe 2^16 (High Color), because humans have difficulty distinguishing between similar colors in True Color.  Or, cells could be multiple-pixel blocks, allowing portraying even more states.

Isotropic is nice.  The von Neumann neighborhood is nice.  Although it's slightly more difficult for signals to cross in a von Neumann neighborhood than a Moore neighborhood, these universes will likely be so chaotic that trying to organize things like signal routing is probably pointless.  (But will self-organization happen if we wait long enough, if the universe is large enough?)

Another possibility is for the universe to be 3D, but only 3 layers deep.  Let there be 2^8 states per cell, and let the 3 layers correspond to the red, green, and blue color channels, which are overlaid and displayed on screen with 24-bit color.  In general, the number of layers can be any divisor of 24.

Call one state, e.g., state 0, "dead".  Consider hardcoding the rule that a dead cell completely surrounded by dead cells remains dead the next generation.

If the desired number of states is not a power of 2, then we should initialize a random number generator with the output of SipHash, then sample the next state with rejection sampling.  Or, if one does not mind things not being perfectly uniform, simply interpret the output of SipHash as a binary fraction between 0 and 1, multiply by the number of states, and round down.

One can use a hash function and the second-order cellular automata construction to construct a reversible cellular automata.  (Incidentally, this second-order construction is similar to one round of a Feistel network.)  Note that, to initialize a second-order cellular automata, one needs to fully specify the first two generations.  Similarly, to run it backwards, one needs to fully specify the last two generations.  (Previously on constructing reversible cellular automata using reversible ciphers.)

Cellular automata based on hash functions will probably generate only chaotic randomness.  First-order cellular automata might be useful for constructing a large hash function.  Reversible cellular automata might be useful for encryption and decryption.  SipHash as the state transition function for such cellular automata might be insufficient for constructing cellular automata that provide cryptographic security, though lots of imperfections can be concealed by increasing the number of rounds, i.e., generations.