[math-fun] In case you hadn't heard, Wolfram has figured out physics.
It turns out General Relativity was a mistake. https://writings.stephenwolfram.com/2020/04/finally-we-may-have-a-path-to-th... —Bill
Erm ... "finally" ? I had imagined it a well-established rule of thumb that the number of GUT proposals under consideration at any one time equals the number of active theoretical physicists (modulo some uncertainty concerning the precise interpretation of both concepts). WFL On 4/26/20, 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
Greg Kuperberg explained to me, when the first publication came out, that the publisher had left out a critical hyphen in the title: A New Kind-of Science -Veit
On Apr 26, 2020, at 12:16 AM, Fred Lunnon <fred.lunnon@gmail.com> wrote:
Erm ... "finally" ? I had imagined it a well-established rule of thumb that the number of GUT proposals under consideration at any one time equals the number of active theoretical physicists (modulo some uncertainty concerning the precise interpretation of both concepts).
WFL
On 4/26/20, 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
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
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-behavior/>, 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-limited-size/> 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
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
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
Rule 90, yes the relation to Pascal’s triangle is great, it’s a personal favorite, see also: https://demonstrations.wolfram.com/Code686BuildsTheChairTiling/ For Rule 30, Wolfram’s questions are much more difficult. I gave up before I could even start. Maybe if I get more time later... —Brad
On Apr 26, 2020, at 4:02 PM, Cris Moore via math-fun <math-fun@mailman.xmission.com> wrote:
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
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Brad, Thanks for answering (on April 26) my questions about the period length of rule 30, etc. I've just created sequences A334496, A334497, and A334501-A334515 as a result of your reply. If we start with a single ON cell, with any of the 256 rules, in a cyclic universe of width n, many of the resulting sequences are uninteresting, many others are duplicates, many more were already in the OEIS, which left A33449 and A334501-A334515. They all just have the 10 terms that you calculated, so all 16 of them need more terms, in case anyone would like to extend them. Best regards Neil Neil J. A. Sloane, President, OEIS Foundation. 11 South Adelaide Avenue, Highland Park, NJ 08904, USA. Also Visiting Scientist, Math. Dept., Rutgers University, Piscataway, NJ. Phone: 732 828 6098; home page: http://NeilSloane.com Email: njasloane@gmail.com On Sun, Apr 26, 2020 at 4:52 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
I double checked, and made a few more conjectures on case splitting: 1. Periodic cases: a(c1*(n+1)+c2)=a(c1*n+c2)+c3(c2) {190, 41, 9, 107, 25} -> {A334501, A334509, A334511, A33514, A33513} 2. For large n, a(n)=3 {62, 131} -> {A334502, A334503} 3. Sequence should be viewed as table with rows a(2^n),a(2^n+1),...,a(2^(n+1)-1) {26, 169, 161, 45, 105} -> {A334504, A334505, A334506, A334508, A334512} Also, 73->A334510, but the pattern is not as easy to see. The most interesting case was anomalous 122 -> A334507. It is halfway periodic, only on the even terms: In[]= a[122, 2 #] & /@ Range[1, 20] In[]=a[122, 2 # + 1] & /@ Range[1, 20] Out[]= {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2} Out[]= {1, 2, 1, 6, 4, 14, 1, 14, 12, 62, 8, 126, 28, 30, 1, 30, 28, 1022, 24, 126} Highly likely that the second sequence is http://oeis.org/A268754. Comparing with APG's mma def. Jan. 13 2009, definition via C.A. seems the more simple. This looks interesting, but I don't know the convention of A268754, so could not check rigorously just yet. Maybe it is easy though. Adam, is there an isomorphism here? --Brad On Tue, May 5, 2020 at 3:56 PM Neil Sloane <njasloane@gmail.com> wrote:
Brad, Thanks for answering (on April 26) my questions about the period length of rule 30, etc.
I've just created sequences A334496, A334497, and A334501-A334515 as a result of your reply.
a[rule_, n_] := -Subtract @@ Flatten[Map[Position[#, #[[-1]]] &, NestWhileList[CellularAutomaton[rule], Prepend[Table[0, {n - 1}], 1], Unequal, All], {0}]] In[]= a[18, #] & /@ Range[32] Out[]= {1, 1, 1, 1, 2, 2, 1, 1, 6, 6, 4, 4, 14, 14, 1, 1, 14, 14, 12, 12, 62, 62, 8, 8, 126, 126, 28, 28, 30, 30, 1, 1} This one is also missing from OEIS, but I think it is just double A268754. Also, r18 = B1/S on a "wire" of height one? I think so, despite my confusion about the code, but for def. see: https://arxiv.org/pdf/0911.2890.pdf The sequence A268754 itself has "binary resonance", so falls under item 3 of my previous list. --Brad On Wed, May 6, 2020 at 12:45 PM Brad Klee <bradklee@gmail.com> wrote:
I double checked, and made a few more conjectures on case splitting:
1. Periodic cases: a(c1*(n+1)+c2)=a(c1*n+c2)+c3(c2) {190, 41, 9, 107, 25} -> {A334501, A334509, A334511, A33514, A33513}
2. For large n, a(n)=3 {62, 131} -> {A334502, A334503}
3. Sequence should be viewed as table with rows a(2^n),a(2^n+1),...,a(2^(n+1)-1) {26, 169, 161, 45, 105} -> {A334504, A334505, A334506, A334508, A334512} Also, 73->A334510, but the pattern is not as easy to see.
The most interesting case was anomalous 122 -> A334507. It is halfway periodic, only on the even terms:
In[]= a[122, 2 #] & /@ Range[1, 20] In[]=a[122, 2 # + 1] & /@ Range[1, 20]
Out[]= {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2} Out[]= {1, 2, 1, 6, 4, 14, 1, 14, 12, 62, 8, 126, 28, 30, 1, 30, 28, 1022, 24, 126}
Highly likely that the second sequence is http://oeis.org/A268754. Comparing with APG's mma def. Jan. 13 2009, definition via C.A. seems the more simple. This looks interesting, but I don't know the convention of A268754, so could not check rigorously just yet.
Maybe it is easy though. Adam, is there an isomorphism here?
--Brad
On Tue, May 5, 2020 at 3:56 PM Neil Sloane <njasloane@gmail.com> wrote:
Brad, Thanks for answering (on April 26) my questions about the period length of rule 30, etc.
I've just created sequences A334496, A334497, and A334501-A334515 as a result of your reply.
Brad, [Apologies for the delay in responding; I forgot about this until today, when I worked through Bill Gosper's exercise ("find a short, branchless MMIX computation that computes the inverse of any given 8x8 matrix X of 0s and 1s, modulo 2, if det X is odd") from TAOCP and therefore ended up being reminded of exponents of the general linear group GL_n(F_2).] The idea behind my Mathematica code is to compute the period much more efficiently (in terms of asymptotic complexity) than explicitly running the cellular automaton and using a cycle detection algorithm. Specifically, we know that the order must divide the exponent of the general linear group GL_n(F_2) because the rule is a linear function on the vector space (F_2)^n. So we just need to do the following: 1. Let k := exponent of GL_n(F_2) (see http://oeis.org/A211171) 2. For each prime factor p dividing k, check whether the oscillator repeats with a period of k/p. (We can simulate k/p steps in time polynomial in log(k/p) by repeated squaring of the matrix which describes the linear map.) 3. If some prime exists, set k to be k/p and jump back to step 2. 4. Otherwise, k is the period of the oscillator. The only non-polynomial-time step here is the prime factorisation, but we already know the prime factors of the exponents of GL_n(F_2) when n <= 1206 (see https://oeis.org/A046800) so it's practical to compute the first 1206 terms of A211171. -------- I'm thinking of writing a program to solve problems of the form 'given a matrix A over F_2 and vectors {u, v}, find the smallest positive integer n (if such an n exists) satisfying A^n u == v'. I think it's reducible to discrete logarithm in a power-of-2 finite field, which can be done relatively efficiently: http://www.dtc.umn.edu/~odlyzko/doc/arch/discrete.logs.pdf In particular, it would allow one to efficiently find a solution to the 'no explicit example has been made' at the end of this webpage: https://www.ics.uci.edu/~eppstein/ca/replicators/b368s12578.html Of perhaps greater practical interest is the fact that it solves the problem: 'given a PRNG which uses a known linear feedback shift register, and given its initial state and current output, compute the number of steps for which it has been run'. Best wishes, Adam P. Goucher
Sent: Wednesday, May 06, 2020 at 6:45 PM From: "Brad Klee" <bradklee@gmail.com> To: "math-fun" <math-fun@mailman.xmission.com> Subject: [math-fun] Missing C.A. Period Analyses.
I double checked, and made a few more conjectures on case splitting:
1. Periodic cases: a(c1*(n+1)+c2)=a(c1*n+c2)+c3(c2) {190, 41, 9, 107, 25} -> {A334501, A334509, A334511, A33514, A33513}
2. For large n, a(n)=3 {62, 131} -> {A334502, A334503}
3. Sequence should be viewed as table with rows a(2^n),a(2^n+1),...,a(2^(n+1)-1) {26, 169, 161, 45, 105} -> {A334504, A334505, A334506, A334508, A334512} Also, 73->A334510, but the pattern is not as easy to see.
The most interesting case was anomalous 122 -> A334507. It is halfway periodic, only on the even terms:
In[]= a[122, 2 #] & /@ Range[1, 20] In[]=a[122, 2 # + 1] & /@ Range[1, 20]
Out[]= {2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2} Out[]= {1, 2, 1, 6, 4, 14, 1, 14, 12, 62, 8, 126, 28, 30, 1, 30, 28, 1022, 24, 126}
Highly likely that the second sequence is http://oeis.org/A268754. Comparing with APG's mma def. Jan. 13 2009, definition via C.A. seems the more simple. This looks interesting, but I don't know the convention of A268754, so could not check rigorously just yet.
Maybe it is easy though. Adam, is there an isomorphism here?
--Brad
On Tue, May 5, 2020 at 3:56 PM Neil Sloane <njasloane@gmail.com> wrote:
Brad, Thanks for answering (on April 26) my questions about the period length of rule 30, etc.
I've just created sequences A334496, A334497, and A334501-A334515 as a result of your reply.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (7)
-
Adam P. Goucher -
Bill Gosper -
Brad Klee -
Cris Moore -
Fred Lunnon -
Neil Sloane -
Veit Elser