A2 Refereed review article in a scientific journal
Decidability and undecidability in cellular automata
Authors: Kari J
Publisher: TAYLOR & FRANCIS LTD
Publication year: 2012
Journal: International Journal of General Systems
Journal name in source: INTERNATIONAL JOURNAL OF GENERAL SYSTEMS
Journal acronym: INT J GEN SYST
Number in series: 6
Volume: 41
Issue: 6
First page : 539
Last page: 554
Number of pages: 16
ISSN: 0308-1079
DOI: https://doi.org/10.1080/03081079.2012.695895
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.
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.
UTU Research Portal