ConwayLife.com • Upper limit for oscillator period with N cells in envelope box - Page 2

Page 2 of 3

Re: Upper limit for oscillator period in MxN box

Posted: October 2nd, 2023, 4:40 pm

by wirehead

AforAmpere wrote: October 1st, 2023, 2:30 pm 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?

The goal is to find oscillators that have a maximal MxN bounding box, in an arbitrary rule with K states (where K can be anything, not just 2!!)

And while I do know the "canonical" form for an oscillator is the one with the minimum population or bounding box, you could just trivially say "this is the oscillator", with the oscillator in its largest phase (maximum bounding box, and then hooray, it never escapes its "initial" bounding box.

------

Best bliptile (K=4) result so far:

5x4 = 14

Code: Select all

x = 5, y = 4, rule = Bliptile
CB2AC$AC2AB$A2.BA$3ACA!

7x12 = 16480

Code: Select all

x = 12, y = 7, rule = Bliptile
5AC2A.ABA$C4AB3AB2A$BC.CBABAB2AC$5AB3ABAB$5AC2AB3A$C5ACB3AB$B6AC2ABA!

------

I updated the OP with results so far.

Re: Upper limit for oscillator period in MxN box

Posted: October 2nd, 2023, 6:14 pm

by H. H. P. M. P. Cole

Another day, another case!

I have done the 2x2 3-state case. Here's the RLE (yet another Panconfigurational):

Code: Select all

x = 2, y = 2, rule = P14
B$.A!
@RULE P14
@TABLE
n_states:3
neighborhood:Moore
symmetries:rotate4reflect
1,0,0,0,0,0,0,0,2,1
0,0,0,0,0,1,0,2,0,2
2,0,0,0,1,0,0,0,0,0
0,0,0,2,1,2,0,0,0,2
1,2,2,2,0,0,0,0,0,2
2,2,1,2,0,0,0,0,0,1
2,2,2,1,0,0,0,0,0,1
1,1,2,1,0,0,0,0,0,0
2,1,0,1,0,0,0,0,0,1
1,1,1,0,0,0,0,0,0,2
1,1,0,1,0,0,0,0,0,2
0,2,2,2,0,0,0,0,0,1
2,2,2,0,0,0,0,0,0,0

Here's a RLE of all 2x2 3-state configs, sorted by cell count and symmetry:

Code: Select all

x = 97, y = 45, rule = B/S012345678History
9$47.2B4.2A4.2C10.2B3.AC$47.2B4.2A4.2C10.AC3.AC3$2B$2B$50.2B4.2B$50.B
A4.BC10.2B3.2B$68.2A3.2C2$2B4.2B$BA4.BC5$2B4.2B4.2B32.BA3.AC3.BC12.BA
4.BC$2A4.AC4.2C32.AB3.CA3.CB12.2C4.2A5$BA4.BC4.BC$AB4.AB4.CB3$44.BA4.
BC4.BC4.2A4.AC4.BA4.BC$44.AC4.AB4.CA4.AC4.2C4.2A4.2C$BA4.BA4.BA4.BC4.
BA4.BC$2A4.AC4.2C4.2A4.AC4.2C5$2A4.2A4.2A4.AC4.AC4.2C$2A4.AC4.2C4.CA4.
2C4.2C!

There are 7 configs with D2\ symmetry but there are 2 configs with C1 symmetry.

Since 7x2 = 14 > 4x2 = 8, I made a p14 with all the configurations with D2\ symmetry.

There are obviously many more, but I chose the most obvious route. Here are its phases:

Code: Select all

x = 37, y = 2, rule = B/S012345678History
CB3.BC3.2C3.2A3.BA3.BA3.BC3.AB$BA3.CA3.CA3.AC3.AC3.2A3.2C3.BC!

Hence we have proved, for 3 states:
- 1x1, p2 (A! -> B! -> A!)
- 1x2, p2 (BA! -> AB! -> BA!)
- 2x2, p14 (shown here)

Re: Upper limit for oscillator period in MxN box

Posted: October 2nd, 2023, 9:37 pm

by Plasmath

Here's a lower bound for a k-state 1xN oscillator, using a base-(k-3) counter:
(This is a base-3 example, but it should make sense how to generalize it to any base)

Code: Select all

x = 10, y = 19, rule = osc1xn
E2$2E2$3E2$4E2$5E2$6E2$7E2$8E2$9E2$10E!

@RULE osc1xn

@TABLE

n_states:6
neighborhood:vonNeumann
symmetries:none

var N = {0,1,2,3,4,5}

5,0,N,0,0,1
1,0,N,0,0,2
2,0,N,0,0,3

5,0,N,0,3,1
1,0,N,0,3,2
2,0,N,0,3,3

3,0,0,0,N,4
3,0,1,0,N,4
3,0,4,0,N,4
3,0,5,0,N,4

4,0,N,0,5,5
4,0,N,0,0,5
4,0,N,0,1,5
4,0,N,0,2,5
4,0,N,0,3,5

@COLORS
0 48  48  48
1 255 255 255
2 255 255 0
3 255 200 0
4 200 100 0
5 100 100 100

The general oscillator period is 2*(k-3)^n - 1 (which I think is pretty close to the perfect k^n)! Can we push the lower bound any further?

Note: It's probably possible to get new lower bounds on general k-state MxN oscillators using LCM combinations of these oscillators within a bounding box, as none of the oscillators are factors of each other.

Note 2: This only works for k > 4 (I haven't checked k = 4, but I have a feeling that this would break as a unary counter).

Re: Upper limit for oscillator period in MxN box

Posted: October 3rd, 2023, 1:24 am

by H. H. P. M. P. Cole

Here's two theorems:

Let F(a,b,c) output the highest period oscillator with c states in an axb bounding box.

THEOREM 1: F(1,1,n) = n-1.

Proof:

Number the states 1 to n-1.

1 -> 2 -> 3 -> ... -> n-1 -> 1

THEOREM 2: F(1,2,n) = (n-1)(n-2).

Proof' by explicit example:

(1)(2) -> (1)(3) -> (1)(4) -> ... -> (1)(n-1) -> (2)(3) -> (2)(4) -> ... -> (2)(n-1) -> (3)(4) -> ... ... -> (n-2)(n-1) -> (2)(1)

And the sequence repeats, reversed in cell order. Since all configurations above are panconfigurational with respect to symmetry and bounding box, this works for all n > 3.

If this is hard to understand, here's a 4-state p6 example:

Code: Select all

x = 2, y = 1, rule = P6
AB!
@RULE P6
@TABLE
n_states:4
neighborhood:vonNeumann
symmetries:rotate4reflect
1,2,0,0,0,1
2,1,0,0,0,3
1,3,0,0,0,2
3,1,0,0,0,3
3,2,0,0,0,1

BTW, should we have a list of all 2x2 3-state objects which stay 2x2 3-state throughout?

EDIT: I made my table in my first post here editable.

Re: Upper limit for oscillator period in MxN box

Posted: October 3rd, 2023, 9:43 am

by b3s23love

I started a distributed 4x4 search (like Sokwe's c/8 search).
Instructions:
1) Download EnumPattEvo
2) Change the constants to:

Code: Select all

#define PRUNE (next.p>10000||next.tx+next.nx>MAXX||next.ty+next.ny>MAXY||next.tx<0||next.ty<0)
#define SPECIAL_RESULT (1==2)
#define MAXX 4
#define MAXY 4
#define MAXGEN 30000
#define MINGEN {whatever the current record is - 1}

3) Compile EPE
4) Claim an RLE by going to H. H. P. M. P. Cole's spreadsheet, then the "4x4 search" sheet, then scrolling to find the RLE you want to complete.
5) Edit the row to say:
Second column: Claimed
Fourth column: {your username}
6) Run the command

