A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On time-symmetry in cellular automata
Tekijät: Gajardo A, Kari J, Moreira A
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2012
Journal: Journal of Computer and System Sciences
Tietokannassa oleva lehden nimi: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Lehden akronyymi: J COMPUT SYST SCI
Numero sarjassa: 4
Vuosikerta: 78
Numero: 4
Aloitussivu: 1115
Lopetussivu: 1126
Sivujen määrä: 12
ISSN: 0022-0000
DOI: https://doi.org/10.1016/j.jcss.2012.01.006
Tiivistelmä
The notion of reversibility has been intensively studied in the field of cellular automata (CA), for several reasons. However, a related notion found in physical theories has been so far neglected, not only in CA, but generally in discrete dynamical systems. This is the notion of time-symmetry, which refers to the inability of distinguishing between backward and forward time directions. Here we formalize it in the context of CA, and study some of its basic properties. We also show how some well-known CA fit into the class of time-symmetric CA, and provide a number of results on the relation between this and other classes of CA. The existence of an intrinsically universal time-symmetric CA within the class of reversible CA is proved. Finally, we show the undecidability of time-symmetry for CA of dimension 2 or higher, even within the class of reversible CA. The case of dimension 1 is one of several open questions discussed in the conclusions. (C) 2012 Elsevier Inc. All rights reserved.
The notion of reversibility has been intensively studied in the field of cellular automata (CA), for several reasons. However, a related notion found in physical theories has been so far neglected, not only in CA, but generally in discrete dynamical systems. This is the notion of time-symmetry, which refers to the inability of distinguishing between backward and forward time directions. Here we formalize it in the context of CA, and study some of its basic properties. We also show how some well-known CA fit into the class of time-symmetric CA, and provide a number of results on the relation between this and other classes of CA. The existence of an intrinsically universal time-symmetric CA within the class of reversible CA is proved. Finally, we show the undecidability of time-symmetry for CA of dimension 2 or higher, even within the class of reversible CA. The case of dimension 1 is one of several open questions discussed in the conclusions. (C) 2012 Elsevier Inc. All rights reserved.
Turun yliopiston Tutkimustietojärjestelmän portaali