Understanding a non-trivial cellular automaton by finding its simplest underlying communication protocol

Goles, E.; Little, C; Rapaport, I

Keywords: dynamics, systems, recognition, protocols, automata, communication, pattern, internet, optimality, cellular


In the present work we find a non-trivial communication protocol describing the dynamics of an elementary CA, and we prove that there are no simpler descriptions (protocols) for such CA. This is, to our knowledge, the first time such a result is obtained in the study of CAs. More precisely, we divide the cells of Rule 218 into two groups and we describe (and therefore understand) its global dynamics by finding a protocol taking place between these two parts. We assume that x? ?{0,1} n is given to Alice while y? ?{0,1} n is given to Bob. Let us call z(x,y)? ?{0,1} the result of the dynamical interaction between the cells. We exhibit a protocol where Alice, instead of the n bits of x, sends 2?log(n)?+1 bits to Bob allowing him to compute z(x,y). Roughly, she sends 2 particular positions of her string x. By proving that any one-round protocol computing z(x,y) must exchange at least 2?log(n)? - 5 bits, the optimality of our construction (up to a constant) is concluded. © 2008 Springer Berlin Heidelberg.

Más información

Título de la Revista: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volumen: 5369
Editorial: Society of Laparoendoscopic Surgeons
Fecha de publicación: 2008
Página de inicio: 592
Página final: 604
URL: http://www.scopus.com/inward/record.url?eid=2-s2.0-58549106415&partnerID=q2rCbXpz