Coupling Cellular Automata with Substitution Systems

A common phenomenon in natural and man-made systems is that an underlying system will evolve, and periodically its evolution will be altered by an external system. Sometimes these perturbations are random. But at other times, they are the result of some definite structure forming in the underlying evolution. In this Demonstration, we show a minimal version of such deterministic perturbation, where a substitution system affects each step of the evolution of a cellular automaton.

At each step, a given cellular automaton executes a step of computation. Then, using this as input, we run a substitution system that transforms each occurrence of a specific sequence of colors into another specific sequence. Finally, the new line of cells is fed to the cellular automaton, which then restarts this cycle.

The interplay between these two systems results in very rich behavior. In fact, it seems that almost any underlying cellular automaton rule is capable of achieving all four Wolfram classes with the right choice of substitution rules.

Increasing the sizes of the blocks will statistically reduce the number of replacements executed by the substitution system. An interesting thing to observe in this Demonstration is how the impact of the substitution system varies by increasing or decreasing the block sizes. This sometimes results in the cellular automaton behavior continuously varying between that of the hybrid system and that of the pure cellular automaton.

The system given here can be viewed as a model of the process of idealization breakdown in scientific models. In this case, the cellular automaton corresponds to the scientific model, while the substitution system is an effect not captured by the model that becomes important in certain state configurations. The question then is, just how often does the substitution system need to fire in order to have a significant effect on the behavior of the system according to some measure?

The system can also be viewed as a model of policymaking in human affairs, and in particular the imposition of global rules in an underlying system. An idealized government can be thought of as influencing society by making a relatively small number of changes (compared to the overall size of the system) in society's otherwise normal operation. The question is, in what ways can these outside perturbations influence the behavior of the system, and how general or specialized do the replacements need to be to achieve a particular purpose? And, are there behaviors that are simply not achievable given certain constraints?