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:
“the dull thunder of approximate words.”
—Thom Gunn (b. 1929)
“Every man is in a state of conflict, owing to his attempt to reconcile himself and his relationship with life to his conception of harmony. This conflict makes his soul a battlefield, where the forces that wish this reconciliation fight those that do not and reject the alternative solutions they offer. Works of art are attempts to fight out this conflict in the imaginative world.”
—Rebecca West (1892–1983)