Upper limit for oscillator period with N cells in envelope box

[wirehead]

First: it's the letter S, not five. More generalized. I should probably exclude rules with one state though.

Oops. Sorry, reading on a small laptop screen, and not looking close enough. I did wonder why it was 5 in particular...

So, here is the revised question: For an arbitrary rectangular box patch in a plane, dimensions MxN, can there be a constructed rule using the range-1 Moore neighborhood with S states, and a pattern in that rule that fits in the box, that oscillates with a period of S^(M*N) ?

I'm very inclined to guess that the answer is "no", on the grounds that basically you're building a base-S counter with M*N digits, and any reasonable way to do that will require carry operations that affect neighboring digits farther away than range 1.

I didn't want to rule out some clever way of implementing some improbable 2D equivalent of a superpermutation -- but see below...

Probably more leaning towards not on a torus.

Quite possibly we can dispose of the not-a-torus case easily:

- If the MxN oscillator has to have S^(MxN) states, then one of the states is the all-cells-OFF state. Let's call that PHASE0.
- The state following all-OFF MxN has to be some state other than all-OFF MxN. Let's call that phase of the oscillator PHASE1.
- However, a non-toroidal infinite universe has an unbounded number of all-OFF MxN boxes.
- CA rules are deterministic, so all of the all-OFF MxN boxes that overlap with the target box must also go to the same PHASE1.
- The only way that that is possible is if all cells in PHASE1 are the same state.
- Therefore we're going to run into trouble as soon as we've cycled through every all-state-k MxN boxes, for all k in S.

I think the same argument applies on a torus, actually. The "what happens after PHASE0" question has the same exact problem when you consider shifted rectangular areas on the torus.

That puts an extremely low lower bound on the question: we can achieve a period-S oscillator! How much higher we can push the lower bound... is a much more interesting question.

Considering that the answer does't look like a "basic question", I'll move it out of the "basic questions" thread. Also going to change S to K to prevent further confusion.

So here are the constraints:

1. Moore neighborhood, range-1, standard square grid.
2. Unbounded universe outside of the box.
3. Box is a MxN rectangle.
4. Rule has K states, but the behavior can be anything.
5. The pattern can be anything, but it cannot escape the box during the entire period.

Task:

• Find the maximum period of an arbitrary pattern in an arbitrary rule following the above constraints.

EDIT: Results so far: K = 2: 1x1 = 1 (proven by reasoning) 1x2 = 1 (proven by reasoning) 1x3 = 2 (proven by reasoning) 1xN = 2 (proven by reasoning) 2x2 = 2 (proven by reasoning) 3x3 = 72 (proven by exhaustive search) 4x2 = 44 (proven by exhaustive search) 3x4 = 248 (best so far) 4x4 = 512 (best so far) K = 3: 2x2 = 14 (proven by exhaustive search) K = 4: 5x4 = 14 (best so far) 7x12 = 16480 (best so far)

H. H. P. M. P. Cole's results spreadsheet

[Chris857]

Couple thoughts:

• How meaningful is K=1? Seems we at least have a trivial case of K=M=N=1, which would be static with period 1, so period = 1 = 1^(1*1) = K^(M*N)
• This post has some high period oscillators, but aren't nearly high enough period to answer the question.

[wirehead]

• How meaningful is K=1? Seems we at least have a trivial case of K=M=N=1, which would be static with period 1, so period = 1 = 1^(1*1) = K^(M*N)

I ruled out any case where M=1, N=1, in particular, because they're trivial -- though I completely expect that any future formula, when given 1, 1, and K as inputs, will produce K as output. You could do that using the rule B012345678/S/GK

What I am really looking for is how close can we push the limit to K^(M*N) and prove that we've pushed it as far as possible. The p113725632 oscillator there is in a 2-state rule and a 3x199 box, but the period is nowhere near 2^597 (518689446110124119814050982961395143876555779030304612499457166211331601426613518299963381118387974286024735826412598647799393884426471913485859354264245460882647725425188690460672).

[Haycat2009]

