Decidability and undecidability in cellular automata

Abstract

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.

Keywords:

• cellular automata
• undecidability
• tiling problem

Acknowledgement

This research supported by the Academy of Finland Grant 131558.