Invertible Honeycomb automata

Invertible Honeycomb automata

The basics of this construction technique are described here.

The idea is to generate a "composite" automata, which transmits information in all directions through the automata, and uses the Honeycomb neighbourhood.

This is desirable since it allows the automata to be updated with both automata simultaneously. Because the neighbourhood's "radius" remains small, the composite update function can retain its speed.

Note that the inverse automata has as large a domain as possible - and as a consequence can thus only be calculated relatively slowly.

If this asymmetry is not considered desirable, a number of short paths - rather than one long one - could perhaps be employed.

First a path is constructed through the automata. This must pass through every cell. There are also a number of other constraints placed on the route it takes - but for now, we will simply exhibit a suitable path:

Then, each cell is allocated an update function which is applied on "even" timesteps.

This function is such that the state of each cell depends only on it's previous state, and the state of up to two of its neighbours in the previous generation.

The two neighbours are chosen in such a way that they are closer to the end of the path in the bottom left-hand corner (with distance being measured along the path).

This is illustrated in the following diagram:

Blue lines from a cell connect it to up to two neighbours.

Next, an update function which is applied on "odd" timesteps is allocated to each cell.

As before, this function is such that the state of each cell depends only on it's previous state, and the state of up to two of its neighbours in the previous generation.

This time, the two neighbours are chosen in such a way that they are closer to the end of the path in the top right-hand corner (again, with distance being measured along the path).

The following diagram shows this situation:

Red lines from a cell connect it to up to two neighbours.

Note that the generation of the rules shold follow the constraints laid down in the description of how to ensure reversibility. Essentially, the dependency on the central cell should be with an Exclusive Or function. (For more details, see here).

Combining the last two diagrams by superposition yields:

If you now consider the effect of applying both updates simultaneously, you will see that the resulting composite automata uses the Honeycomb neighbourhood.

A diagram should help visualise what is happening:

If you apply the "even" (blue) update function first, and then apply the "odd" (red) update function, you will see that the state of the white cells in the diagram above depend on the state of the seven cells in the shaded regions.

A single "red" function is involved. This function operates on a domain of three cells, each of which is the result of applying a single "blue" update function to the initial state.

Examination of the diagram before this one should indicate that the honeycomb neighbourhood may be used for every cell in the automata (with suitable truncations applied at the edges).