HPSSBB (Highest Periods Supporting Specific Bounding Boxes) Project

[unname4798]

This is a project for highest period oscillators in a specific bounding box. Only R1MINTSG (R1 Moore INT on a Square Grid) is supported.
1x1:

Code: Select all

#R B/S0
o!

1x2:

Code: Select all

#R B/S1e
2o!

2x2:

Code: Select all

#R B2e/S
o$bo!

[muzik]

2x2:

Code: Select all

x = 2, y = 2, rule = MAPADC9vyIA/f8AAH//AAD//wCA//+AAP//AID/fwAA//8AAH//AAB//wAA//8AAP//AAD//4AA//8AAP//AAD//w
o$bo!

[unname4798]

2x2:

Code: Select all

x = 2, y = 2, rule = MAPADC9vyIA/f8AAH//AAD//wCA//+AAP//AID/fwAA//8AAH//AAB//wAA//8AAP//AAD//4AA//8AAP//AAD//w
o$bo!

Only INT is supported.

[Aleph]

I'd like to point to some known results. First, we have "glass tile oscillators" collected in a thread by confocaloid. viewtopic.php?f=11&t=6792

confocaloid points out that margolus oscillators are an infinite series of these oscillators. As a result, we have lower bounds for all bounding boxes, since margolus oscillators fit in squares, which fit in rectangles. However, since we aren't required to use the *entire* bounding box, a simple replicator shuttle can grow with the *longer* side length of a rectangle, instead of the shorter one, to which margolus oscillators are constrained.

[unname4798]

I'd like to point to some known results. First, we have "glass tile oscillators" collected in a thread by confocaloid. viewtopic.php?f=11&t=6792

confocaloid points out that margolus oscillators are an infinite series of these oscillators. As a result, we have lower bounds for all bounding boxes, since margolus oscillators fit in squares, which fit in rectangles. However, since we aren't required to use the *entire* bounding box, a simple replicator shuttle can grow with the *longer* side length of a rectangle, instead of the shorter one, to which margolus oscillators are constrained.

No adjustable oscillators!

[Aleph]

No adjustable oscillators!

These adjustable oscillators are only intended to be lower bounds. I heavily doubt that most of them are optimal, but I just want something to fill up the table for now. But if you insist:

1x3 >= P2

Code: Select all

x = 3, y = 1, rule = B2i/S01
obo!

From confocaloid's thread, we know that:
15x3 >= P104
12x3 >= P12
9x8 >= P46
7x6 >= P32
6x6 >= P30
6x4 >= P10
6x3 >= P6
4x4 >= P8
EDIT: Oops
Edit 2: Oops again
Edit 3: A sheet, I guess
https://docs.google.com/spreadsheets/d/ ... id=0#gid=0
Edit 4: I dug up a P50 in 9x9 by Ampere: https://catagolue.hatsya.com/object/xp5 ... n4ij5ay6ci
The same review also led me to a 3x2n binary counter oscillator that they found; once again, it only makes for a lower bound on period.

Code: Select all

x = 3, y = 14, rule = B2e3jry4t5i7e/S012aci3ijr4aci5ey7e
3o$bo$bo$bo$bo$bo$bo$bo$bo$bo$bo$bo$bo$bo!

I believe that a length-(2n>=4) oscillator has a period of 6.25*2^n+2n-13, but I am currently lacking a proof or disproof. I also made a ruletable for the 4-state rule emulating this, in hopes that it can shine in some metaphorical light.

Code: Select all