Code: Select all

./epe2 --5s -e -p '{the RLE you claimed}'

Example:

Code: Select all

./epe2 --5s -e -p 'bbbo$obob$obbb$boob'

7) Wait until the command finishes (this may take a few days)

<-- Cool dude.
9) Check if the search yielded a new record (by checking the Patterns: line). If yes, make a post on the forum and edit the fourth column of the claimed line with "Yes"; otherwise, edit it with "No".
Very similar instructions apply if you want to verify someone else's search.

Re: Upper limit for oscillator period in MxN box

Posted: October 3rd, 2023, 10:01 am

by wildmyron

Entity Valkyrie 2 wrote: September 26th, 2023, 11:48 am
dvgrn wrote: September 25th, 2023, 4:45 am
EvinZL wrote: September 24th, 2023, 11:02 pm 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 addition to the restriction imposed above, the dot and two dominos can be excluded from any 2x2 2-state oscillator because any rule which allows them to fill the remainder of the bounding box will also cause at least one of the other configurations to expand outside of the bounding box. This leaves 7 configurations. In the special case of 2x2, every cell has perfect information with the Moore neighbourhood and so a p7 oscillator can be made by cycling through those 7 configurations:

Code: Select all

x = 2, y = 2, rule = MaxPeriod_2x2k2
ob$bo!

