Topological dynamics of cellular automata: dimension matters (Q537911)

The paper aims at making a difference between one-dimensional and two-dimensional cellular automata. First, a basic difference concerning the topological dynamics classification is presented. Then it is shown that some properties are non-recursive in higher dimension. For dimensions higher than 1 there exists a class \(N\) of cellular automata which are neither in \(E_{\mathrm{qu}}\) (the set of cellular automata with equicontinuous points) nor in \(S_{\mathrm{ens}}\) (the set of sensitive cellular automata). For these classes it is shown that each of them is neither recursively enumerable nor co-recursively enumerable; also any pair of them is recursively inseparable. Finally the authors show that there exist two-dimensional cellular automata having only a countable set of equicontinuous points and the set of sensitive cellular automata raises from \(\Pi_2^0\) in dimension 1 to \(\Sigma_3^0\)-complete in dimension 3.