Nonlinearity in Large-Cycle Cellular Automata

The class of maximal-length cellular automata (CAs) has gained significant attention over the last few years due to the fact that it can generate cycles with the longest possible lengths. For every l of the form l = 2ⁿ-1 where n ∈ ℕ, a cycle of length l can be generated by a cellular automaton (CA) of size ⌊log₂ l⌋ + 1; this maximal-length CA is in fact the optimal (minimum-sized) CA to generate a cycle of length l. However, maximal-length CAs are, in general, linear and have some drawbacks. Moreover, it is nontrivial to address this problem for any l ∈ ℕ, that is, removing the constraint that l is of the form 2ⁿ-1. In this paper we therefore employ nonlinearity in the rules and aim to generate the near-optimal CA for any given cycle length l, meaning that the generated CAs will be of size n = (⌊log2 l⌋ + 1) + d, where the displacement d is as small as possible. We use a generic operator to concatenate a collection of component CAs of sizes n1, n2, …, n_k by employing an evolutionary strategy. Here, n = n₁ + n₂ + ⋯ + n_k and l ≥ lcm(ℓ₁, ℓ₂, …, ℓ_k ), where ℓi (1 ≤ i ≤ k) is the maximum cycle length of a CA of size n_i . An influencing factor in the design of component CAs is to achieve the near-optimal CA for a given cycle length. Here we consider nonlinear reversible large-cycle CAs as component CAs. We also measure the effectiveness of nonlinearity in large-cycle generation.