@RULE MaxPeriod_2x2k2

Maximum oscillator period in a 2x2 bounding box with 2 states  

@TABLE

n_states:2
neighborhood:Moore
symmetries:none

1000100000
0000010101
1000000010
0101000001

0001010001
1000001001
0100000101
1010000000

1001100000
1000010101
1100000011
0111000001

0001110001
1000011000
1100000101
1011000001

1000110001
0000011101
1000000110
1101000001

1001010001
1000001101
0100000111
1110000001

1001110001
1000011100
1100000111
1111000000

This is less than the recently postulated upper bound of 10, but I'm confident it is the maximum with a static background. The rules in the OP don't seem to explicitly require that, and with B0 an oscillator with period > 7 might be possible. However, the current status seems to only consider INT rules - I'm not sure if that's accidental or due to a change in direction for this thread. (It might be interesting to track both, especially considering that the tools for exploring anisotropic rule-spaces are considerably less well developed)

The technique applied here won't be usable for bounding boxes larger than 2x2 so the maximum period attainable will likely be less than the number of configurations which fill the bounding box. Also, I think dvgrn had a reasonable point that in some cases patterns which expand are allowed, so long as the transition which causes expansion doesn't happen at the boundary. However, it seems unlikely to me that an oscillator exhibiting this behaviour could be a maximal period oscillator for any given (M,N,K).

[Edit] The technique can be applied to 2x2 oscillators in rules with K states. In those cases the maximum period will be the number of 2x2 configurations which fill the bounding box. I derived the rule above by hand but clearly a script can and should be used to generate such rules for K >= 3

Re: Upper limit for oscillator period in MxN box

Posted: October 3rd, 2023, 10:28 am

by Cyclotrons

For a moment, lets consider a more general version of the question: Can a pattern fully localized to an MxN bounding box go through all permutations of that bounding box at all (not required to oscillate)?

The answer is no.

Take the case where there is a single live cell in the bounding box, with the rest being state 0. If the above conjecture were true, a configuration with the single cell at (M,N) for each M and N would have to occur in a sequence.

Lets rule out the unbounded universe case first: Any rule where a single cell was able to change neighboring state 0 cells on its lonesome would break out of the bounding box for at least M or N possible positions.

Now for the torus case:
Let P be a pattern that permutes through all permutations of an MxN torus.
Let C0 be a pattern where all cells are state 0.
Let X be the set of distinct patterns where a single state 1 cell is in a unique position in the torus, with all other cells being state 0.

All rules obey translational symmetry: all patterns behave the same regardless of absolute position.
Therefore, if 1 pattern in X evolves into another pattern in X, all other patterns in X will evolve into another pattern in X.

Per dvgrn's post, C0 cannot evolve into any pattern in X.
Conversely, no pattern in X can evolve into C0 if it evolves into another pattern in X.
P must have C0 and all patterns in X as phases.
Therefore, P cannot exist.

Come to think of it, the same argument should apply to patterns besides a single live cell too, at least for the torus case, which should allow you to construct an upper bound for a pattern's lifespan in an MxN torus.

-

Note that none of this applies if you use a bounded grid or allow cells outside of the box in an unbounded universe.

Re: Upper limit for oscillator period in MxN box

Posted: October 3rd, 2023, 7:08 pm

by H. H. P. M. P. Cole

Everyone, another theorem is coming in the Land of Isotropic Multistate Automata!

