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:
“The mere existence of an additional child or children in the family could signify Less. Less time alone with parents. Less attention for hurts and disappointments. Less approval for accomplishments. . . . No wonder children struggle so fiercely to be first or best. No wonder they mobilize all their energy to have more or most. Or better still, all.”
—Adele Faber (20th century)
“However patriarchal the world, at home the child knows that his mother is the source of all power. The hand that rocks the cradle rules his world. . . . The son never forgets that he owes his life to his mother, not just the creation of it but the maintenance of it, and that he owes her a debt he cannot conceivably repay, but which she may call in at any time.”
—Frank Pittman (20th century)