x = 1, y = 14, rule = Ampere_counter
C$A$A$A$A$A$A$A$A$A$A$A$A$A!
@RULE Ampere_counter
A 4-state 1D CA emulating the binary counter oscillators in B2e3jry4t5i7e/S012aci3ijr4aci5ey7e of the form o$(2n)o$o! for n>=2.
@TABLE
n_states:4
neighborhood:Moore
symmetries:none
#00x->0
0, 0, 0,1,0, 0,0,0,0, 1#010->1
0, 0, 0,1,1, 0,0,0,0, 1#011->1
0, 0, 1,1,0, 0,0,0,0, 1
0, 0, 0,1,2, 0,0,0,0, 3#012->3
0, 0, 2,1,0, 0,0,0,0, 3
0, 0, 0,1,3, 0,0,0,0, 1#013->1
0, 0, 3,1,0, 0,0,0,0, 1
0, 0, 0,2,0, 0,0,0,0, 2#020->2
0, 0, 0,2,1, 0,0,0,0, 2#021->2
0, 0, 1,2,0, 0,0,0,0, 2
0, 0, 0,2,2, 0,0,0,0, 2#022->2
0, 0, 2,2,0, 0,0,0,0, 2
0, 0, 0,2,3, 0,0,0,0, 3#023->3
0, 0, 3,2,0, 0,0,0,0, 3
0, 0, 0,3,0, 0,0,0,0, 3#030->3
0, 0, 0,3,1, 0,0,0,0, 2#031->2
0, 0, 1,3,0, 0,0,0,0, 2
0, 0, 0,3,2, 0,0,0,0, 1#032->1
0, 0, 2,3,0, 0,0,0,0, 1
#033->0
0, 0, 1,0,1, 0,0,0,0, 0#101->0
0, 0, 1,0,2, 0,0,0,0, 1#102->1
0, 0, 2,0,1, 0,0,0,0, 1
0, 0, 1,0,3, 0,0,0,0, 1#103->1
0, 0, 3,0,1, 0,0,0,0, 1
0, 0, 1,1,1, 0,0,0,0, 1#111->1
0, 0, 1,1,2, 0,0,0,0, 2#112->2
0, 0, 2,1,1, 0,0,0,0, 2
#113->0
0, 0, 1,2,1, 0,0,0,0, 2#121->2
#122->0
#123->0
0, 0, 1,3,1, 0,0,0,0, 2#131->2
0, 0, 1,3,2, 0,0,0,0, 3#132->3
0, 0, 2,3,1, 0,0,0,0, 3
0, 0, 1,3,3, 0,0,0,0, 2#133->2
0, 0, 3,3,1, 0,0,0,0, 2
#202->0
0, 0, 2,0,3, 0,0,0,0, 2#203->2
0, 0, 3,0,2, 0,0,0,0, 2
0, 0, 2,1,2, 0,0,0,0, 1#212->1
0, 0, 2,1,3, 0,0,0,0, 1#213->1
0, 0, 3,1,2, 0,0,0,0, 1
0, 0, 2,2,2, 0,0,0,0, 2#222->2
0, 0, 2,2,3, 0,0,0,0, 3#223->3
0, 0, 3,2,2, 0,0,0,0, 3
#232->0
0, 0, 2,3,3, 0,0,0,0, 1#233->1
0, 0, 3,3,2, 0,0,0,0, 1
#333->0
@COLORS
0   0   0   0
1   85  85  85
2   170 170 170
3   255 255 255

[vilc]

Here are some results concerning thin bounding boxes, obtained with EPE. This method doesn't work prectically for width 4 or higher since the bounding box constraint is not static in EPE, leading to many false-positives. It should be possible to do an exhaustive search this way for small cases, by trying every possible starting pattern in the given rectangle.

2x2 : p2 is maximal.
3x2 : p10

Code: Select all

x = 3, y = 2, rule = B2e3n4ar/S012a3an4r
o$b2o!

4x2 : p44

Code: Select all

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

5x2 : p64

Code: Select all

x = 5, y = 2, rule = B2ik3ar4ar/S012aci3ajn4ir5i
o2bo$obobo!

6x2 : p106

Code: Select all

x = 6, y = 2, rule = B2ek3aenr4r5i/S012ei3aijn4r5i
bo$o2bobo!

7x2 : p180

Code: Select all

x = 7, y = 2, rule = B2e3ajr4air5i/S012cei3aenr4a5i
bo$obobobo!

8x2 : p268

Code: Select all

x = 8, y = 2, rule = B2ei3aejr4a5i/S12aci3aenr4a5i
3o4bo$4b2obo!