F(a,b,c) (notation used in my previous posts) is now deemed UNCOMPUTABLE. However, some values are computable, particularly F(1,1,n), F(1,2,n), and F(2,2,n). In these one transition encodes one complete phase of the oscillator. Hence Panconfigurationals exist for every symmetry in 2x2 boxes.

I have calculated F(1,1,n) and F(1,2,n) in my previous posts already, so no introduction is required. Also, for n >= 4, the number of configs with C1 symmetry is greater than the number of configs with D2\ symmetry.

Hence, here is a derivation of the formula for the max period of a 2x2 oscillator when the number of states is greater than or equal to 4.

Type 1

Code: Select all

0 a
b b

There are (n-1)(n-2) such configurations.

Type 2

Code: Select all

0 a
b c

There are (n-1)(n-2)(n-3)/2 such configurations.

Type 3

Code: Select all

a b
c c

There are (n-1)(n-2)(n-3)/2 such configurations.

Type 4

Code: Select all

a b
c d

There are (n-1)(n-2)(n-3)(n-4)/8 such configurations.

Summing them up and multiplying by 4 gives:

1/2 (n - 2) (n - 1) (n^2 + n - 4)

Since there are more configurations with a higher symmetry in 1, 2, and 3 states, this formula is invalid.

Hence F(2,2,n) has the values:

1, 2, 14, 48, 156, 380, 780, 1428...

EDIT: Please post your completed results or partial results (like carsoncheng's 4x4 p532 and carsoncheng's 6x2 p134) here as well for purposes of collation. Please put the relevant RLEs and ruletables in my spreadsheet, again for collation purposes.

EDIT2: As a response to Galoomba, in 2x3 boxes and higher, one transition does not encode the entire oscillator's phase. Hence such transition is expected to behave the same in all instances of it, making the max period slightly smaller. Hence this is why it is deemed uncomputable - there is no quick formula for it.

Re: Upper limit for oscillator period in MxN box

Posted: October 3rd, 2023, 7:15 pm

by galoomba

H. H. P. M. P. Cole wrote: October 3rd, 2023, 7:08 pm F(a,b,c) (notation used in my previous posts) is now deemed UNCOMPUTABLE.

I don't think so. There are finitely many rules with a fixed number of states and patterns with a fixed bounding box.

Re: Upper limit for oscillator period in MxN box

Posted: October 3rd, 2023, 7:38 pm

by wirehead

galoomba wrote: October 3rd, 2023, 7:15 pm
H. H. P. M. P. Cole wrote: October 3rd, 2023, 7:08 pm F(a,b,c) (notation used in my previous posts) is now deemed UNCOMPUTABLE.
I don't think so. There are finitely many rules with a fixed number of states and patterns with a fixed bounding box.

It is definitely computable. The only way might be brute force, but there is a finite number of transitions in the rule space (c^9) and we already know that the upper bound on the period is c^(a*b). So any brute force algorithm will have a definite answer for F(a, b, c) in O(c^(a*b) * c^9) time. Hopefully we can reduce that!

And anyway the goal is not to find particular cases for the function F, but the function F itself (i.e. the formula, but even a picewise function would be acceptable).

Re: Upper limit for oscillator period in MxN box

Posted: October 3rd, 2023, 7:52 pm

by H. H. P. M. P. Cole

wirehead wrote: October 3rd, 2023, 7:38 pm
galoomba wrote: October 3rd, 2023, 7:15 pm
H. H. P. M. P. Cole wrote: October 3rd, 2023, 7:08 pm F(a,b,c) (notation used in my previous posts) is now deemed UNCOMPUTABLE.
I don't think so. There are finitely many rules with a fixed number of states and patterns with a fixed bounding box.
It is definitely computable. The only way might be brute force, but there is a finite number of transitions in the rule space (c^9) and we already know that the upper bound on the period is c^(a*b). So any brute force algorithm will have a definite answer for F(a, b, c) in O(c^(a*b) * c^9) time. Hopefully we can reduce that!

And anyway the goal is not to find particular cases for the function F, but the function F itself (i.e. the formula, but even a picewise function would be acceptable).

I mean 'uncomputable' as in 'uncomputable using a formula'.

EDIT: Cleaned up my status table/spreadsheet.

Re: Upper limit for oscillator period in MxN box

Posted: October 7th, 2023, 7:00 am

by carsoncheng

p560 in 4x4:

Code: Select all

x = 4, y = 4, rule = B2ek3ajnq4ainrz5-enq6-en8/S02eik3ajqry4aiqrty5-qr7e8
bo2$o$3bo!

Re: Upper limit for oscillator period in MxN box

Posted: October 10th, 2023, 6:21 am

by carsoncheng

p636 in 4x4:

Code: Select all

x = 4, y = 4, rule = B2ek3ajnq4aijkqrw5aeijq6-e/S02eik3ajkqr4-ceknt5-akr6eik
bo2$o$3bo!

Re: Upper limit for oscillator period in MxN box

Posted: October 12th, 2023, 4:37 pm

by Plasmath

Here's an 8x8 p27334 found through manual search, which I think is a new lower bound (still not a great one considering the size of the oscillator):

Code: Select all

x = 8, y = 8, rule = B2-ac3-i45ai78/S01234-ir5aci6-c7e8
o2b5o$b3ob2o$2ob4o$b6o$o5bo$o2b3obo$ob2obobo$o2b5o!

Re: Upper limit for oscillator period with N cells in envelope box

Posted: October 16th, 2023, 8:33 pm

by wirehead

Cross-posting another result by confocaloid:

Haycat2009 wrote: October 14th, 2023, 11:04 am
confocaloid wrote: October 13th, 2023, 3:38 am No answer, but here is what it looks like after Edit 2: T = 1, 2, 3, 5, 10, 100 gigaticks:
Code: Select all
snip
It does not appear to settle into any period below 50 x 10^9.
I remember seeing a post on the max period in MxN box. This could challenge it!

If indeed this is an oscillator, it really is gonna be a head-scratcher.

Also since this is obviously a diamond shape, bounding diamond would be a better metric of area. I think I'll just change it it to N cells in the envelope instead of a forced MxN rectangle.

Re: Upper limit for oscillator period with N cells in envelope box

Posted: October 17th, 2023, 5:31 am

by confocaloid

Plasmath wrote: October 12th, 2023, 10:25 pm When does this pattern become periodic? It hasn't stabilized for 770,000,000 generations:
Code: Select all
x = 16, y = 16, rule = B2-a3-ai4inrtwyz5-jky6-cn78/S3k4-jqt5-aer6-ac7
bobo5bob2ob2o$ob2o4bo4b2o$obobobo2bob5o$4bob2o3b5o$2b2o2b5o2b3o$4bobo
bo4b2o$o5bo2bobobo$3o4b2obo4bo$bobo5bobo3bo$3b2ob3obo3b2o$2o2b6o2bo$o
2bobo2bo2bob3o$b4o2b2o2bo$b2o2b3obo2bobo$2o4bo4b5o$3obobo3bo4bo!

wirehead wrote: October 16th, 2023, 8:33 pm Cross-posting another result by confocaloid:

Clarification: There is no actual result. I started from generation 10^11 = 100,000,000,000 of that initial 16x16 soup posted by Plasmath, evolving two copies of the pattern, one copy 1 tick per iteration, another copy 2 ticks per iteration, comparing copies after each iteration. If the pattern settles into an oscillator, this is guaranteed to find a multiple of the period, but I have no idea how long it might take.

Edit: I interrupted the program after 14 x 10^9 iterations without detecting oscillation. Maybe the pattern evolves for really long time before settling to a low period, or maybe it already settled into a really high period. My code is fairly slow; it would be nice to have a fast tool for determining periods of oscillators like these.

wirehead wrote: October 16th, 2023, 8:33 pm Also since this is obviously a diamond shape, bounding diamond would be a better metric of area. I think I'll just change it it to N cells in the envelope instead of a forced MxN rectangle.

I think both would be interesting. Those higher-period square-shaped oscillators are fun to watch.
Another possibility is the MCPS of the set of cells that are alive in at least one phase.

Re: Upper limit for oscillator period with N cells in envelope box

Posted: October 17th, 2023, 3:42 pm

by hotcrystal0

What is the limit for 3x4?

Re: Upper limit for oscillator period in MxN box

Posted: October 17th, 2023, 4:26 pm

by Plasmath

hotcrystal0 wrote: October 17th, 2023, 3:42 pm What is the limit for 3x4?

