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:
“There is but little virtue in the action of masses of men. When the majority shall at length vote for the abolition of slavery, it will be because they are indifferent to slavery, or because there is but little slavery left to be abolished by their vote. They will then be the only slaves. Only his vote can hasten the abolition of slavery who asserts his own freedom by his vote.”
—Henry David Thoreau (1817–1862)
“And just as there are no words for the surface, that is,
No words to say what it really is, that it is not
Superficial but a visible core, then there is
No way out of the problem of pathos vs. experience.”
—John Ashbery (b. 1927)