1) What kind of tilings? 2) CAM family.
Harold V. McIntosh
cellular automata, which in turn is relevant to the layout of the CAM
family.
The main neighborhoods for automata are the Moore neighborhoods (an
n-dimensional cube) and the von Neumann neighborhoods (an n-dimensional
cross). They exist for any number of states k, number of dimensions n, and
radii r; hence a Wolfmanlike nomenclature "n-D (k,r) automaton." It makes
sense for r to be half-integral if the width of the neighborhood is even,
but then you would want to stagger alternate generations to get a
symmetric evolution diagram. Both lattices are cubical.
In higher dimensions the only lattices are cubical, although if metric
properties are important, parallelopipeds are also admissable. Whenever
you are willing to allow colored lattices, multiplicities, sublattices,
somewhat irregular lattices, or the like, the number increases
drastically. Most books on crystallography treat two, three, even four
dimensions; many at least comment on still higher dimensional lattices.
For automata, it is hard enough to work with "small" automata, much less
to think about larger ones. A mathematician would prefer "fat"
neighborhoods (Moore neighborhoods) because the evolution function can be
constant outside certain subsets "without any loss in generality"; so a
2-D hexagonal neighborhood is a subset of a 2-D Moore neighborhood. But
electronic engineers would prefer "thin" neighborhoods (von Neumann
neighborhoods) because they have to pay for all the cells (routing space
on the circuit board, extra table lookup memory, and so on).
It may also happen that such things as de Bruijn diagrams are easier to
calculate for cartesian product neighborhoods (Moore neighborhoods) than
for others. Such calculations tend to be prohibitive because of an
exponential increase with the <<volume>> of the neighborhood, not to
mention that they may be noncomputable in full generality in two
dimensions and beyond, whatever the neighborhood layout.
There may be some intrinsic reason to desire a high dimensional automaton.
Analogs between finite difference schemes and partial differential
equations have never worked out very well; but otherwise, matching the
dimension to the number of variables might be seen as a reasonable
decision.
What <<has>> worked out, very well indeed, is to describe transitions
between different nonlinear regimes of the differential equation by
transitions of an appropriate automatom. This lies behind all the
Greenberg-Hastings rules, models of the Zhabotinsky reaction, and so on.
Developing visual techniques and confronting the economics of visual
displays may be the principal reason that we do not see more high
dimensional automata in this category.
Another thing which seems to work very well is embodied in the Margolus
neighborhood, for which different rules are operative at different points
in the lattice, and even at different times. In the CAMs, there is a basic
Moore (k,1\2) neighborhood (e.g. a 2x2 square) with a different rule
operative at each of its corners, which is selected by the board's parity
signals.
Users are generally spared the details of the process, which readily
produces reversible behavior among pointlike "billiard balls". There is a
strong temptation to match the dimension of these automata to a certain
number of degrees of freedom; also quite an art to obtaining or avoiding
the consequences of symmetries of one sort or another. Several of last
week's commentators emphasized these details.
To turn to the CAM family (as described in the Toffoli-Margolis book,
without the latest Automatrix enhancements):
The CAMs consist of four "planes" grouped in two pairs, or half-CAMs. Each
plane is a square lattice, whose cells can be variously interconnected
according to the board options. Matching cells in the four planes are
permanently connected, so a (16,0) automaton is always available. As an
automaton it is trivial, but it is a nice way to think of permuting,
exchanging, copying, complementing, clearing, or setting entire planes. It
is only necessary to load the appropriate rule; the desired effect is
achieved in a single generation.
From there on, things get much more detailled, even without thinking about
how to interconnect the edges of the planes to get bigger planes, tori,
Klein bottles, and so forth. The choice between von Neumann, Moore, or
Margolis neighborhoods affects the number of states which can participate
in the automaton. Each half CAM can support a binary radius one Moore
automaton, two binary or one quaternary radius one von Neumann automata,
or a Margolus automaton.
By exercising ingenuity, binary hexagonal automata or binary radius 1/2
Moore neighborhoods are possible; indeed any neighborhood which is a
subset of the fundamental neighborhood. Likewise trinary von Neumann
automata are possible by foregoing one of the quaternary states. One
dimensional automata can also be represented in various ways.
The other half-CAM can serve as a (4,0) counter, be used to generate
random numbers, contain a cursor, reticule, and commentary, or what not;
all this is described in the book. So, although the owner of a CAM has to
accept <<exactly>> what the CAM offers, the offering is by no means
inconsequential.
This does not mean that the CAM is without either limitations or
inconveniences. Let us accept that we will view a three-dimensional
automaton by displaying a single plane section. If we are willing to load
three consecutive planes into the CAM memory, the central plane can be
evolved, stored, and the planes shifted. Thus in 256 steps, maybe five or
ten seconds, we can obtain one generation of evolution of a 256x256x256
cube, and even view the evolution through a moving cross section.
Here the critical factor is whether the entire state space of three CAM
planes can be swapped in a time comparable with one TV scan, the relevant
unit of time for the CAM. As PC's get faster, the swap is more feasible.
If the CAM had more onboard memory, the swap would be a mere address
switching. In days of yore, the MicroAngelo had an onboard DMA controller.
We don't know the answer to this - we are working on it.
A juggling act of a different sort occurs when there is reason to swap the
lookup table defining the rule; evidently the less of the table that has
to be loaded, the faster and easier the doing. One way the necessity can
arise is to let the CAM do its own housekeeping. Besides the (16,0)
automaton which rearranges entire planes, there are others which shift,
rotate, or reflect one or more planes. By creating masking planes and
storage planes, it becomes possible to edit the remaining
planes.
All in all, many things which might be done within the PC memory with
swapping, can be provoked directly within the CAM's own memory. Which
alternative is more economical depends somewhat on circumstances, on just
what is going to be done.
But all of this soon exhausts the capacity of the lookup table, even
allowing for alternate rules and multiple planes. Maybe it is time to buy
that second CAM.
---
Harold V. McIntosh |Depto. de Aplicacion de Microcomputadoras
mcin...@uapnx1.dgsca.unam.mx |Inst. de Ciencias, UAP, Apdo. Postal 461
MCINTOSH@UNAMVM1 (BITNET) |72000 Puebla, Pue., Mexico