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:
“All fashions are charming, or rather relatively charming, each one being a new striving, more or less well conceived, after beauty, an approximate statement of an ideal, the desire for which constantly teases the unsatisfied human mind.”
—Charles Baudelaire (1821–1867)
“Those great ideas which come to you in your sleep just before you awake in morning, those solutions to the world’s problems which, in the light of day, turn out to be duds of the puniest order, couldn’t they be put to some use, after all?”
—Robert Benchley (1889–1945)