25
$\begingroup$

The cellular automaton Rule 30 is most commonly explored starting with a single 1 cell against a background of infinitely many 0 cells. This gives the familiar plot:

However, if you start with a 1 cell but use a background consisting of the pattern 01, you find that it only expands to fill a portion of its right side:

enter image description here

I noticed something curious about it today; it appears that the ratio of the "structured" part of each row to the preceding alternating cells approaches the Golden Ratio, $1.618\ldots$

Equivalently, if you right-align the structured part of the plot, this is also the ratio of its height to its width (trimming the alternating background), like so:

enter image description here

That said, this is an empirical guess only and it could be coincidental. A plot of the difference between the actual ratio and $\varphi$ through 600k rows is suggestive but hardly conclusive:

enter image description here

I'm inclined to think it really is slowly approaching $\varphi$ primarily because the ruleset and initial conditions seem too straightforward for it to spit out an arbitrary irrational, assuming Rule 30 is well-balanced in the long run as current evidence suggests. Unfortunately, the computation becomes slow work at this point (at least, using my naive approach) so that's as far as I've been able to check.

My question: what possible properties, either specifically or in general, might apply to Rule 30 in this case to explain why this ratio arises?

Alternatively, if someone can either put forth a good argument for why this is probably a meaningless coincidence, or can code a faster approach that resolves the issue one way or another, I'll also consider my question answered.

$\endgroup$
10
  • 2
    $\begingroup$ Equivalently, given that the structured part's right side moves with speed $1$, you conjecture that the left side moves with speed $1/(\varphi+1)\approx0.382$. $\endgroup$
    – mr_e_man
    Commented Jul 21, 2022 at 20:35
  • 1
    $\begingroup$ @JairTaylor Yep, it looks like any random bit string against that alternating background behaves roughly the same way; all of them are in the same ballpark ratio-wise. $\endgroup$
    – Trevor
    Commented Jul 22, 2022 at 0:21
  • 2
    $\begingroup$ In that case, I am thinking modeling this process assuming some randomness could help, as a non-rigorous heuristic. $\endgroup$ Commented Jul 22, 2022 at 0:28
  • 2
    $\begingroup$ If you believe the ratio approaches the Golden Ratio, please upvote this comment. $\endgroup$
    – Apass.Jack
    Commented Aug 4, 2022 at 11:02
  • 7
    $\begingroup$ If you believe the ratio approaches some constant that is not the Golden Ratio, please upvote this comment. $\endgroup$
    – Apass.Jack
    Commented Aug 4, 2022 at 11:04

1 Answer 1

4
$\begingroup$

I have written a multi-threaded C program to compute the ratio for 1M rows (which took some 1h20 on a friend of mine's beefy computer). It can be found here: https://github.com/mell-o-tron/Rule30Variation

The results seem to suggest that the ratio does not converge to $\phi$, but rather to some other constant.

plot

I will add the raw data points to the Github if requested.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .