Universal pattern generation by cellular automata



: Kari J

Publisher: ELSEVIER SCIENCE BV

: 2012

: Theoretical Computer Science

: THEORETICAL COMPUTER SCIENCE

: THEOR COMPUT SCI

: 429

: 180

: 184

: 5

: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2011.12.037


We construct a reversible, one-dimensional cellular automaton that has the property that a finite initial configuration generates all finite patterns over its state alphabet. We also conjecture that a related cellular automaton satisfies the stronger property that every finite pattern gets generated in every position, so that the forward orbit of the finite initial configuration is dense. (C) 2011 Elsevier B.V. All rights reserved.



Last updated on 2024-26-11 at 22:12