Majority Problem (cellular Automaton)

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:

    In no other country in the world is the love of property keener or more alert than in the United States, and nowhere else does the majority display less inclination toward doctrines which in any way threaten the way property is owned.
    Alexis de Tocqueville (1805–1859)

    The family environment in which your children are growing up is different from that in which you grew up. The decisions our parents made and the strategies they used were developed in a different context from what we face today, even if the “content” of the problem is the same. It is a mistake to think that our own experience as children and adolescents will give us all we need to help our children. The rules of the game have changed.
    Lawrence Kutner (20th century)