I'm interested in linear 2-state cellular automata (with local rules only) that could compute the majority function. Say the state of a cell is either 0 or 1. Is it possible to have a cellular automaton that sets all cells to 1 if the majority of initial states is 1 and sets all cells to 0 if the majority of initial states is 0? The cellular automaton could be synchronous or asynchronous. I tend to believe that the answer is negative (mainly because of rule locality). Any literature on this problem? I also believe that one could approximate it in the sense that one could devise a cellular automaton that fails only on a small fraction of its inputs (purely experimental at this point).
This is a well known problem. It's known to be impossible to solve exactly, but either approximable in the sense you describe or solvable exactly if you relax the conditions under which it recognizes a majority: see http://en.wikipedia.org/wiki/Majority_problem_(cellular_automaton)