Universal pattern generation by cellular automata

: Jarkko Kari

: Waleed W Smari

: 2013

: International Conference on High Performance Computing & Simulation, HPCS 2013

: 302

: 303

: 2

: 978-1-4799-0836-3

DOI: https://doi.org/10.1109/HPCSim.2013.6641430

: http://dx.doi.org/10.1109/HPCSim.2013.6641430

Cellular automata are mathematical models for massively parallel processing of information by a large number of identical, locally interconnected tiny processors on a regular grid. Extremely simple processors, or cells, are known to be able to generate together complex patterns. In this talk we consider the problem of designing a cellular automaton that can generate all patterns of states from a finite initial seed. We describe a one-dimensional solution that is based on multiplying numbers by a suitable constant. The automaton to multiply by constant 3/2 is shown to be related to some difficult open questions in number theory. We discuss these connections and pose several questions concerning pattern generation in cellular automata.