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)
“The line that I am urging as today’s conventional wisdom is not a denial of consciousness. It is often called, with more reason, a repudiation of mind. It is indeed a repudiation of mind as a second substance, over and above body. It can be described less harshly as an identification of mind with some of the faculties, states, and activities of the body. Mental states and events are a special subclass of the states and events of the human or animal body.”
—Willard Van Orman Quine (b. 1908)