6
$\begingroup$

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

$\endgroup$
3
  • $\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, 2010 at 16:56
  • $\begingroup$ a rule that involves a finite number of cells at a finite distance $\endgroup$
    – user2471
    Dec 1, 2010 at 17:03
  • $\begingroup$ i think this paper can helps you mendeley.com/research/… $\endgroup$
    – user7222
    Jan 23, 2012 at 11:41

1 Answer 1

14
$\begingroup$

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)

$\endgroup$
3
  • $\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, 2010 at 19:40
  • 2
    $\begingroup$ @user2471 The paper you are looking for is located here mathnet.ru/php/…. But it is in russian. $\endgroup$ Dec 1, 2010 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, 2010 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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