40x1 -> infinite growth and glider gun

[Aloril]

Grows infinitely and at tip of growth fires gliders:

Code: Select all

x = 40, y = 1, rule = B3/S23
5o2b3o3b7ob5o5b9o!

If this and mirror are spaced at enough even distance, grows pattern back from collision point until out of space:

Code: Select all

x = 10040, y = 1, rule = B3/S23
9o5b5ob7o3b3o2b5o9960b5o2b3o3b7ob5o5b9o!

With big distance grows second pattern beside first one:

Code: Select all

x = 100000040, y = 1, rule = B3/S23
9o5b5ob7o3b3o2b5o99999960b5o2b3o3b7ob5o5b9o!

[hkoenig]

Those are Glider/Type 2 Switch Engines. It's not a "glider gun" but a "forward rake".(The other type of Switch Engine being the 8-Block/Type 1)

[p46beth]

Nice, though a 39 by 1 infinite growth pattern is already known. I think this has a faster growth rate though, due to the gliders.

[Aloril]

Yes, that 39x1 pattern at http://www.conwaylife.com/wiki/index.ph ... ck_pattern is what caused me to search further. So far all other infinite growth patterns are variations of these 2 (mainly different timing, sometimes few extra gliders and different initial debris). Main goal was to find pattern that generates unlimited amount gliders.

Running times for different bit sizes (record marked with '!'):
1 bits: 1 generations!
2 bits: 1 generations
3 bits: 1 generations
4 bits: 2 generations!
5 bits: 6 generations!
6 bits: 12 generations!
7 bits: 14 generations!
8 bits: 48 generations!
9 bits: 25 generations
10 bits: 82 generations!
11 bits: 185 generations!
12 bits: 285 generations!
13 bits: 158 generations
14 bits: 119 generations
15 bits: 3183 generations!
16 bits: 375 generations
17 bits: 395 generations
18 bits: 1138 generations
19 bits: 3183 generations
20 bits: 3137 generations
21 bits: 2668 generations
22 bits: 3767 generations!
23 bits: 3069 generations
24 bits: 5029 generations!
25 bits: 5685 generations!
26 bits: 5802 generations!
27 bits: 6292 generations!
28 bits: 8403 generations!
29 bits: 5798 generations
30 bits: 5909 generations
31 bits: 7902 generations
32 bits: 6647 generations
33 bits: 9657 generations!
34 bits: 9352 generations
35 bits: 12048 generations!
36 bits: 10667 generations
37 bits: 11790 generations
38 bits: 14811 generations!
39 bits: 14605 generations
40 bits: 13783 generations
41 bits: 21178 generations!
42 bits: 14911 generations

Spaced by 10000, N bits at coordinate N*10000.

Code: Select all

x = 410042, y = 1, rule = B3/S23
o9999b2o9998bobo9997b4o9996b5o9995b6o9994b7o9993b8o9992b3ob5o9991b4ob
5o9990b3ob7o9989b4ob7o9988b5ob7o9987b5ob8o9986b4o2b3ob5o9985b4ob5ob5o
9984b3ob13o9983b4ob7ob5o9982b3ob4o2b3ob5o9981b4o3b7ob5o9980b4o2b3ob5ob
5o9979b3o2b7o2b4ob3o9978b5ob3o3b3o2b6o9977b3o5b3o2b4o2b5o9976b3o2b3o2b
4o3b8o9975b3o2b3ob10o2b5o9974b4ob3o8b3ob7o9973b7ob4o2b14o9972b5ob3o2b
12ob5o9971b3ob5ob3o2b8ob6o9970b3o4b5o3b5ob10o9969b4ob3ob12o2b3ob5o
9968b3ob4ob4o4b4ob5ob5o9967b3ob4ob4ob8ob3ob7o9966b3o3b5o5b8ob3ob6o
9965b6ob4ob3o2b11ob7o9964b4ob5o4b3ob4ob4o3b7o9963b4o2b4o3b5o2b5o2b3o2b
6o9962b3o3b9o2b4ob6o2b4o2b3o9961b3o5b3o3b5o3b4o2b6o2b4o9960b10o3b3ob4o
3b3ob13o9959b3ob6o2b3o2b5o2b5o3b4o2b4o!

For which values of N and M has NxM been searched exhaustively?
For M=1 it has been now searched for N<=42.

[calcyman]

