Posted by Fred Meinberg.
Paul-Jean Letourneau talking about cellular automata with memory.
Using CA's to emulate CA's with memory
Elementary Cellular Automata are the 256 rules that we know well from NKS - they have a number of symmetries so the actual space of different rules is smaller. He has a nice animation of how the update rules in ECA work, highlighting active cells and which rules are being used.
In CA's with memory (ECAM) we don't look at the center cell of a triplet in a given space, but rather at the cell t-steps above the center cell. Everything else is the same as in a ECA. (Animation really helps understanding this.)
A small difference is that since you're looking two steps back we need two rows as an initial condition.
We can vary the space of rules (changing how many steps back we look), but he follows NKS philosophy and keep things as simple as possible.
So, how do ECAM work? We see an example with rule 30. t=1 and t=3 make the behavior quite simple if we use simple initial conditions. With random initial conditions the t=3 cases look complicated.
If we look at all rules with t=1, we have some changes, and notice that a bunch of them have quite simple behavior. Rule 90 for instance keeps its nested behavior.
t=2 generates more complex behavior from initial conditions. Rule 45 looks interesting to me. Starting them with random initial conditions generates interesting animals. But we move on to emulation.
PJ now shows how we can use conventional CA's to emulate CA's with memory. The trick is to understand that one can use a CA rule with a number of "don't care" cells that we don't keep track of in the evolution of the emulating CA, but that we encode the history of relevant cells. The encoding requires 2^(t+1) colors, we're moving in a very large - 2^2^(t+1) - e space.
There is also another way of emulation - using block cellular automata using blocks of size t+1 x t+1. We use many more colors here: 2^(t+1)^2, so we need a visualization trick, by coloring a whole block with its average color. The emulation of rule 30 show the same division between an ordered area on the left and a chaotic area on the right.
More rules: 22, 62, 110. Overall behavior seems to be preserved using block emulation.
Q&A:
Did you look at the slope between the two boundaries in Rule 30? Not at that one, but other slopes seem to be preserved.
Did you have a closer look at the colors in the block CA's? We could use a mapping function.
Comments