I actually really like the algorithmic question about rule 30: is there a way to compute the state t steps in the future which is noticeably faster than simulating it (which takes t^2 steps to fill in the light-cone)? This is interesting both for general initial conditions and for the initial condition consisting of a single 1 surrounded by 0s. For some other rules, like 90 and 150, there is a much more efficient algorithm that takes advantage of their algebraic structure (in particular that they are “additive”, or linear mod 2, so we can use the mod-2 Pascal’s triangle or things like it). On the other hand, for a rule like 110 that is computationally universal, there is almost certainly not a significant speedup over direct simulation. My guess is that rule 30 is in a nice middle ground: that there is no fast algorithm to predict it, but that it is not computationally universal either. (Some years ago I tried to convince Wolfram that this middle ground could exist, i.e. that this is not a binary distiction between “computationally universal” and “simple”.) - Cris
On Apr 26, 2020, at 2:59 PM, Brad Klee <bradklee@gmail.com> wrote:
Bill mentioned this last year Oct. 1 in a thread "The Rule 30 Prizes are Launched!"
I did the following search of OEIS:
https://oeis.org/search?q=rule+period+cellular+automaton&sort=&language=engl... "
and found: https://oeis.org/A180001, probably the closest entry to what you are looking for. The code can be generalized to Rule 30 by adding one variable:
a[rule_, n_] := -Subtract @@ Flatten[Map[ Position[#, #[[-1]]] &, NestWhileList[CellularAutomaton[rule], Prepend[Table[0, {n - 1}], 1], Unequal, All], {0}]]
In[36]:= a[30, #] & /@ Range[10] Out[36]= {1, 1, 1, 8, 5, 1, 4, 40, 72, 15}
This sequence does not appear to be in OEIS.
It is also possible to map over all 255 rules: In[40]:= Outer[a[#1, #2] &, Range[0, 255], Range[10]] Out[40]= https://0x0.st/ijnD.txt
To get the true max period, you need to search over initial conditions:
a[rule_, init_] := -Subtract @@ Flatten[Map[ Position[#, #[[-1]]] &, NestWhileList[CellularAutomaton[rule], init, Unequal, All], {0}]] tri[n_] := a[30, #] & /@ Tuples[{0, 1}, n];
In[61]:= tri /@ Range[7] Max /@ %
Out[61]= {{1, 1}, {1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1, 1}, {1, 8, 8, 8, 8, 1, 8, 8, 8, 8, 1, 8, 8, 8, 8, 1}, {1, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 1}, {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, {1, 4, 4, 63, 4, 63, 63, 4, 4, 4, 63, 63, 63, 63, 4, 63, 4, 4, 4, 4, 63, 63, 63, 63, 63, 4, 63, 63, 4, 63, 63, 4, 4, 63, 4, 63, 4, 63, 4, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 4, 63, 63, 63, 63, 4, 4, 63, 63, 4, 63, 63, 4, 4, 4, 63, 63, 4, 4, 63, 63, 63, 4, 4, 63, 63, 4, 63, 63, 4, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 4, 63, 4, 63, 4, 63, 4, 63, 63, 4, 63, 63, 4, 63, 63, 63, 63, 63, 4, 4, 4, 4, 63, 63, 4, 63, 63, 4, 4, 63, 4, 63, 4, 4, 4, 4, 1}}
Out[62]= {1, 1, 1, 8, 5, 1, 63}
It looks like n=7 is the first time that the max period disagrees with the period of the usual one-ON initial condition. Too easy.
--Brad
On Sun, Apr 26, 2020 at 1:04 PM Neil Sloane <njasloane@gmail.com> wrote:
Bill Gosper's link led me eventually to Stephen Wolfram's web age about the "Rule 30" prizes. https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes/
In that page there is a section that begins like this:
"Here’s something else, that may be confusing, or may be helpful. The Rule 30 Prize Problems all concern rule 30 running in an infinite array of cells. But what if one considers just *n* cells < https://www.wolframscience.com/nks/p255--systems-of-limited-size-and-class-2...
, say with the periodic boundary conditions (i.e. taking the right neighbor of the rightmost cell to be the leftmost cell, and vice versa)? There are 2^ *n* possible total states of the system—and one can draw a state transition diagram < https://www.wolframscience.com/nks/notes-6-7--state-networks-for-systems-of-...
that shows which state evolves to which other. Here’s the diagram for *n* = 5: ..."
Me: So take a cylinder of perimeter n, say Z/nZ X N, turn some cells ON in the top ring, and run Rule 30. What is the max period? Is this in the OEIS?
On Sun, Apr 26, 2020 at 9:36 AM Brad Klee <bradklee@gmail.com> wrote:
I tried to ctrl-f for "virial theorem", but didn't find anything. --Brad
On Sat, Apr 25, 2020 at 9:20 PM Bill Gosper <billgosper@gmail.com> wrote:
It turns out General Relativity was a mistake.
https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-th...
—Bill _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun