Periodic orbits for additive cellular automata (Q1079017)

The classical d-dimensional cellular automaton (d-CA) is an ordered quadruple \(<Z^ d,A,\tau^{(n)},X>\), where: \(Z^ d\) is a d-dimensional regular array, \(A=\{0,1,...,a-1\}\) is the alphabet of the d-CA, \(\tau^{(n)}\) is the global transition function of the d-CA, X is the neighbourhood index of the d-CA, and n is the number of neighbour finite automata in the d-CA. The state of the entire array \(Z^ d\) is called a configuration (CF) of the d-CA, i.e. a CF is any mapping CF: \(Z^ d\to A\). The operation of the d-CA is specified by a local function \({\mathcal L}^{(n)}(x_ 1,x_ 2,...,x_ n)=x_ 1'\), which produces the next state of the automata which are directly connected to \(x_ 1\). The simultaneous application of a local function to the neighbourhood of every automaton of the array \(Z^ d\) defines a global function \(\tau^{(n)}\) of the current CF c into the next CF \(c\tau\) (n). CF c is called periodical in a d-CA with period k iff \(c\tau^{(n)k}=c\). The spatial period \(\alpha\) (x) of the one-dimensional CF \(x=...x_{i-1}x_ i..\). is the smallest positive natural number p such that \(x_{i+p}=x_ i\) for every \(i\in Z^ 1.\) In this paper binary additive 1-CA are considered. Such 1-CA has the alphabet \(A=\{0,1\}\) and the local function \({\mathcal L}^{(n)}(x_ 1,...,x_ n)=\sum^{n}_{1}x_ i (mod 2)\). The authors formulate and study a necessary and sufficient condition for a CF c to be periodical for any type of binary additive 1-CA. The number of periodical CF with period k is counted. Then the authors prove that periodical CF with period k are generated by a linear map and have necessarily a spatial period \(\alpha\) (k). In the paper relations between periods k and spatial periods \(\alpha\) (k) are also investigated. This problem has a negative solution for more general types of 1-CA. More precisely, in the reviewer's book ''Mathematical theory of homogeneous structures and their applications'' (1980; Zbl 0434.68033) it was proved that the problem of k-periodicity of arbitrary finite CF c in 1-CA is undecidable.