Definitely 2^(MN)

[wirehead]

Definitely 2^(MN)

Um, no. It's not that simple, considering that I specified any number of states, not just 2. dvgrn posted a good argument above as to why K^(MN) is not possible for any number of reasons that I encourage you to read.

[Haycat2009]

Definitely 2^(MN)

Um, no. It's not that simple, considering that I specified any number of states, not just 2. dvgrn posted a good argument above as to why K^(MN) is not possible for any number of reasons that I encourage you to read.

My bad, I was thinking of anisotropic rules.

[EvinZL]

My bad, I was thinking of anisotropic rules.

The question allows anisotropic rules, but anisotropic rules can't achieve S^(MN) except with 1 state or in a 1 by 1 grid. The dvgrn-argument shows for any rule, isotropic or not, you can only get max(S,S^(MN)-S)

[dvgrn]

The question allows anisotropic rules, but anisotropic rules can't achieve S^(MN) except with 1 state or in a 1 by 1 grid. The dvgrn-argument shows for any rule, isotropic or not, you can only get max(S,S^(MN)-S)

... Which is not much of a reduction in the upper bound, but at least it's something!

That was just the first thing I thought of, though. Seems like there must be some much subtler arguments that can knock down the upper bound a lot farther.

[Entity Valkyrie 2]

The question allows anisotropic rules, but anisotropic rules can't achieve S^(MN) except with 1 state or in a 1 by 1 grid. The dvgrn-argument shows for any rule, isotropic or not, you can only get max(S,S^(MN)-S)

... Which is not much of a reduction in the upper bound, but at least it's something!

That was just the first thing I thought of, though. Seems like there must be some much subtler arguments that can knock down the upper bound a lot farther.

For a 2-state rule, there are only really 10 configurations in a 2x2 box
(Assume red is on, blue is off, black is outside 2x2 box)

Code: Select all

x = 29, y = 2, rule = LifeHistory
DB.DD.DB.DB.BD.DD.DD.BD.DB.DD$
BB.BB.DB.BD.DB.DB.BD.DD.DD.DD!

since a non-location-dependent CA wouldn't be able to tell the difference between these pairs/quadruplets

Code: Select all

x = 0, y = 0, rule = LifeHistory
DD.BB$
BB.DD3$
DB.BD$
DB.BD3$
DB.BD.BB.BB$
BB.BB.BD.DB!

[Disaster16439]

The question allows anisotropic rules, but anisotropic rules can't achieve S^(MN) except with 1 state or in a 1 by 1 grid. The dvgrn-argument shows for any rule, isotropic or not, you can only get max(S,S^(MN)-S)

... Which is not much of a reduction in the upper bound, but at least it's something!

That was just the first thing I thought of, though. Seems like there must be some much subtler arguments that can knock down the upper bound a lot farther.

For a 2-state rule, there are only really 10 configurations in a 2x2 box
(Assume red is on, blue is off, black is outside 2x2 box)

Code: Select all

x = 29, y = 2, rule = LifeHistory
DB.DD.DB.DB.BD.DD.DD.BD.DB.DD$
BB.BB.DB.BD.DB.DB.BD.DD.DD.DD!

since a non-location-dependent CA wouldn't be able to tell the difference between these pairs/quadruplets

Code: Select all

x = 0, y = 0, rule = LifeHistory
DD.BB$
BB.DD3$
DB.BD$
DB.BD3$
DB.BD.BB.BB$
BB.BB.BD.DB!

In a 2x2 2 state int, the max is 2. The dot needs b1e or c to expand, and then it will keep expanding no matter what. Same goes for domino. Blocks have d8_4 and nothing else on this list has it. Ok, now we are left with these:

Code: Select all

x = 17, y = 2, rule = LifeHistory
DB.BD.2D.2D.BD.DB$BD.DB.DB.BD.2D.2D!

Now let us consider the preblocks. They have D2_x in 2 different symmetry directions, so we can remove two of the preblocks. The duoplets have d4_x symmetry, while the preblocks only have d2_x. Hghhhbh7*dc**6th7'lo. So, the duoplets can never change into preblocks. So the maximum is p2. Here is a rule with both patterns:

