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

Abstract

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.