next up previous contents
Next: Cycles in space Up: What to look Previous: Blocking transformations

Tailor made automata

Two contrasting ways to approach automata theory are to begin with an automaton to see how it evolves, or to think of an interesting evolution and try to select the rules accordingly; the latter were von Neumann's and Conways approaches. From either aspect it is convenient to have a random number generator available; in the first instance for following the evolution of typical configurations, in the second it can even provide the rule to study.

A more deliberate approach begins specific plans for the evolution, and attempts to deduce a suitable rule. Suppose that the objective is a slow glider, that advances two cells in four generations. There is at least a rectangle to be considered, to accommodate the generations, the displacement, and the neighborhood length. The evolution of at least 25 neighborhoods must be defined, but fewer may suffice on symmetry grounds; at least five if every row is the same.

Neither , , nor automata look promising with 4, 8, and 9 distinct neighborhoods, respectively; but any other state-radius combination beginning with the 16-neighborhood ought to have rules with such a glider. These figures may not be precise, but they lend plausibility to the conjecture that there is an automaton of some minimal complexity for almost any task that can be described by a sample evolution.

One typical task which is quite instructive is to emulate a Turing machine; Albert and Culick [3] suggest one approach. Just as there are simpler Turing machines than the universal machine, there are numerous simple automata to be designed. Binary counters are a good example; their existence shows that there are automata with very long transients, also with very long cycles. A challenge might be to come as close as possible to the theoretical upper limit, a sort of variant on the ``busy beaver'' problem for Turing machines.

Another traditional exercise is the ``firing squad problem,'' wherein there is a reserved state, ``fire'' which all the cells of an automaton of arbitrary length are to enter simultaneously, none having occupied it previously [83,114]. It is a whimsical one-dimensional variant of one of the components of von Neumann's constructor; which was supposed to activate each finished object, as a finishing touch when it was finally completed and turned loose on its own.



next up previous contents
Next: Cycles in space Up: What to look Previous: Blocking transformations



Harold V. McIntosh
E-mail:mcintosh@servidor.unam.mx