I investigated the evolution of a single black cell on 1-dimensional grids with periodic boundary conditions of variable sizes $N$ under Wolfram's rule 110 which is the only one for which Turing completeness has been directly proven.
I especially determined by brut force calculation the length $\lambda_{110}(N) = \lambda(N)$ of the limit cycle the single black cell evolves to. Plotting logarithmically the limit cycle lengths for rule 110 and $N = 6\dots 250$ looks like this, the longest limit cycle having length $\lambda = 419,064 = 228 \cdot 2 \cdot 919 $ for $N=228$:
I normalized the spectrum by considering $\kappa(N) = \lambda(N)/N$.
This spectrum with its intricate structure is unique among all elementary cellular automata. Furthermore rule 110 is one of only a few non-trivial class III and class IV rules for which $\lambda(N)$ could be computed for all $N \leq 250$. (For rule 106 the algorithm didn't return in reasonable time even for $N=29$.) The other rules' spectra look either much more chaotic or boringly simple. I analyzed the spectrum for different properties.
For how many $N$ is $\lambda(N) < N$, i.e. $\kappa(N) < 1$?
Which values $\lambda$ does $\lambda(N) < N$ take?
For how many $N$ is $\kappa(N)$ an integer number, i.e. $\lambda(N) \equiv 0 \text{ mod }N$?
Which $\kappa$ have many $N$ with $\kappa(N) = \kappa$ (seen as progressions in the plots above)?
Which $\kappa$ are unique, i.e. there is only one $N \leq 250$ with $\kappa(N) = \kappa$?
The results of the analysis are summarized here:
On a logarithmic scale in horizontal direction (the $\kappa$ axis) the number of grid sizes $N$ with $\kappa(N) = \kappa$ or $\lambda(N) = \lambda$ (blue) is plotted. There are
- several $N$ with $\lambda(N) = 7$
- one $N$ with $\lambda(N) = 9$
- many $N$ with $\kappa(N) = 2, 10, 15, 30$
- many $N$ with $\kappa(N) = \frac{3}{2}, \frac{15}{4}, \frac{15}{2}$
- many $N$ with unique $\kappa(N)$, most of them for $\kappa > 59$ and many of them prime or semi-prime.
I calculated the cumulated probabilities $P(N) = \frac{|\{ n \leq N\,|\,p(n)\}|}{N}$ for these properties:
Let me make three simple conjectures for Wolfram's rule 110, based on these observations:
There are infinitely many $N$ with $\lambda(N)= 7$.
For almost all $N$ with $\lambda(N) < N$ we find $\lambda(N)= 7$.
There are infinitely many $N$ with $\kappa(N) = 2$.
My question is: How would one try to prove these conjectures?
Some limit cycles of length $7$ for rule 110:
With transitions (transients). For $N=87$ the limit cycle isn't reached, yet.
Approaching limit cycles of length $\lambda = 2\cdot N$. For $N=48,58,64$ the limit cycles aren't reached, yet.
