Thursday, February 27, 2014

[jrlnfbsr] Random cellular automata

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?

Previous thoughts.

No comments :