Problem Statement
Given a configuration of a two-state cellular automata with i + j cells total, i of which are in the zero state and j of which are in the one state, a correct solution to the voting problem must eventually set all cells to zero if i > j and must eventually set all cells to one if i < j. The desired eventual state is unspecified if i = j.
The problem can also be generalized to testing whether the proportion of zeros and ones is above or below some threshold other than 50%. In this generalization, one is also given a threshold ; a correct solution to the voting problem must eventually set all cells to zero if and must eventually set all cells to one if . The desired eventual state is unspecified if .
Read more about this topic: Majority Problem (cellular Automaton)
Famous quotes containing the words problem and/or statement:
“The problem of culture is seldom grasped correctly. The goal of a culture is not the greatest possible happiness of a people, nor is it the unhindered development of all their talents; instead, culture shows itself in the correct proportion of these developments. Its aim points beyond earthly happiness: the production of great works is the aim of culture.”
—Friedrich Nietzsche (1844–1900)
“Most personal correspondence of today consists of letters the first half of which are given over to an indexed statement of why the writer hasn’t written before, followed by one paragraph of small talk, with the remainder devoted to reasons why it is imperative that the letter be brought to a close.”
—Robert Benchley (1889–1945)