7
$\begingroup$

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

  • 0
    These column densities appear to be 5/8, 19/32, and 17/32.2012-10-28

2 Answers 2

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.

  • 0
    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.2012-01-21
0

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 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.

  • 0
    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$.2012-01-21