Are you doing the Callahan-esque search, where rows of fewer than three live cells are not considered? This cuts the number of searches from 2^n to Phi^n, where Phi = 1.618033...

And the running time function is uncomputable. It seems unbelievable at first, but your '!' function eventually overtakes the Ackermann function.

[Aloril]

In addition skipping rows of less than 3 I skip all that have only length<=4 live cells. Also skipping mirrored versions.

It seems to be already growing faster than exponential when looking at logarithmic plot. I do hope that it hits soon deep growth, but I'm sceptical that it would happen before 50 bits. Maybe around 60-100 bits? I wonder for how many bits its possible to calculate busy beaver function for GoL?

[calcyman]

I do hope that it hits soon deep growth, but I'm sceptical that it would happen before 50 bits. Maybe around 60-100 bits?

My proof of the result is derived from the possibility of building a Turing machine in Life, so it doesn't give any reasonable estimate as to when it transcends these fast-growing functions, only that it will do eventually.

At least it starts off nice and slow, unlike the original Busy Beaver function, where even sigma(6) is unknown.

[p46beth]

Hmm, it is an interesting sequence. It seems to skip around wildly. I searched the first few terms in Sloane's OEIS, and it does not have an entry.

Now, lets look at the positions of the new highest values:
1,4,5,6,7,8,10,11,12...