9x2 : p380

Code: Select all

x = 9, y = 2, rule = B2e3ejr4r/S012aik3aeinr4ai5i
ob2o4bo$2b5o!

10x2 : p710

Code: Select all

x = 10, y = 2, rule = B2eik3aejn4ar5i/S012eik3a4ai5i
obo3b2obo$bobob2obo!

3x3 : p72

Code: Select all

x = 3, y = 3, rule = B2ei4aijknr5jnq/S012-en3ajnr4i5ij6ak
bo$o$b2o!

A 5x1 p4 found with LLS, but in a B0 rule (so the "bounding-box" is actually ill-defined) :

Code: Select all

x = 5, y = 1, rule = B012aci3i7e8/S6i
3obo!

Also, there are no 1-cell-thick oscillators with period strictly larger than 2 in non-B0 rules.
Proof :
Let us consider O a period p > 2 oscillator with a 1xn bounding box in a non-B0 rule. We can assume without loss of generality that O is the smallest such oscillator for the given rule. We can also view O as an oscillator in an outer-totalistic range-1 1-dimensional rule R.

R cannot have B1, because any pattern would grow towards infinity on both sides. But we need birth and death because the period is >= 2, so R must have B2.
This means that the instantaneous bounding box remains the same. Therefore the cells at the extremities trigger a survival transition, either S0 or S1.

• If S0 only were triggered on a given end during the cycle, we could remove the last cell : its constantly off neighbour would always have less on neighbours than it had before the removal, and therefore would behave the same. But this contradicts minimality.

  Code: Select all

  x = 3, y = 4, rule = B/S012345678History
  CBA3$C2B!
  

• If S1 only were triggered on this end, by a similar argument of minimality the third cell should change its state during the cycle. In particular, it would be on at least once, so R would have S2. Therefore, a row of 2 or more consecutive cells could not shrink, contradicting the behaviour of the three edge cells.

  Code: Select all

  x = 3, y = 4, rule = B/S012345678History
  2CA3$2CB!
  

So R has both S0 and S1, thus not S2, and R is B2/S01.

If we take a phase P of O, we can consider it as a series of runs of consecutive on/off cells.
If there is a gap wider than 1, we have separate patterns on both sides (because R does not have B1), with respective periods p1 and p2. We have lcm(p1, p2) = p > 2, so p1 > 2 or p2 > 2, which contradicts again minimality. All gaps in P have length 1.

Code: Select all

x = 23, y = 10, rule = B2i/S01History
7.3A.A2BA.A3$7.D8.D$4.D.D10.D.D$4.2D12.2D$4.3D10.3D3$3A.A15.A.A!

P cannot have an island with 4 cells or more, since it would create a wide gap on the next generation.

Code: Select all

x = 5, y = 5, rule = B2i/S01
4o4$5o!

It cannot have an island with 2 cells either, because both cells would survive, and there would be a birth on a least one side (gaps of length 1), without a death for the cell beyond the gap (S01) causing the appearance of a length-4 (or more) island.

Code: Select all

x = 12, y = 5, rule = B2i/S01History
4.2CDC4$3A.2CDC.3A!

Finally, any single dot must be on an end, since it would otherwise create a length-5 island on the next generation.

Code: Select all

x = 9, y = 5, rule = B2i/S01History
2.CDEDC4$2ACDEDC2A!

We are left with patterns such as these, which are always p2 oscillators in R :

Code: Select all

x = 13, y = 7, rule = B2i/S01
obo3$ob3obo3$ob3ob3ob3o!

[confocaloid]

At least in part, this is a rediscovery, for example there was a p72 oscillator in 3-by-3 already known (although it looks like a different p72 oscillator). See the related linked thread:
viewtopic.php?f=11&t=6047 Upper limit for oscillator period with N cells in envelope box

[...] 3x3 : p72

Code: Select all

x = 3, y = 3, rule = B2ei4aijknr5jnq/S012-en3ajnr4i5ij6ak
bo$o$b2o!

[...]

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