Approximate Solutions
Gács, Kurdyumov, and Levin found an automaton that, although it does not always solve the majority problem correctly, does so in many cases. In their approach to the problem, the quality of a cellular automaton rule is measured by the fraction of the possible starting configurations that it correctly classifies.
The rule proposed by Gacs, Kurdyumov, and Levin sets the state of each cell as follows. If a cell is 0, its next state is formed as the majority among the values of itself, its immediate neighbor to the left, and its neighbor three spaces to the left. If, on the other hand, a cell is 1, its next state is formed symmetrically, as the majority among the values of itself, its immediate neighbor to the right, and its neighbor three spaces to the right. In randomly generated instances, this achieves about 78% accuracy in correctly determining the majority.
Das, Mitchell, and Crutchfield showed that it is possible to develop better rules using genetic algorithms.
Read more about this topic: Majority Problem (cellular Automaton)
Famous quotes containing the words approximate and/or solutions:
“A worker may be the hammer’s master, but the hammer still prevails. A tool knows exactly how it is meant to be handled, while the user of the tool can only have an approximate idea.”
—Milan Kundera (b. 1929)
“Football strategy does not originate in a scrimmage: it is useless to expect solutions in a political compaign.”
—Walter Lippmann (1889–1974)