# Density of black cells in rule 110

Is there a way to compute the limit of the ratio (number of black cells)/(number of white cells), in the rule 110 or rule 30 automaton? With initial state = 1 black cell.

Simulation of first 120000 rows shows a quite stable total density of 0.592..., and row-density 0.592...

Here is average density of some consecutive columns of height some thousands: How to explain the apparent periodicity? These are quite clearly converging, how to calculate the exact values? (0.62499..==5/8 ??)

0.6249983636387438, 0.5937438636452892, 0.5312544999934545, 0.5937569545353388, 0.624991818193719, 0.6249983636387438, 0.5937569545353388, 0.5312414091034049, 0.5937438636452892, 0.6250049090837686, 0.6249983636387438, 0.5937504090903141, 0.5312479545484298, 0.5937373182002644, 0.624991818193719, 0.6250049090837686, 0.5937569545353388, 0.5312479545484298, 0.5937438636452892, 0.6250049090837686, 0.6250114545287934, 0.5937504090903141, 0.5312479545484298, 0.5937504090903141, 0.6249983636387438, 0.6250114545287934, 0.5937504090903141, 0.5312414091034049, 0.5937634999803637, 0.6250114545287934, 0.6249983636387438, 0.5937438636452892

-
I assume you're only counting within a finite length of cells. Also, one might consider that the frequency might not even stabilize, and its asymptotic evolution will probably depend on choice of initial state. – anon Jan 20 '12 at 23:40
New find, column density very stable, but differs alot between different columns!! Column density is periodic, with period 5, and takes on 3 different values. – sture Jan 21 '12 at 9:03
These column densities appear to be 5/8, 19/32, and 17/32. – Peter Shor Oct 28 '12 at 3:39

Since rule 110 is Turing universal, there are probably families of well-defined starting conditions such that each of them has one of two limiting densities, but where it is undecidable whether a given starting states has one fate or the other.

One needs to apply some ingenuity in order to define a concept of "limiting density" for this to work though. One possibility would be to restrict our attention (for the purpose of measuring density) to a narrow downwards-pointing cone, look at the limiting density inside the cone (which may or may not exist), and then let the width of the cone go towards 0. I think it would be possible for this kind of limiting density to depend on whether the cyclic tag system in the universality proof grows without bounds or not.

-
IIRC, the universality of rule 110 is at least partly a matter of semantics - the universality construction requires at the very least infinitely many initially-on cells in the starting configuration, and I'm not even sure if the initial state is asymptotically periodic (although I believe it is). That said, the periodic background configuration for the construction has density 4/7 for each timestep. – Steven Stadnicki Jan 21 '12 at 5:26
It's true that the question is sensitive to how one defines the eventual density -- especially since the world has to be infinite anyway for the question to be nontrivial. I've updated the answer with some thoughts about this. -- As far as I understand Wikipedia's account of the universality proof, the initial configuration consists of two strictly periodic half-lines separated by a finite central section. – Henning Makholm Jan 21 '12 at 5:52

A heuristic calculation:

If every cell is black (independently from each other) with probability $p$ then in the next row we have $$p'=3p^2(1-p)+2p(1-p)=p\big(3p(1-p)+2(1-p) \big)$$ Starting from $0<p<1$ and iterating this we get the fixed point at $p=\frac{\sqrt{5}-1}{2}$.

This might or might not be correct depending on how pseudorandom the actual patterns are.

-
You should really do the calculation to the second level. Assume the original state is composed of 00,01,10,11, with probabilities $p_1$, $p_2$, $p_3$, $p_4$. Now, find fixed points of the $p_i$. – Peter Shor Jan 21 '12 at 18:27