Code: Select all

x = 12, y = 2, rule = B2e3a/S2a
o9bo$2o9bo!

I'll try 3x2 later.

[Entity Valkyrie 2]

In a 2x2 2 state int, the max is 2. The dot needs b1e or c to expand, and then it will keep expanding no matter what. Same goes for domino. Blocks have d8_4 and nothing else on this list has it. Ok, now we are left with these:

Code: Select all

x = 17, y = 2, rule = LifeHistory
DB.BD.2D.2D.BD.DB$BD.DB.DB.BD.2D.2D!

Now let us consider the preblocks. They have D2_x in 2 different symmetry directions, so we can remove two of the preblocks. The duoplets have d4_x symmetry, while the preblocks only have d2_x. Hghhhbh7*dc**6th7'lo. So, the duoplets can never change into preblocks. So the maximum is p2. Here is a rule with both patterns:

Code: Select all

x = 12, y = 2, rule = B2e3a/S2a
o9bo$2o9bo!

I'll try 3x2 later.

By the way, here are two 2x2 p4 oscillators:

Code: Select all

x = 2, y = 2, rule = B01236a/S56e
bobbboo$
obbbbob!

However, the rule contains B0, so it might not qualify.

Also:

The question allows anisotropic rules

[EvinZL]

New bound: S^(MN)-S^(MN-N)-S^(MN-M)+S^(MN-M-N+1)

This is based on edge configurations. Without loss of generality, at some generation, a cell on the left edge of the bounding box is on, and in some generation, a cell on the right edge of the bounding box is on. If there is no transition allowing the bounding box to expand left, then there is an ON cell at the left edge in all generations. If there is, then the left edge of the bounding box in any generation is restricted because it cannot expand outside the box. I think the optimal number of possible configurations is when there is no expand right transition or expand left transition, giving the above number.

[dvgrn]

Without loss of generality, at some generation, a cell on the left edge of the bounding box is on, and in some generation, a cell on the right edge of the bounding box is on. If there is no transition allowing the bounding box to expand left, then there is an ON cell at the left edge in all generations.

Can you explain the logical leap between these two sentences? It doesn't seem to follow. Wouldn't there often be a transition that allows the bounding box to expand left when there are two or three adjacent cells in the left column, in some configuration? All we know is that the left boundary will never contain that configuration.

[H. H. P. M. P. Cole]

Every 10 posts I do something big.

Here's a 3x3 p72 found with EPE I would love to call 'Panconfigurational' though it is far from that:

Code: Select all

x = 3, y = 3, rule = B2ei3er4aijny5inqr/S012ak3ajnr4i5ijn6a
3o2$2bo!

I'm pretty sure there's no more higher periods. Here's all the 3x3 configurations up to rotation, reflection, and translation if you are interested. It's a good thing I keep such RLEs.

Code: Select all

x = 181, y = 81, rule = B/S012345678
62bo14bo14bo14bo14bo14bo13bo14bo11bobo$2bo13b2o12bobo12b3o13bo14b2o12b
o14bobo12b2o13b3o12bobo12b3o10bobo11$92bo14bo14bo14bo14bo14bo$b2o13b2o
13b2o13b2o12bobo12b3o74bo14bo$b2o12bobo12b2o13b3o12b3o12b3o12bo14bobo
12b2o13b3o12b2o13b3o12$2bo14bo14bo14bo14bo14bo14bo14bo14bo14bo14bo14b
o$bo14bo14bo14bo14b2o13b2o12bo14bo14bo14bo14bo14bo$o14bobo12b2o13b3o12b
2o13b3o14bo13bo14b2o12bobo12b2o13b3o11$2bo14bo14bo14bo14bo14bo14bo14b
o14bo14bo14bo14bo$obo12bobo12bobo12bobo12bobo12bobo12bobo12b2o13b2o13b
2o13b2o13b2o$2bo13bo14b2o12bo14bobo12b2o13b3o14bo13bo14b2o12bobo12b2o
11$2bo14bo14bo14bo14bo14bo14bo14bo13bo14bo14bo14bo$2o13b3o12b3o12b3o12b
3o12b3o12b3o12b3o12bobo12bobo12bobo12bobo$3o14bo13bo14b2o12bo14bobo12b
2o13b3o13bo14b2o12bobo12b3o11$bo14bo14bo14bo14b2o13b2o13b2o13b2o13b2o
12bobo12bobo12bobo$3o12b3o12b3o12b3o12bo14bo14b2o13b3o12b3o44bo$bo14b
2o12bobo12b3o12bobo12b3o12b3o12b2o13b3o12bobo12b3o12b3o11$b2o13b2o13b
2o12bobo12b3o12b3o12bobo12bobo12bobo12b3o12b3o12b3o$obo12bobo12b2o14b
o14bo13b2o13bobo12bobo12b3o12b3o12bobo12b3o$2o13b3o12bobo12bobo12bobo
12bobo12bobo12b3o12bobo12bobo12b3o12b3o!

Here's the same RLE but with patterns which have no symmetry:

Code: Select all

x = 168, y = 68, rule = B/S012345678
107bo14bo14bo$105bobo12b2o13b3o11$122bo14bo$16b2o28b2o$15bobo27b3o72b
2o13b3o12$32bo14bo74bo14bo29bo$31bo14bo73bo14bo29bo$30b2o13b3o73b2o12b
obo27b3o11$17bo14bo29bo14bo14bo44bo14bo$15bobo12bobo27bobo12bobo12bob
o42b2o13b2o$16bo14b2o27bobo12b2o13b3o43b2o12bobo11$2bo29bo14bo29bo14b
o14bo$2o28b3o12b3o27b3o12b3o12b3o$3o28bo14b2o27bobo12b2o13b3o11$76b2o
13b2o$75bo14b2o$75b3o12b3o!

If there is really a p72 with minpop 4, the max period osc with minpop 5 is p68. Hence the oscs should have either minpop 4 or minpop 3.

i checked with EnumPattEvo and with minperiod 73,
- 2o$2bo! has no results
- 2o2$2bo! has no results
- obo$2bo! has no results
- 3o$2bo! has no results
- 2o$obo! has no results
- 3o2$2bo! has no results
- 2o$bo$2bo! has no results
- 2bo$o$b2o! has no results
- 2bo$o$obo! has no results
and finally, 2bo$obo$bo! has no results.

Hence, p72 is the highest period possible. Yay!

Sidenote: in a square, the maximum number is 4*(number of asymmetric configs), but in a rectangle the maximum number is 2*(number of asymmetric configs + number of C2 configs + number of D2 configs).

Hence, using the methodologies above, I got 10 for 2x3:

Code: Select all

x = 3, y = 2, rule = B2e3jn4ar/S012ak3a
2bo$obo!

It cycles through all the asymmetric configurations twice. There are 12 such oscillators. Perhaps this would be more fitting for the title of 'Panconfigurational'?

Hence, here are the maximum periods for each bounding box so far:
- 1x1, 1
- 1x2, 1
- 1x3, 2
- 1xn, 2
- 2x2, 2
- 2x3, 10
- 3x3, 72

The greatest period for nx1 boxes where n>=3 is 2 as they become 1d elementary cellular automata with range 1. The only ECA bearing oscs is B2/S01. The oscs are all p2s due to the fact that a cell being born is a 'two-sided affair'. Hence the only permissible periods are p1 and p2.

Please let me know if I missed anything out. Also, here's a status table:

(currently deprecated)

It is free to edit so that you can put your new and/or improved results in it.

EDIT: Adding B4z to the original Panconfigurational rule results in this rule where there is a 3x3 oscillator for EVERY static subgroup of (group-theoretical) D4 (there is a 4-cell P2 representing C1, but Panconfigurational is here to show that the rule indeed supports the Panconfigurational):

Code: Select all

x = 19, y = 23, rule = B2ei3er4aijnyz5inqr/S012ak3ajnr4i5ijn6a
9bo$8bobo$9bo5$2o14b3o$obo$b2o13b3o4$bo6b2o7bo$2bo13bobo$o8b2o5bobo5$
8b3o2$10bo!

[Entity Valkyrie 2]

Hence, p72 is the highest period possible. Yay!

Is a higher period possible with B0?

[H. H. P. M. P. Cole]

Hence, p72 is the highest period possible. Yay!

Is a higher period possible with B0?

AFAIK no. I'm only testing non-B0 rules.

[wirehead]

Every 10 posts I do something big.

Here's a 3x3 p72 found with EPE I would love to call 'Panconfigurational' though it is far from that:

Code: Select all

x = 3, y = 3, rule = B2ei3er4aijny5inqr/S012ak3ajnr4i5ijn6a
3o2$2bo!

...

Hence, p72 is the highest period possible. Yay!

Wow... I was not expecting progress this much so fast.

So for M, N = 3, 3, and K=2, the function outputs 72.

The actual formula for the function is still unknown...

[LaundryPizza03]

Every 10 posts I do something big.

Here's a 3x3 p72 found with EPE I would love to call 'Panconfigurational' though it is far from that:

Code: Select all

x = 3, y = 3, rule = B2ei3er4aijny5inqr/S012ak3ajnr4i5ijn6a
3o2$2bo!

I'm pretty sure there's no more higher periods. Here's all the 3x3 configurations up to rotation, reflection, and translation if you are interested. It's a good thing I keep such RLEs.

Code: Select all

x = 19, y = 23, rule = B2ei3er4aijnyz5inqr/S012ak3ajnr4i5ijn6a
9bo$8bobo$9bo5$2o14b3o$obo$b2o13b3o4$bo6b2o7bo$2bo13bobo$o8b2o5bobo5$
8b3o2$10bo!

I uploaded to Google Drive a collection of all oscillators and spaceships where each phase is no larger than 3x3. Download as a ZIP file.

The unique speeds and periods that occur are: p1, p2, p3, p4, p5, p6, p7, p8, p9, p10, p11, p12, p13, p14, p15, p16, p17, p18, p20, p22, p24, p26, p28, p30, p32, p34, p36, p38, p40, p44, p48, p52, p56, p60, p64, p68, p72, c/1o, 2c/2o, c/2o, c/3o, 4c/4o, 2c/4o, c/4o, 2c/5o, c/5o, 3c/6o, 2c/6o, c/6o, 3c/7o, 2c/7o, c/7o, 4c/8o, 2c/8o, c/8o, c/9o, 2c/10o, 4c/12o, 2c/12o, 2c/14o, 4c/16o, c/3d, c/4d, c/5d, c/6d, c/7d, 2c/8d, c/8d, c/9d, 2c/10d, c/10d, c/11d, 3c/12d, 2c/12d, c/12d, 2c/14d, c/14d, 2c/16d, c/16d, (2,1)c/6, (2,1)c/7.

[AforAmpere]

Is the goal to find them such that the initial bounding box never moves, or that the pattern never gets larger than an MxN box? EPE allows the bounding box to slide around, so a normal search will find all examples of the former, but would be annoying to search through. Instead, PRUNE can be set like:

Code: Select all

#define PRUNE (next.tx+next.nx>MAXX||next.ty+next.ny>MAXY||next.tx<0||next.ty<0)

Also, it's funny, I did the 3x3 search and found that p72 a few years ago as one of the initial tests of EPE, but I only ever posted the results on Discord. It's neat to see it come back around.

Here's a lower bound on 3x4 at p208:

Code: Select all

x = 3, y = 4, rule = B2eik3anqr4iqt5aeiny6-in7/S01e2a3-cqry4ijwz5eik6k7
o$bo2$2bo!

[b3s23love]

In 4x4 I found this p284:

Code: Select all

x = 3, y = 2, rule = B2ce3ajqy4-cejqt5-eikn6-in78/S01e2cin3cijkn4aejkrwy5ainqy6k7e8
obo$2bo!

Not sure if a higher-period example is known or if there already exists a table for this (outside from Cole's one).

[H. H. P. M. P. Cole]

Same methodologies as before, confirmed highest period 4x2 osc, p44!

Code: Select all

x = 4, y = 2, rule = B2ek3ejr4ai/S012ai3aeijr4a
3bo$obo!

EDIT: Thanks, LaundryPizza for the comprehensive analysis of all 3x3 patterns that stay 3x3!

[carsoncheng]

In 4x4 I found this p284:

Code: Select all

x = 3, y = 2, rule = B2ce3ajqy4-cejqt5-eikn6-in78/S01e2cin3cijkn4aejkrwy5ainqy6k7e8
obo$2bo!

Not sure if a higher-period example is known or if there already exists a table for this (outside from Cole's one).

Looks like a higher-period example is fairly easy to find; here is a p420:

Code: Select all

x = 4, y = 4, rule = B2ek3ajnq4-ektyz5eijry6-e7e/S02ik3ajkry4-cejkn5-acnr6e
bo2$o$3bo!

EDIT: p436:

Code: Select all

x = 4, y = 4, rule = B2ek3ajnq4aijqrw5eijr6-en8/S02ik3ajkry4airtwz5acijq6acn7e
bo2$o$3bo!

EDIT 2: p456:

Code: Select all

x = 4, y = 4, rule = B2ek3ajnq4aiqrw5-cjnq6-n7e/S02ik3ajr4-cekny5-cery6ce7
bo2$o$3bo!

[b3s23love]

Here's a lower bound on 3x4 at p208:

Code: Select all

x = 3, y = 4, rule = B2eik3anqr4iqt5aeiny6-in7/S01e2a3-cqry4ijwz5eik6k7
o$bo2$2bo!

p212:

Code: Select all

x = 3, y = 4, rule = B2ekn3ac4jkqr5aeiqr6ekn7e/S012ac3aik4-cekq5e6kn7c
2bo$2bo2$o!

EDIT 1:
p248:

Code: Select all

x = 3, y = 4, rule = B2ek3acjy4cjkrz5-ceky6-ae8/S012acn3aiq4-cknqy5eky6-en
o$2bo2$2bo!

[carsoncheng]

p512 in 4x4:

Code: Select all

x = 4, y = 4, rule = B2ek3ajnq4aijkr5-cjnq6cei7e/S02eik3ajry4aqrtwy5acijn6akn8
bo2$o$3bo!

EDIT: p532:

Code: Select all

x = 4, y = 4, rule = B2ek3ajnq4acijqrt5-cq6-an7c/S02eik3ajkry4airz5ackn6-en7e
bo2$o$3bo!

[Plasmath]

The 2-state 1xN cases are pretty simple but haven't had a rigorous proof yet, so I'll show that their maximum period is 2 (other than 1x2 and 1x1, their periods are 1):
Because we are currently disregarding B0 rules and any B1e-like birth transition will result in an explosive rule, we are left with the following possible birth and survival transitions:
Birth: 2i
Survival: 0, 1e (left), 1e (right), 2i
We need to have the leftmost and rightmost active cell active at all times because we don't have a B1e transition for the oscillator to grow to the bounding box again, so we need to have both of the S1e transitions. We are left with 4 rules:

• B2i/S1e: This has only one stable object - the duoplet.
• B2i/S01e: This rule has one family of period-2 oscillators with minimum bounding box 1x3.

  Code: Select all

  x = 15, y = 19, rule = B2i/S01e
  obo3$ob3o3$ob3obo3$ob3ob3o3$ob3ob3obo3$ob3ob3ob3o3$ob3ob3ob3obo!

• B2i/S1e2i: Only still lives in this rule.
• B2i/S01e2i: No death possible, so only still lives.

Thus, in 1x1 and 1x2 only still lives (trivially period-1 oscillators) exist, and in 1x3 and onward the maximum oscillator period is 2.