Upper limit for oscillator period with N cells in envelope box

[wirehead]

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.

[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)

[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).

[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.

[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.

[wildmyron]

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

[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.

[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.

[galoomba]

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.

[wirehead]

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).

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

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.

[carsoncheng]

p560 in 4x4:

Code: Select all

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

[carsoncheng]

p636 in 4x4:

Code: Select all

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

[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!

[wirehead]

Cross-posting another result by confocaloid:

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.

[confocaloid]

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!

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.

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.

[hotcrystal0]

What is the limit for 3x4?

[Plasmath]

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!