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).

  • $\begingroup$ when you say local rules, do you mean just its two immediate neighbors (and itself), or do you also allow distance d? If it is the former then there are only 256 possible rules that can be mechanically checked. $\endgroup$ – Noam Dec 1 '10 at 16:56
  • $\begingroup$ a rule that involves a finite number of cells at a finite distance $\endgroup$ – user2471 Dec 1 '10 at 17:03
  • $\begingroup$ i think this paper can helps you mendeley.com/research/… $\endgroup$ – user7222 Jan 23 '12 at 11:41

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)

  • $\begingroup$ Does anymore have an electronic version of ^ Gács, Péter; Kurdyumov, G. L.; Levin, L. A. (1978). "One dimensional uniform arrays that wash out finite islands". Problemy Peredachi Informatsii 14: 92–98. (found on the wiki page mentioned above)? $\endgroup$ – user2471 Dec 1 '10 at 19:40
  • 2
    $\begingroup$ @user2471 The paper you are looking for is located here mathnet.ru/php/…. But it is in russian. $\endgroup$ – Oleksandr Bondarenko Dec 1 '10 at 20:09
  • $\begingroup$ Thanks a lot Oleksandr! I hope that my basic knowledge of Russian can help here... although, Gacs and Levin papers are usually hard to read even in English :) $\endgroup$ – user2471 Dec 1 '10 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.