I believe that the current upper limit is 3392, based on the bounds found in this post. The current lower limit is this p248 oscillator found by b3s23love:

Code: Select all

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

Re: Upper limit for oscillator period with N cells in envelope box

Posted: March 3rd, 2024, 11:48 pm

by H. H. P. M. P. Cole

Time to revive this thread.

N cells in envelope is a particularly good idea.

Here are the first few lower bounds:

Let f(n) be the maximum period of an oscillator with an n-cell envelope.

1 cell: 1 (o!, B/S0) (proven maximum)
2-cell: 1 (2o!, B/S1e) (proven maximum)
3-cell: 2 (obo!, B2i/S01e) (proven maximum)
4-cell: 3 (o$b2o!, B2e3r/S012a3r) (proven maximum: see EDIT)

A naive upper bound (n >= 2) is 2^n-n-1 where n is the number of cells in the envelope. (The bound is just total combinations minus empty set minus subsets with 1 cell). Please let me know if you can find better lower/upper bounds for any number of cells!

Here is a proof that an osc with a 3-cell envelope cannot exceed period 2:

No 2-cell configs that can be affected by B2 have the same symmetry. This can be proven by brute-force. Hence oscillators with maxpop of 2 are impossible (unless they are period-1), therefore there must be at least one phase of pop 3. There must only be one phase with pop 3, namely the envelope itself (you can't have supersets of a universal set). However, as stated before, no 2-cell configs have the same symmetry, so there is a maximum number of one 2-cell config that can have the same symmetry as the envelope. Hence the maximum period is 2. QED.

EDIT: There are only a few minpop 2-cell oscs where the envelope is less than or equal to 4 cells:

- duoplet, B2e/S
- 2c-dots, B2c/S
- 2i-dots, B2i/S01e
- 2k-dots, B2k/S02a
- 2n-dots, B2n/S01c

All of them have period 2. Hence for a hypothetical maximum-period oscillator with a 4-cell envelope, it must not have a minpop of 2. Therefore it must have a minpop of 3, a maxpop of 4, and one phase of population 4, hence the upper bound is reduced to period 5.

Now the problem reduces to 'find the tetraplets with the most number of lowest-symmetry subsets and make them into an oscillator', since in a non-polyplet cluster, isolated cells have to stay at S0 the whole time, with cells in the Moore neighbourhood of the isolated cell not being affected by the other 3 cells in the envelope.

I visually looked at all the tetraplets and there was only one (the L-tetromino) which had a set of 3 or more subsets which could be made into an oscillator, which is the p3 oscillator in the summary above. Hence period 3 is the maximum for a 4-cell envelope. YAY!!!

(also, if someone can update EnumPattEvo2 to include maxpop, minpop, and envelope size settings, this would be very helpful)

EDIT2: Let the envelope be a SL. Then any terminus (outer cell) that has the condition S1c, S1e, or S2a is a stator cell. If not attempts to birth said cell will result in runaway behaviour.

Generalizing the above constraints will lead one to realize that the envelope must be a polyplet, for oscillators in isolated clusters of n cells will oscillate at period f(n) or less.

Re: Upper limit for oscillator period with N cells in envelope box

Posted: March 1st, 2025, 6:41 pm

by EvinZL

This counter gives a lower bound of 5*2^(n-2) for 2-state 2*n bounding box

Code: Select all

x = 16, y = 2, rule = MAPADDs/AMDzMwAMOz8AwPMzADw7PwDA8zMAADsAAMAzAAAAOz8AAAAAAAA7PwAAAAAAADs/P////8AAOwA/wD/AA
o$16o!

Re: Upper limit for oscillator period with N cells in envelope box

Posted: March 1st, 2025, 6:49 pm

by wirehead

EvinZL wrote: March 1st, 2025, 6:41 pm This counter gives a lower bound of 5*2^(n-2) for 2-state 2*n bounding box
Code: Select all
x = 16, y = 2, rule = MAPADDs/AMDzMwAMOz8AwPMzADw7PwDA8zMAADsAAMAzAAAAOz8AAAAAAAA7PwAAAAAAADs/P////8AAOwA/wD/AA
o$16o!

That works for anisotropic rules, but what about isotropic rules? Is there a version of this that works in any orientation?

Re: Upper limit for oscillator period with N cells in envelope box

Posted: October 18th, 2025, 7:01 am

by muzik

What's our limit for 3x5 so far?

Re: Upper limit for oscillator period with N cells in envelope box

Posted: October 19th, 2025, 2:44 am

by muzik

Here's a tiny lower bound, at p8:

Code: Select all

x = 5, y = 3, rule = B3a4n6a/S1e2aei3aer4ir5i6e
o3bo$o2b2o$5o!

Far better can be done.

Re: Upper limit for oscillator period with N cells in envelope box

Posted: October 19th, 2025, 10:21 am

by vilc

muzik wrote: October 19th, 2025, 2:44 am Here's a tiny lower bound, at p8

Slightly better : a p54 (found with LLS).

Code: Select all

x = 3, y = 5, rule = B2ei3eky4acnrty5ceiq6-n7/S1e2-cn3-iq4-enrtz5jkqry6ck78
2bo$2bo$bo$o$3o!

Is there a way to have newer versions of EPE prune for a fixed bounding box ? All I get is oscillators like this p100:

Code: Select all

x = 4, y = 3, rule = B2ckn3aejr4aekqtw5cr6ac/S012kn3aeijq4aijntw5ciq6akn7c8
3bo2$o2bo!

Edit:
p58

Code: Select all

x = 3, y = 5, rule = B2e3ejr4ejknrt5-jq6-cn8/S012-e3ajnq4cinrwyz5-en67e
b2o$b2o$bo$3o$3o!

Edit 2:
p64

Code: Select all

x = 3, y = 5, rule = B2eik3ckn4-aikry5-cekq6cn7e8/S012aci3-ckry4ciknrwz5ijn7
2o$o$2o$2o$b2o!

Edit 3:
I figured out the EPE custom pruning functionnality.
In EPEMain.cpp, change the return statement of custom_prune to :

Code: Select all

return ((arr.disp_x >= 0)&&(arr.disp_y >= 0)&&(arr.dims_x + arr.disp_x <= 5)&&(arr.dims_y + arr.disp_y <= 3));

I found this p254, which is slightly better than the 4x3 record (p248).

Code: Select all

x = 5, y = 3, rule = B2en3aejnr4acijky5aceky6-an7c/S01e2ae3aiqr4cnqrtz5-ek6-i
obo2$4bo!

Edit 4:
p260

Code: Select all

x = 5, y = 3, rule = B2en3aejnr4acijkwy5-ciqr6-en7/S01e2ae3aiqr4cjnqrz5-eky6-in7c
obo2$4bo!

Edit 5:
p346

Code: Select all

x = 5, y = 3, rule = B2en3-ciky4acjkqw5aekny6-i7/S01e2ae3-cejy4cjnrwyz5ciknr6cik7c
obo2$4bo!

Edit 6:
p352

Code: Select all

x = 5, y = 3, rule = B2en3aejnr4acijkz5-iqr6cn7/S01e2ae3aiknr4cjnqrty5-ejq6-a78
obo2$4bo!

Edit 7:
p354

Code: Select all

x = 5, y = 3, rule = B2en3-ciky4cjkqyz5ikny6aik7/S01e2ae3aiknr4cjnrty5cjky6aen7
obo2$4bo!

Re: Upper limit for oscillator period with N cells in envelope box

Posted: October 25th, 2025, 1:48 am

by ThePlayzr

I can't access the spreadsheet of results by H. H. P. M. P. cole, and am not willing to use my email, as that literally has my full name and school in it, so can someone post it in this thread or PM it to me?
Anyway, 1xN with 2 states has been proven to be limited at p2, except 1x1 and 1x2 are 2, but 2x2 has no proof yet. This rule has very high period ones though:

Code: Select all

x = 12, y = 14, rule = B3a4r/S1c2ac3in4i
obo$2obo3$obobo$2obobo3$obobobobo$2obobobobo3$obobobobobo$2obobobobob
o!

It behaves like the edge of a margolus oscillator.
period 1 is the max for 2x1, period 2 is the max for 2x2, period 10 is the limit for 2x3, but the rest doesn't appear to have a known limit. However, this does give p14 for 2x6, p62 for 2x10, p126 for 2x12, and goes on like https://oeis.org/A160657.