On 1-dimensional cellular automata
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)