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 n - 1 where n∈N, a cycle of length l can be generated by a cellular automaton (CA) of size ⌊ log 2 ⁢ 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∈N, that is, removing the constraint that l is of the form 2 n - 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 = ( ⌊ log 2 ⁢ 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 n 1 , n 2 , … , n k by employing an evolutionary strategy. Here, n = n 1 + n 2 + ⋯ + n k and l ≥ lcm ⁢ ( ℓ 1 , ℓ 2 , … , ℓ 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.