Decidability and undecidability in cellular automata

: Kari J

Publisher: TAYLOR & FRANCIS LTD

: 2012

: International Journal of General Systems

: INTERNATIONAL JOURNAL OF GENERAL SYSTEMS

: INT J GEN SYST

: 6

: 41

: 6

: 539

: 554

: 16

: 0308-1079

DOI: https://doi.org/10.1080/03081079.2012.695895

We survey results on decidability questions concerning cellular automata. Properties discussed include reversibility and surjectivity and their variants, time-symmetry and conservation laws, nilpotency and other properties of the limit set and the trace, properties chaoticity related such as sensitivity to initial conditions and mixing of the space, and dynamics from finite initial configurations. We also discuss briefly the tiling problem and its variants, and consider the influence of the dimension of the space on the decidability status of the questions.