Majority Problem (cellular Automaton)
The majority problem, or density classification task is the problem of finding one-dimensional cellular automaton rules that accurately perform majority voting.
Using local transition rules, cells cannot know the total count of all the ones in system. In order to count the number of ones (or, by symmetry, the number of zeros), the system requires a logarithmic number of bits in the total size of the system. It also requires the system send messages over a distance linear in the size of the system and for the system to recognize a non-regular language. Thus, this problem is an important test case in measuring the computational power of cellular automaton systems.
Read more about Majority Problem (cellular Automaton): Problem Statement, Approximate Solutions, Impossibility of A Perfect Classifier, Exact Solution With Alternative Termination Conditions
Famous quotes containing the words majority and/or problem:
“The candidate tells us we are the “backbone of the State,” and we know that it is true, not because we are possessed of certain endowed virtues, but because we are a majority and have the vote.”
—Federal Writers’ Project Of The Wor, U.S. public relief program (1935-1943)
“If we parents accept that problems are an essential part of life’s challenges, rather than reacting to every problem as if something has gone wrong with universe that’s supposed to be perfect, we can demonstrate serenity and confidence in problem solving for our kids....By telling them that we know they have a problem and we know they can solve it, we can pass on a realistic attitude as well as empower our children with self-confidence and a sense of their own worth.”
—Barbara Coloroso (20th century)