Simulation By Conventional Cellular Automata
As Toffoli and Margolus write, the block cellular automaton model does not introduce any additional power compared to a conventional cellular automaton that uses the same neighborhood structure at each time step: any block cellular automaton may be simulated on a conventional cellular automaton by using more states and a larger neighborhood. Specifically, let the two automata use the same lattice of cells, but let each state of the conventional automaton specify the state of the block automaton, the phase of its partition shifting pattern, and the position of the cell within its block. For instance, with the Margolus neighborhood, this would increase the number of states by a factor of eight: there are four possible positions that a cell may take in its 2 × 2 block, and two phases to the partition. Additionally, let the neighborhood of the conventional automaton be the union of the blocks containing the given cell in the block cellular automaton. Then with this neighborhood and state structure, each update to the block automaton may be simulated by a single update to the conventional cellular automaton.
Read more about this topic: Block Cellular Automaton
Famous quotes containing the words simulation and/or conventional:
“Life, as the most ancient of all metaphors insists, is a journey; and the travel book, in its deceptive simulation of the journey’s fits and starts, rehearses life’s own fragmentation. More even than the novel, it embraces the contingency of things.”
—Jonathan Raban (b. 1942)
“Westminster Abbey is nature crystallized into a conventional form by man, with his sorrows, his joys, his failures, and his seeking for the Great Spirit. It is a frozen requiem, with a nation’s prayer ever in dumb music ascending.”
—M. E. W. Sherwood (1826–1903)