Additional Rules
Toffoli and Margolus suggest two more reversible rules for the Margolus neighborhood with two-state cells that, while not motivated by physical considerations, lead to interesting dynamics.
In the "Critters" rule, the transition function reverses the state of every cell in a block, except for a block with exactly two live cells which remains unchanged. Additionally, blocks with three live cells undergo a 180-degree rotation as well as the state reversal. This is a reversible rule, and it obeys conservation laws on the number of particles (counting a particle as a live cell in even phases and as a dead cell in odd phases) and on the parity of the number of particles along diagonal lines. Because it is reversible, initial states in which all cells take randomly chosen states remain unstructured throughout their evolution. However, when started with a smaller field of random cells centered within a larger region of dead cells, this rule leads to complex dynamics similar to those in Conway's Game of Life in which many small patterns similar to life's glider escape from the central random area and interact with each other. Unlike the gliders in Life, reversibility and the conservation of particles together imply that when gliders crash together in Critters, at least one must escape, and often these crashes allow both incoming gliders to reconstitute themselves on different outgoing tracks. By means of such collisions, this rule can also simulate the billiard ball model of computing, although in a more complex way than the BBM rule. The Critters rule can also support more complex spaceships of varying speeds as well as oscillators with infinitely many different periods.
In the "Tron" rule, the transition function leaves each block unchanged except when all four of its cells have the same state, in which case their states are all reversed. Running this rule from initial conditions in the form of a rectangle of live cells, or from similar simple straight-edged shapes, leads to complex rectilinear patterns. Toffoli and Margolus also suggest that this rule can be used to implement a local synchronization rule that allows any Margolus-neighborhood block cellular automaton to be simulated using an asynchronous cellular automaton. In this simulation, each cell of an asynchronous automaton stores both a state for the simulated automaton and a second bit representing the parity of a timestamp for that cell; therefore, the resulting asynchronous automaton has twice as many states as the automaton it simulates. The timestamps are constrained to differ by at most one between adjacent cells, and any block of four cells whose timestamps all have the correct parity may be updated according to the block rule being simulated. When an update of this type is performed, the timestamp parities should also be updated according to the Tron rule, which necessarily preserves the constraint on adjacent timestamps. By performing local updates in this way, the evolution of each cell in the asynchronous automaton is identical to its evolution in the synchronous block automaton being simulated.
Read more about this topic: Block Cellular Automaton
Famous quotes containing the words additional and/or rules:
“Dog. A kind of additional or subsidiary Deity designed to catch the overflow and surplus of the world’s worship.”
—Ambrose Bierce (1842–1914)
“One might get the impression that I recommend a new methodology which replaces induction by counterinduction and uses a multiplicity of theories, metaphysical views, fairy tales, instead of the customary pair theory/observation. This impression would certainly be mistaken. My intention is not to replace one set of general rules by another such set: my intention is rather to convince the reader that all methodologies, even the most obvious ones, have their limits.”
—Paul Feyerabend (1924–1994)