Majority Classification

Without random access memory or any central unit to perform counting, cellular automata can compute whether an initial configuration contains a majority of "on" or "off" states. If "on" states are the majority, the cellular automaton will signal this fact by turning all the cells "on." The majority classification task is like having to predict which of two candidates will win an election in your city when all you can see are the political signs on your neighbors' front lawns.

When designing a ruleset for such an automaton, one reasonable first guess for a rule might be: "Each cell should update to the state that is currently a majority in its local neighborhood." However, this "local majority vote" approach doesn't work in practice.

The strategy depicted in figures one and two was evolved by genetic algorithm and is quite clever. Whenever a black region on the left meets a white region on the right, a vertical boundary is created between them. However, when a white region on the left meets a black region on the right, a checkerboard triangle forms, composed of alternating black and white cells. The sides of the growing checkerboard region travel at the same velocity. If one side collides with a vertical boundary before the other, that side had a shorter distance to travel. That is, that region is smaller than the region bordered by the other side. At the collision point, the side disappears, and the black region is allowed to grow. When the final point disappears, the lattice will display only the color of the initial majority.

Jim Crutchfield, who had earlier invented a technique for detecting "information processing structures" in dynamical systems, suggested that boundaries between simple regions are carriers of information and information is processed when these boundaries collide. Using space-time diagrams to trace the boundaries results in something akin to a trace of elementary particles in a bubble chamber.

Summarized from Complexity: A Guided Tour by Melanie Mitchell