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.

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: