Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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
add comment

2 Answers 2

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.

share|improve this answer
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
add comment

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.

share|improve this answer
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
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.