On time-symmetry in cellular automata
On time-symmetry in cellular automata
复制标题
DOI：
10.1016/j.jcss.2012.01.006
复制
发表时间：
2012-07-01
影响因子：
1.1
通讯作者：
Moreira, Andres
中科院分区：
文献类型：
--
作者：
Gajardo, Anahi;Kari, Jarkko;Moreira, Andres
可逆性的概念在元胞自动机（CA）领域得到了深入的研究，有几个原因。然而，在物理理论中发现的一个相关概念到目前为止一直被忽视，不仅在CA中，而且通常在离散动力系统中。这是时间对称的概念，指的是无法区分向后和向前的时间方向。在这里，我们形式化的CA的上下文中，并研究它的一些基本属性。我们还展示了一些著名的CA适合时间对称CA类，并提供了一些结果之间的关系，这和其他类CA。证明了在可逆CA类中存在一个内在普适的时间对称CA。最后，我们证明了2维或更高维CA的时间对称性的不可判定性，即使在可逆CA类。维度1的情况是结论中讨论的几个未决问题之一。(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.