The Q*Bert and Margolus neighbourhoodsThere exists an isomorphism between automata using the Q*Bert neighbourhood, and one of the two alternating sub-lattices generated by the 8-state triangular scheme of Morita and Ueno.The isomorphism can be seen relatively easily by super-imposing the differing grids the automata work on, and looking at cells overlapping one sublattice of the triangular automaton. The Q*Bert cells follow the cells of one of the sublattices exactly. The second independent sublatice may not always be very useful. For example, in a non-uniform implementation designed to perform computations, it shares the same cells - and is likely to be computing a closely related function to the first sub-lattice. In such cases, it seems that eliminiating the second layer could potentially save three bits per cell of writable state memory. However, there are other costs in using the Q*Bert neighbourhood. It employs different functions on alternate time steps - and distinguishing between alternate time steps may cost a bit in each cell. A similar isomorphism demonstrably exists between the Margolus neighbourhood and one of the two alternating sub-lattices generated by the Isometric von Neumann neighbourhood. In order to observe this relationship one of the neighbourhoods must be rotated through 45 degrees and resized appropriately before the relationship between the cells becomes clear. Hopefully a diagram of this will follow at some point.
Adding states to eliminate sub-latticesIt is often possible to change an automata which divides the plane into alternating sublattices, into one which does not by the addition of an extra bit per cell, that can act as a bridge between them.If the automata subsequently built with such a scheme are uniform, this works well - while if such automata are non-uniform, the result can be somewhat confusing.
The X and Y neighbourhoodsThere are also isomorphisms between the X neighbourhood and the 16-state rectangular scheme of Morita and Ueno, and between the Y neighbourhood and the 8-state triangular scheme of Morita and Ueno.The X and Y neighbourhoods contain two copies of their related automata, as wholly independent sublattices.
Signal distance considerationsIt is interesting to measure the maximum distance a signal has to cross while a given cell is being updated.The maximum absolute distance from a point in the domain to a point in the range is likely to limit the speed of update of the automata - assuming signal propagation speed across this distance is an important factor.
|