This is also not in OEIS (from what I have found Sloane's has relatively few sequences related to cellular automata.)

I found similar lack of apparent pattern when searching large starting blocks in B345/S4567. In this case, odd patterns tended to result in low period oscillators. But patterns composed entirely of 2 by 2 blocks (assimilation is a blockic CA) tended to become very high period oscillators.
I searched squares filled 100% with an even side length for their period. Many ended up quite high. For a 2n by 2n square, the resultant oscillator had period:
n a(n)
1 1*
2 2*
3 4*
4 6*
5 8*
6 6
7 10*
8 8
9 30*
10 416*
11 4
12 1516*
13 9420*
14 1870
15 14634*
16 23142*

Questions this raises:
Does a pattern exist (aside from the definition)?
Do either of these sequences return to a certain value infinitely often?
Can we prove that it does, in fact, exceed any arbitrarily high value?

[Aloril]

43 bits: 17034 generations (no new record)

Code: Select all

x = 43, y = 1, rule = B3/S23
3ob9o2b4o2b4ob4ob4o2b6o!

Resulting debris looks a bit like square.

[Aloril]

New record:
44 bits: 22878 generations!

Code: Select all

x = 44, y = 1, rule = B3/S23
6ob4o2b4o6b3ob5ob3ob7o!

Not a record:
45 bits: 21723 generations

Code: Select all

x = 45, y = 1, rule = B3/S23
3ob3ob5ob3o2b3ob3ob5ob5o2b5o!

I have reran 5-43 bits and ran 44-45 bits with escaping spaceship counting code.

Records:
1-14 bits: none
bits: total spaceships('!'==record): pattern as integer: list of spaceship counts
15 bits: !6: 31199 glider:6
16 bits: 4: 63455 glider:4
17 bits: 4: 116607 glider:4
18 bits: 4: 237551 glider:4
19 bits: !8: 499695 glider:8
20 bits: !12: 933863 glider:12
21 bits: 12: 1996767 glider:12
22 bits: !14: 3936127 glider:14
23 bits: 12: 7403487 glider:12
24 bits: !22: 14739359 glider:22
25 bits: 22: 30308607 glider:22
26 bits: 18: 62392191 glider:18
27 bits: !24: 129630143 glider:24
28 bits: !30: 267337727 glider:30
29 bits: !32: 486260991 glider:30 lwss:2
30 bits: 26: 998374647 glider:26
31 bits: 30: 1895365631 glider:30
32 bits: 30: 4030467967 glider:30
33 bits: !40: 8035301343 glider:40
34 bits: 32: 16634413039 glider:32
35 bits: 40: 34123005439 glider:40
36 bits: !42: 60137662463 glider:42
37 bits: 42: 121282230391 glider:42
38 bits: !56 248855896047 glider:54 lwss:2
39 bits: 50: 541164248831 glider:50
40 bits: 44: 1024347726327 glider:44
41 bits: 46: 2147357286367 glider:46
42 bits: 54: 4327147028031 glider:54
43 bits: 56: 8675833671551 glider:56
44 bits: !70: 15933779156967 glider:68 mwss:2
45 bits: 64: 34217601765279 glider:64

Spaced by 10000, N bits at coordinate N*10000.

Code: Select all

x = 300045, y = 1, rule = B3/S23
4o2b3ob5o9985b4ob5ob5o9984b3o3b3ob7o9983b3o2b8ob4o9982b4o2b8ob4o9981b
3o3b9o2b3o9980b4o2b3ob5ob5o9979b4o6b4ob7o9978b3o4b4ob5ob5o9977b3o5b3o
2b4o2b5o9976b3o2b3o2b4o3b8o9975b3ob3o8b3ob7o9974b4ob3o2b10ob6o9973b7ob
4o2b14o9972b3o2b5ob4o6b8o9971b3ob3o6b7o2b4ob3o9970b3o4b5o3b5ob10o9969b
4o6b4o6b4ob7o9968b3ob4ob4o4b4ob5ob5o9967b4ob5ob5o2b11ob4o9966b7o3b4o3b
3ob4ob9o9965b3o10b4ob5o2b11o9964b3o4b4o2b5ob7o4b3ob3o9963b3o2b5o4b4ob
4o2b8ob4o9962b5ob12o2b3o3b4ob8o9961b3ob3o2b10o4b4o4b5ob3o9960b5o2b7o4b
3ob5ob7ob5o9959b5ob4ob6o5b5ob5o3b6o9958b6o3b15ob5ob4ob7o9957b3o2b5ob3o
b5o2b6o3b8o2b3o9956b5o3b4ob3o2b12o3b5o2b5o!

[Aloril]

Not a record:
46 bits: 18963 generations; pattern as integer: 65901428276223

Code: Select all

x = 46, y = 1, rule = B3/S23
3ob5ob6ob5o2b3o3b5ob10o!

New record:
46 bits: 72 spacehips: pattern as integer: 62105494518799 glider:72

Code: Select all

x = 46, y = 1, rule = B3/S23
3o4b5o6b8o5b5o6b4o!

Not a record:
47 bits: 18937 generations; pattern as integer: 123213987301255

Code: Select all

x = 47, y = 1, rule = B3/S23
3o8b10ob5o3b3o3b4o4b3o!

Not a record:
47 bits: 70 spaceships: pattern as integer: 127470233255711 glider:68 mwss:2

Code: Select all

x = 47, y = 1, rule = B3/S23
3o2b5ob3ob5o2b6o3b8o3b5o!

[Aloril]

Error in previous post, fixed version: Not a record:
47 bits: 21178 generations; pattern as integer: 137333622038527

Code: Select all

x = 47, y = 1, rule = B3/S23
5o2b3o2b3ob4o2b3o5b3ob13o!

Not a record:
48 bits: 22878 generations; pattern as integer: 263738777007999

Code: Select all

x = 48, y = 1, rule = B3/S23
3ob6ob4o2b4o6b3ob5ob3ob7o!

New record:
48 bits: 90 spaceships! pattern as integer: 268278940777599 glider:90

Code: Select all

x = 48, y = 1, rule = B3/S23
4o2b11o3b3ob4ob3o2b4o3b7o!

Not a record:
49 bits: 21178 generations; pattern as integer: 509570472599551

Code: Select all

x = 49, y = 1, rule = B3/S23
3o2b4ob3o2b3o2b5o7b3ob13o!

Not a record:
49 bits: 72 spaceships: pattern as integer: 528038345210911 glider:72

Code: Select all

x = 49, y = 1, rule = B3/S23
4o7b7o6b8o2b5o5b5o!

New record:
50 bits: 23070 generations! pattern as integer: 993751216392159

Code: Select all

x = 50, y = 1, rule = B3/S23
3o4b5o2b5ob4o4b7o4b5ob5o!

Not a record:
50 bits: 88 spaceships: pattern as integer: 993751216392159 glider:88

Code: Select all

x = 50, y = 1, rule = B3/S23
3o4b5o2b5ob4o4b7o4b5ob5o!

[Aloril]

New record:
51 bits: 24787 generations! pattern as integer: 2180305369668863

Code: Select all

x = 51, y = 1, rule = B3/S23
4ob5ob5o2b4o2b3o4b5o2b3o2b8o!

Not a record:
51 bits: 80 spaceships: pattern as integer: 2038440902770559 glider:80

Code: Select all

x = 51, y = 1, rule = B3/S23
3o2b4ob5o2b3o6b4o2b4ob6ob7o!