A2 Vertaisarvioitu katsausartikkeli tieteellisessä lehdessä
Decidability and undecidability in cellular automata
Tekijät: Kari J
Kustantaja: TAYLOR & FRANCIS LTD
Julkaisuvuosi: 2012
Journal: International Journal of General Systems
Tietokannassa oleva lehden nimi: INTERNATIONAL JOURNAL OF GENERAL SYSTEMS
Lehden akronyymi: INT J GEN SYST
Numero sarjassa: 6
Vuosikerta: 41
Numero: 6
Aloitussivu: 539
Lopetussivu: 554
Sivujen määrä: 16
ISSN: 0308-1079
DOI: https://doi.org/10.1080/03081079.2012.695895
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali