Density Classification Task

The Density Classification Task is the task in which the constituents of a Finite State Machine simultaneously assume the initial majority state given an initial random distribution of states.

Cellular Automata

One example of where the Density Classification Task can be seen is in a one-dimensional Cellular Automata model. Cells are randomly assigned a value of 0 or 1. If the majority of the cells are initially assigned 1, then the Density Classification Task has been completed when all cells have assumed a value of 1 (after a given number of generations). Inversely, if the majority of cells are initially assigned 0, then the task has been completed when all cells have assumed a value of 0. In a noisy environment (where there is a probability that two cells will miscommunicate, reporting a 1 instead of a 0 or vice versa), a simple majority rule will accomplish the task.

Applications

A Finite State Machine's ability to complete the Density Classification Task can be indicative of the interlinkage between its constituents.