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][1] 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$:

[![enter image description here][2]][2]

I normalized the spectrum by considering $\kappa(N) = \lambda(N)/N$.

[![enter image description here][3]][3]

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:

[![enter image description here][4]][4]

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:

[![enter image description here][5]][5]

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:

[![enter image description here][6]][6]

With transitions (transients). For $N=87$ the limit cycle isn't reached, yet.

[![enter image description here][7]][7]

Approaching limit cycles of length $\lambda = 2\cdot N$. For $N=48,58,64$ the limit cycles aren't reached, yet.

[![enter image description here][8]][8]


  [1]: https://en.wikipedia.org/wiki/Rule_110#Interesting_properties
  [2]: https://i.sstatic.net/Mfjwq.png
  [3]: https://i.sstatic.net/jRw1y.png
  [4]: https://i.sstatic.net/DaDfL.png
  [5]: https://i.sstatic.net/M8vKR.png
  [6]: https://i.sstatic.net/6x1D6.png
  [7]: https://i.sstatic.net/678Lg.png
  [8]: https://i.sstatic.net/gzS7Z.png