<p>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 <a href="http://en.wikipedia.org/wiki/Majority_problem_%28cellular_automaton%29" rel="nofollow">http://en.wikipedia.org/wiki/Majority_problem_(cellular_automaton)</a></p>

CC BY-SA 2.5
2010-12-01T19:40:09.193Z
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)?
user2471
CC BY-SA 2.5
2010-12-01T20:09:49.520Z
@user2471 The paper you are looking for is located here http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=1551&option_lang=eng. But it is in russian.
Oleksandr Bondarenko
CC BY-SA 2.5
2010-12-01T20:59:50.247Z
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 :)
user2471
CC BY-SA 2.5
2010-12-01T17:04:16.720Z
2010-12-01T17:20:29.063Z
2010-12-01T17:20:29.063Z
David Eppstein
<p>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).</p>

CC BY-SA 2.5
2010-12-01T16:56:26.857Z
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.
Noam
CC BY-SA 2.5
2010-12-01T17:03:43.320Z
a rule that involves a finite number of cells at a finite distance
user2471
<cellular-automata>
On 1-dimensional cellular automata
user2471
# On 1-dimensional cellular automata

(Asked by: username_0 on 2010-12-01)

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

**Tags:** cellular-automata
> **Comments:**
> **username_1**: 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.  
> **username_0**: a rule that involves a finite number of cells at a finite distance  

---

## 1 answers

### Answer by username_2 on 2010-12-01. Score: 14 | Accepted answer

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)](http://en.wikipedia.org/wiki/Majority_problem_%28cellular_automaton%29)

> **Comments:**
> **username_0**: 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)?  
> **username_3**: @user2471 The paper you are looking for is located here http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=ppi&paperid=1551&option_lang=eng. But it is in russian.  
> **username_0**: 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 :)  

---

