Composite automata

Composite automata

Cellular automata can be combined by several sorts of composition.

Spatial composition

Finite automata can be combined with other finite automata to make larger automata by simply laying them down adjacent to one another - or on top of each other. Sometimes, sparse connections can usefully be made between them.

One possible application of this technique is to combine linear and non-linear automata to create a secure random number generator with a guaranteed high period.

It is diffucult to guarantee a large period in a typical highly non-linear structure. On the other hand, it is relatively easy to make linear systems with maximal periods. By linking two such systems together, a lon-linear system with a demonstrably large period may be constructed.

Temporal composition

Another way to combine two automata is to temporally interleave them. This means using different update rules in alternation.

Temporal composition can often result in an increase in the radius of the neighbourhood of the composite automata - but does not always not do so. See my pages on Constructing Honeycomb automata and Constructing Moore automata for an example of the composite automata having the same radius as its components.

Combined spatial and temporal composition

This technique can be used to construct automata in higher dimensions than the dimensions of the components.

As an example, I'll show briefly how to construct a Moore neighbourhood automata from a Wolfram neighbourhood one.

(t & 1) = 0 (t & 1) = 1
(t & 1) = 0   (t & 1) = 1

These two diagrams are intended to indicate two arrays of Wolfram neighbourhood automata.

The 1D automata run through the two-dimensional grid of cells horizontally on the left and vertically on the right.

If a composite automata is formed from the application of these two configurations on alternate timesteps, the result is a Moore neighbourhood automaton:

The method could be used to construct invertible Moore automata from invertable Wolfram automata.

This sort of technique could obviously be used to construct other types of higher-dimensional automata.

Tim Tyler | Contact |