Let the next state of a cell be a hash-like function of the neighborhood (including the current state). The key idea is that a hash-like function makes the next state uniformly distributed, and we hypothesize that this prevents a (say, random) population from quickly converging to, say, all dead.
The simplest way to create such rules is a randomly populated lookup table, taking care to avoid biases in distribution of the next state. Requiring large lookup tables might be useful to make a computation memory bound in the style of Scrypt. However, such tables can quickly become extremely large.
Another way is to apply modular addition, bit-rotation (assuming cells have 2^N states), and xor to the neighborhood cells, taking ideas from recent ARX ciphers. All other block cipher primitives (e.g., S-boxes) are also fair game. Assuming a finite universe, we are essentially jumbling up a large block like a block cipher.
Useful might be Fredkin and Toffoli gates which preserve the number of bits.
Finally, we can go the whole 9 yards and apply an actual cryptographic function to the neighborhood, for example, HMAC, with each key providing a separate rule set.
Create a simple demonstration of a 2-state, 2-dimensional CA where the next state is Xor of the neighborhood. What happens to a random initial population?
No comments :
Post a Comment