B3 Article in conference proceedings
Universal pattern generation by cellular automata

List of Authors: Jarkko Kari
Publication year: 2013
Book title *: International Conference on High Performance Computing & Simulation, HPCS 2013
Number of pages: 2
ISBN: 978-1-4799-0836-3

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.

Internal Authors/Editors

Last updated on 2019-21-08 at 23:05