Thread for basic questions

For general discussion about Conway's Game of Life.
User avatar
wwei23
Posts: 2451
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: Thread for basic questions

Post by wwei23 » January 6th, 2021, 11:22 pm

MathAndCode wrote:
January 6th, 2021, 10:54 pm
Yes, but what about all of the cases in between?
I couldn't find examples on the LifeWiki for those. I was just pointing out some of the periods we definitely had. :P
@Hunting so we're making a referential signature chain?
Stop being mean to MathAndCode!
LeapLife has fun drifters!

User avatar
calcyman
Posts: 2352
Joined: June 1st, 2009, 4:32 pm

Re: Thread for basic questions

Post by calcyman » January 6th, 2021, 11:56 pm

For periods of the form 8n+4, all p >= 92 are all possible.

In particular, the following family gives you 148 and above (it just misses 140, because the p140 oscillator has minpop 141):

Code: Select all

x = 35, y = 35, rule = B3/S23
19b2o$10bo9bo7bo$10b3o7bobo3b3o$13bo7b2o2bo$12b2o12bo$24b2o$b2o14bo6bo
$2bo13bobo$2bobo11bo2bo3b2o$3bobo11b2o4b2o$5bo2b2o22b2o$2bo2bo2b2o22bo
$2bo27bobo$3bo26b2o$3o$o7bo$6b2o2bo15b2o$9b2o14bo2bo$25bobo$26bo7bo$
32b3o$3b2o26bo$2bobo26b2o$2bo22b3o$b2o22b6o$10b2o4b2o10b2obo$9bo2bo2bo
2bo11bobo$16bobo13bo$17bo14b2o$8bo2bo$8bob2o9b2o$9bob3o7bo$6b3o3bobo7b
3o$6bo7bo9bo$14b2o!
But you can get 140 with this LCM oscillator:

Code: Select all

x = 21, y = 27, rule = B3/S23
9bo$8bobo2b2o$8bobo3bo$6b2obob3o$5bobo3bo$4bo2bob2o$3bo3b2o$3b4o$b2o3b
o$o2bobo4b2o$b2o2bo3bobo$3b2o4b2o$3bo$bobo$b2o2$12bo6bo$6b2o3b2o7bo$6b
2o3bobo5b2o$12b3obo$14b3o2$14b3o$12b3obo$6b2o3bobo5b2o$6b2o3b2o7bo$12b
o6bo!
And 132-in-132 is possible (jslife), only just:

Code: Select all

x = 42, y = 44, rule = B3/S23
20b2o10b2o$19bo2bo8bo2bo$19b3o2b6o2b3o$22b2o6b2o$21bo10bo$21b2obo4bob
2o$4bo21b2o$4b3o$7bo$6b2o23b2o$31b2o6$26bo$2b2o21b3o12b2o$bobo20bo3bo
11b2o$bo22b2ob2o$2o3$2o$bo22b2ob2o$bobo20bo3bo11b2o$2b2o21b3o12b2o$26b
o6$31b2o$6b2o23b2o$7bo$4b3o$4bo21b2o$21b2obo4bob2o$21bo10bo$22b2o6b2o$
19b3o2b6o2b3o$19bo2bo8bo2bo$20b2o10b2o!
This one gives you period 124: https://conwaylife.com/wiki/Mold_on_Merzenich%27s_p31

Here's an example for 116:

Code: Select all

x = 30, y = 25, rule = B3/S23
23b2o$23bo$25bo$10b2o9b4obo$9bobo9bo3bobo$9bo13bo3bo$7b2ob4o8b4ob2o$6b
o3bo2bo7bo3b2o$6bobobo5b2o2bo2b2o2b2o$4b2ob3o6b2o3b2obobo2bo$3bo2bo19b
obo$3bob2o14b2obobob2o$b2o3bo14b2ob2o$o2b3o$2obo$3bo$3b2o6bo5bo$10b3o
3b3o5$10bo7bo$9bobo5bobo$10bo7bo!
This handles p108: https://conwaylife.com/wiki/T-nosed_p4_on_56P27

and p100: https://conwaylife.com/wiki/Centinal

and p92: https://conwaylife.com/wiki/Twin_bees_s ... ng_blinker
What do you do with ill crystallographers? Take them to the mono-clinic!

User avatar
toroidalet
Posts: 1212
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: Thread for basic questions

Post by toroidalet » January 7th, 2021, 7:29 pm

Using 3 gliders in the rectifier loop, we can get 8n+6 for n≥19 (lowest period is the disappointingly high 158):

Code: Select all

x = 101, y = 79, rule = B3/S23
8bo$7bobo$8bo2$6b5o$5bo4bo20b2o$4bo2bo23bo$bo2bob2o21bobo$obobo5bo18b
2o$bo2bo4bobo7bo3bobo$4b2o2bo2bo5bo2b2obobo$9b2o9bo3bo$16bo23b2o$16bo
2bo20bo$15bo2b2o18bobo$16bo3b2o16b2o$16bo3b2o$15bo3b2o$14bobo$14bobo$
15bo$38bo$39bo$37b3o7$30bo$29bobo$29bobo$30bo2$42b2o$41b2o$43bo8$70bo$
69bobo$69bobo$70bo11$75bo$74b2o$73bo$74b2o$61b2o12bo$60bobo$60bo$59b2o
$90b2o$89bo2bo2b2o$89bobo4bo2bo$70b2o18bo5bobobo$69bobo21b2obo2bo$69bo
23bo2bo$68b2o20bo4bo$90b5o2$92bo$91bobo$92bo!
And 8n+2 for n≥20 (lowest period 162):

Code: Select all

x = 143, y = 121, rule = B3/S23
8bo$7bobo$8bo2$6b5o$5bo4bo20b2o$4bo2bo23bo$bo2bob2o21bobo$obobo5bo18b
2o$bo2bo4bobo$4b2o2bo2bo$9b2o$40b2o$40bo$38bobo$38b2o$24b2o$25b2o$24b
2o$21bo11$30bo$29bobo$29bobo$30bo9$57bobo$58b2o$58bo12$63b2o$63bobo$
63bo24$98bo$99b2o$98b2o3$112bo$111bobo$111bobo$112bo7$103b3o$103bo$
104bo$127bo$126bobo$126bobo$122b2o3bo$121b2o3bo$103b2o16b2o3bo$102bobo
18b2o2bo$102bo20bo2bo$101b2o23bo$118bo3bo9b2o$117bobob2o2bo5bo2bo2b2o$
117bobo3bo7bobo4bo2bo$112b2o18bo5bobobo$111bobo21b2obo2bo$111bo23bo2bo
$110b2o20bo4bo$132b5o2$134bo$133bobo$134bo!
At this point, reflector loops get us all periods that are not multiples of 8, which are much easier due to being composite.

In response to Moosey's variation, it seems like the way to go is period multipliers, Mersenne loops, and composite oscillators (we can then trivially bring the stator up by using more complex catalysts or maybe adding barberpoles).
Creationism is an insult to God. He would have done a much better job.

User avatar
wwei23
Posts: 2451
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: Thread for basic questions

Post by wwei23 » January 7th, 2021, 10:11 pm

Don't we already have a c/3 orthogonal wickstretcher? This example was grabbed straight from jslife.

Code: Select all

x = 285, y = 248, rule = B3/S23
197b3o$198b2o$197bo$196bo2b2o$199b2o$196b3o$196bo$196bo$196b2obo$199b
2o$198b3o$198bobo$197b2obo$197b4o17bo$173bo24bo2b2o2bo11bobo$166bo5bob
o26bo2bobo12b2o$165bobo4bobo23bo2bo4b2o10bo$167b2o5bo29bobo12b2o$166bo
7b2o22b3o4b2o11b3o$167b2o4bobo25bobo$166b3o30b2o3bo2bo9bo2bo$174b3o3bo
27bo9bobo$165bobo6b3o2bobo16bobo7bo11bo$165b3o6bo4bobo16bobo5bob3o8bo$
170bo4b2o4bo17b2o5bo2b3o5bobo$162b3o4bo2b2o2bo4b2o12b2o2bo4bob3o2bo6bo
22bo$141bo20b3o6bob3o4bobo10bo2b2o2b2o2bo3b3o7b2o12bo9b2o$140bobo27b4o
bo16b2obo4bo14b2obo14bo8b2o$142b2o20b2o5b2obo6b3o8b2obo3b2o4b3o4bob4o
15b2o6bo$141bo22b2o5b2obo6b3o9bo2b2o5bob3o4bobo19bo8bo$142b2o19bo10bo
6bo12bob2o3bo5b2o23b4o5bobo$68bo72b3o27b2o4bo4b2o18b4o6bo2bo20bo6bo$
69bo100bo2bo2bo2b2o2bo13bobobobo3bo3bo3bo18b3o3bobo$69b2o69bobo19b3o2b
2o2b3o4bob3o13bo2bo3bo3bo5bo2bo20b2obobo$70bo69b3o18bo2bo5bo2bo3b4obo
22bobo4bob3o19bobo$67b2ob2o99b2o5b2obo15bob4o3bo9bo17b2o2bob3o$66bo3bo
66b3o21b4obo11b2obo16b3o11b3o21bo4b2o$68b2o67b3o23bo2bo14bo32bo21b3o$
68bo87bo21b2o32b2o23b4o$68b2o69b2o14bo5b3o13bo2bo20bo8bo12b2o12bo2bo$
65bo2b2o69b2o13b3o5bobo9b2o2b3o16b2obo11bo10b2o3b2o2b2o5bo$66bo3bo67bo
16b2o12bo7bo2bo16bo4bo7b2o4bo4bo7bobo2bo2b3o$70b2o91b2o13b2o14bo3b3ob
2obo4bo2bo2b2o4b7ob5obo$69bo2bo68bo21bobo3bo3bo20bo15bo2bo3bobo11bo$
69bo71bo22b2obo4bobo18b2o9b3o3bo4b3o3b6o3bo2b3o4b2o$69b2obo16bo50bob3o
26bo3bo29bobo2bo4b2o4bo4b2ob2obo3bobobo2bo$43bo25bo2bo3bo11bobo50b4o
16b3obo5bo3bo15b2o11bob2o2bo4b2obo2b2o3bo4b3obobo6b2o$37bo6b2o24b3o2bo
bo10bobo50b2obo17bo8bo3bo14b3o12bo2b3o3bo3bo2b4o2b2o4b2o5bo3b2o$36bobo
5b2o23b3o4b2o12bo50b2o29bobo16b2o11bob2o2bo4b2obo2b2o3bo4b3obobo6b2o$
36bobo4bo26bo6bo63bo2bo21b3o4bo12b2o17bobo2bo4b2o4bo4b2ob2obo3bobobo2b
o$38bo6bo22bob2o2bobo13b2o49bobo12b2o7bo3bo16b2o5b2o9b3o3bo4b3o3b6o3bo
2b3o4b2o$44b3o24bo2bobo11bobo50bo2bo11b2o6bo5bo11bo11bo15bo2bo3bobo11b
o$38b2o6bo22b3o3b3o11bobo50bobo18bo3bo3bo9bobo10bo3b3ob2obo4bo2bo2b2o
4b7ob5obo$36bobo7b2o2bo26b2o10b3o71bo2bobo2bo8bo2bo13bo4bo7b2o4bo4bo7b
obo2bo2b3o$37b2o4b2o6b2o16b3o6b2o62b3o18bo3bo3bo9b2o14b2obo11bo10b2o3b
2o2b2o5bo$37bo8bo4b2o17b2o5bo10bobo73bo5bo30bo8bo12b2o12bo2bo$33bo2bo
4bo4bo3bo15bo10bo2b3o6b2o74bo3bo42b2o23b4o$32bo8b3o3bo4bo13bo4bo3b3obo
bo7bo22bo53b3o45bo21b3o$12bo21b2o4bobob3o4b3o10b2obobobo3bo4bo6bobo13b
o7bobo77bo20b3o21bo4b2o$11bobo19bobo17bo10bobobo2bo8bo6bobo12bobo8b2o
36bo40bo23bo17b2o2bob3o$11bobo21b2o4bobo2bo6b2o9bobob3o6bo5b2o2b2o15bo
7bo38b2o38bo20bob3o19bobo$13bo19bobo7b3o4b2o12b2ob2obo3b2ob2o4b3o16bo
2bo7b2o31b3ob5o13bo44bo2bo20b2obobo$34bo9bo8bo11bo4b2obo4bo24b3o6b3o
24bo4bobo8bo11bobo41bo3bo18b3o3bobo$13b2o26b3o4bo4bo11bo2bob2o3b2obo4b
3o20bo31bo3bobo4b2o2bobo12b2o42bo2bo20bo6bo$11bobo25bo8b3o3bo13bobobob
obo5bob3o18b3o4b2o27bo2b3o2bo5bo13bo62b4o5bobo$12b2o25bobob2o2bobob3o
13b2obob2o2b3o3bo25bo2b3o24b2obo6bo5bo4bo6bobo43bobo19bo8bo$12bo26bo3b
2o23b2o2b2o2b3o5bob2o17b2obobo20bo20bobo3bobo5bobo43bob4o15b2o6bo$8bo
2bo29b2o5bobo2bo14b5o9bo3b2o24b2o15bobo10b2o9bo6bo6b4o44b2obo14bo8b2o$
7bo42b3o30b3o20bobo3bo17b2o12bo8b2o3bo2bo7bobo46b2o12bo9b2o$9b2o40bo
33bo21bo27b3o4bo2bo5bobo5b3o7bobo46bo22bo$8bobo37b3o32b2o24b2o25b2o4bo
bo7bo4bo3bo10bo44bobo$10b2o20bo4b3o6bo34b3o8bobo4bo8bob2o23bo7bo13b4o
9bobo46bo$8bobo13bo6bobo2bo2bo6bobob2o21bo6bo2bo8bob2o3bo3b2o2bo2bo25b
3o17b2o14bo47bo$9bo14b2o14bo5bo3b2o20bob2o6bo3bobo7bo3bobo2bo4bo24bobo
2b2o14b2o12bo47bobo$24bo8bo7bo6b2o25b2o5b2o4bo3b8o3bobobobo27bo2bobo
14b5o9b2o44bo2bo$24bo2bo4bo3b2ob2o31b2o4bo3b3o4b2o11bo3bob3o24b3o2bobo
15bo12b2o$17b2o3b3obo5b2o3bobo33bo2bobo3b2o2bo2b2ob6o3bob4ob2obo21b3o
6bo16bo2bo7bo47b3o$bo14bo2bo3b3o7bo39b3o2bo3b3ob2o2bobo4bo4b2o3bo3b2ob
o11bo7b2o6b2o17b2o56b2o$bo13b2o2bo14bo13b3o21bobo3bo3b3o5b2o2bo4bobo3b
obobo2b2obo11b2o12bobo17b2o55bo$3o13b2ob2o50b3o4bo3b3o2bo2b2o2bo2b2o5b
o7b2ob2o9b2o5bo2bo24bo17bo39b2o$16b2obo28b2o22bobo3bo3b3o5b2o2bo4bobo
3bobobo2b2obo21bo4b3o13b2o2b2o2bo13b2o35bobo$46bo2bo11b2o10b3o2bo3b3ob
2o2bobo4bo4b2o3bo3b2obo18bo3b2o5bo16b2o4b2o11b2o36bo$3o13b2o13b2o13b2o
13b2o10bo2bobo3b2o2bo2b2ob6o3bob4ob2obo20bo2b2o6bo23b2o10bo$bo29b2o9bo
4b4o21b2o4bo3b3o4b2o11bo3bob3o24b6o2bo15bobo19bo$bo39bobo5b2o6b2o16b2o
5b2o4bo3b8o3bobobobo22bo2bo24b2o3b3o11bobo$40bo2bo12b2o14bob2o6bo3bobo
7bo3bobo2bo4bo23bob3o2b2o16bo2bo2b3o11bobo$41b2o13bo5b2o9bo6bo2bo8bob
2o3bo3b2o2bo2bo22b2o3bob2o19bo18bo$61bo2b2o15b3o8bobo4bo8bob2o21b3ob4o
20bo6b2o11b2o$b2o57bo22b2o24b2o12bo9b3o3bo29bo11bo$b2o57bo5bo18bo21bo
16bo34bob2o6bo2bo6b3o$bo81b3o20bobo3bo9b3o11b2o2b3o16bobo5bo4bo7bo$60b
2ob3o16bo3b2o24b2o23bo2b3o13b5obo4bo4bo5bo24bo$17bo3b3o60bob2o17b2obob
o24bo5b2o10b2o3bob3o3bo2b3o7b2o21bobo$15bo2bo5bo13bo43bo25bo2b3o22b2o
18bo9b5o4bo3b2o12b3o6bobo$14bo3bobo4b2o12b2o41bob3o18b3o4b2o26bo2b2o
11bo3b2o3b2obo6bo2bo15b2o8bo$bobo5b3o4bo3bo3b3o12b2o42b3o20bo29b3o4bo
9b2o3b2obo3b2o8bobo15bo$2b2o5b5o2bobobo82b3o6b3o20bob3o3bo12b3o9b2o4bo
19b3o7b2o$2bo7bo4bo3bo3bobo11b3o43b3o16bo2bo7b2o20bo3bo17b3ob2ob2ob3o
27bo4bobo$24b2o11b3o43b2o2b2o15bo7bo24bo3b2o16bobo5bo5bob3o18b2o2bo2b
2o$12b2o10bo62bobo12bobo8b2o20bo3bo2bo16bobobobo2b2o3b2o2bo21bo$14b2o
6bobo15b3o44bobo13bo7bobo4bobo15b3obob2o15b2ob2o4bo5b2ob2o17b2obobobo$
14b2o6bobo15bobo46bo22bo6b2o12b3o6bo19bo4bo5bo3bo18b2o2b2obo$14b2o7bo
65b2o28bo13bob2ob4o17bo14b3o20bob3obo$13bo27b3o44bobo45bo2b2o19bo14bo
21bo3b2o$42b2o90bo5bo33bo26bo$41bo47b3o45bo18bobo13b3o9b2o12bo2bo$42b
2o45bobo44b4o31bo11b3o3b3ob2o3bob2o$40bobo45bobo65bobo12b3o3b2o8bo7b2o
b3o$41bo48b2o78b2obo3b3o3b8o3b3ob2o$168bo2b2o2b2o5bo7bo$90bo76bobob2o
2b2ob2ob8ob2ob4o3b3o$88bobo41b2o32bo4b2o2bo5bo3bo2bob2o5b2ob3o2bo$88bo
bo41b2o8b2o22bo4b2o2bobo3bo4b2o2b3o3b3obo3bobo$89bo38b2o13bo22bo4b2o2b
o3b3o4b3o7bo7bo2bo$113bobo9b2ob3o35bo4b2o2bobo3bo4b2o2b3o3b3obo3bobo$
117bo6b3ob3o24b2o9bo4b2o2bo5bo3bo2bob2o5b2ob3o2bo$b2o7b2o13b2o13b2o13b
2o13b2o13b2o13b2o11b2o2bo7b2ob2o10bo5bo7bobo10bobob2o2b2ob2ob8ob2ob4o
3b3o$b2o6bobo12bobo12bobo12bobo12bobo12bobo12bobo12bo11b3o7bo3bo2b5o5b
3o12bo2b2o2b2o5bo7bo$9b2o13b2o13b2o13b2o13b2o13b2o13b2o13bobo10bo7bobo
3bobo3bo5b2o15b2obo3b3o3b8o3b3ob2o$113bo2bo17bo2bo6b2o5b2obo16b3o3b2o
8bo7b2ob3o$114b2o19b2o14b2obo16bo11b3o3b3ob2o3bob2o$20b2o129b2o2bo2b2o
12b3o9b2o12bo2bo$20bobo130b3ob2o15bo26bo$20bo154bo21bo3b2o$174b3o20bob
3obo$173bo3bo18b2o2b2obo$174b2ob2o17b2obobobo$125b5o43b2o2bo21bo$125b
2o2b2o2b3o37bob3o18b2o2bo2b2o$124b2obob2o2b3o61bo4bobo$8bo116bobobobob
o40bo19b3o7b2o$8b2o112bo2bob2o3b2obo39bobo15bo$7bobo37bo74bo4b2obo4bo
39bo2bo15b2o8bo$46b2o73b2ob2obo3b2ob2o39bo3b2o12b3o6bobo$46bobo72bobob
3o6bo44b2o21bobo$121bobobo2bo8bo40bo24bo$121b2obobobo3bo4bo42bo$123bo
4bo3b3obobo40b3o21bo$123bo10bo2b3o41bo20bobo$127b2o5bo46b2o21bo$126b3o
6b2o43bo21bo2bo$134b2o43bobo21b3o$11b3o112b3o3b3o44bobo19bo3bo$13bo
114bo2bobo47bo19b4o$12bo59b3o50bob2o2bobo45bo20b2o$72bo54bo6bo45b2o18b
2o$73bo52b3o4b2o45b2o19b5o$127b3o2bobo44bo22bo$126bo2bo3bo69bo2bo$126b
2obo75b2o$126bo78b2o$126bo2bo75bo$127b2o73b2o2b2o2bo$15b2o106bo3bo77b
2o4b2o44bo$16b2o104bo2b2o84b2o43bobo$15bo83b2o24b2o76bobo52b2o$98b2o
25bo78b2o3b3o45bo$100bo24b2o76bo2bo2b3o46b2o$123bo3bo77bo51b3o$124b2ob
2o76bo6b2o$127bo85bo42bo2bo$126b2o75bob2o6bo2bo40bobo$126bo76bobo5bo4b
o42bo$125bo74b5obo4bo4bo41bo$19b2o168bo7b2o3bob3o3bo2b3o40bobo$18bobo
91bo75bobo9bo9b5o42bo22bo$20bo90bobo11b2o63b2o8bo3b2o3b2obo44b2o12bo9b
2o$111bobo11bobo62bo6b2o3b2obo3b2o43b2obo14bo8b2o$113bo11bo63bobo8b3o
9b2o37bob4o15b2o6bo$191bo9b3ob2ob2ob3o37bobo19bo8bo$64bo48b2o77bo10bob
o5bo59b4o5bobo$63bobo45bobo76bobo10bobobobo2b2o37bo2bo20bo6bo$65b2o45b
obo75bobo10b2ob2o4bo37bo3bo18b3o3bobo$64bo47b3o73b4o14bo4bo40bo2bo20b
2obobo$65b2o120bobo13bo47bob3o19bobo$23bo12bo27b3o44bobo73bobo14bo50bo
17b2o2bob3o$23b2o12b2o7bo65b2o76bo60b3o21bo4b2o$22bobo12b2o6bobo15bobo
46bo22bo16bo36b2o62bo21b3o$37b2o6bobo15b3o44bobo13bo7bobo14b2o35bobo
12b2o46b2o23b4o$35b2o10bo62bobo12bobo8b2o13bobo35bo15bo26bo3b3o10bo12b
2o12bo2bo$47b2o11b3o43b2o2b2o15bo7bo67b2o9b2o15b3o2b2o13bo10b2o3b2o2b
2o5bo$33bo4bo3bo3bobo11b3o43b3o16bo2bo7b2o55bo19bo2bo19b2o11b2o4bo4bo
7bobo2bo2b3o$32b5o2bobobo82b3o6b3o53b2ob2o18bobo3bob3o6b3o2bo12bo2bo2b
2o4b7ob5obo$32b3o4bo3bo3b3o12b2o42b3o20bo85bo3bo5bo5bob3o13bo2bo3bobo
11bo$37bo3bobo4b2o12b2o41bob3o18b3o4b2o57bobo8b3o11bo6bo7bo14bo4b3o3b
6o3bo2b3o4b2o$38bo2bo5bo13bo43bo25bo2b3o55bo3bo9bo13bo28bo4b2o4bo4b2ob
2obo3bobobo2bo$40bo3b3o60bob2o17b2obobo58bo2b2o9bo13bo2bob2o22bo4b2obo
2b2o3bo4b3obobo6b2o$56bo48bo3b2o24b2o56b3o9b2obo12b2o26bo3bo3bo2b4o2b
2o4b2o5bo3b2o$32b3o20b4o47b3o20bobo3bo58bo9bo6b2o8b2o26bo4b2obo2b2o3bo
4b3obobo6b2o$32bo2bo19bo3bo48bo21bo46b3o24b4o3b2o36bo4b2o4bo4b2ob2obo
3bobobo2bo$31bo3bo20bo2bo46b2o24b2o43bo22bo2b3o28bo14bo4b3o3b6o3bo2b3o
4b2o$31bobob2o19b3o32b2o11b3o8bobo4bo8bob2o43bo22bo29bob3o13bo2bo3bobo
11bo$31b3ob2o15b2o8b3o6b2o9bo3b2o2b3o10bo2bo8bob2o3bo3b2o2bo2bo97bo4bo
12bo2bo2b2o4b7ob5obo$31bo3bo15bo2bo7b3o5bo2bo8bo6bo4bo10bo3bobo7bo3bob
o2bo4bo79bobo17bo3bo11b2o4bo4bo7bobo2bo2b3o$31b2obo17b2o11bo5bobo14bo
5bo7bo2b2o4bo3b8o3bobobobo52b2o29bo14b2ob3o14bo10b2o3b2o2b2o5bo$32b2o
12b2o18bo5bo27b2o3b3o4b2o11bo3bob3o48b6o25bo2b2o13bo17bo12b2o12bo2bo$
33bobo10b2o13b2o3bo9b2ob3o3b2o12bo5b2o2bo2b2ob6o3bob4ob2obo47b2o2b2o
24bo3b2o33b2o23b4o$26b3o5b3o25bob5o7b2o3bob3o14bo4b3ob2o2bobo4bo4b2o3b
o3b2obo48b2o5b2o17b2o3bo35bo21b3o$26bo3bo2bo2bo20bo5bo2bo16b3o16bo2b3o
5b2o2bo4bobo3bobobo2b2obo43bo3b3o2bo3b2o13b4obo3bo17b3o11b3o21bo4b2o$
26b2o4b3o2bo13b2o2b3o11bo32bo2b3o2bo2b2o2bo2b2o5bo7b2ob2o41bo2b4o3bobo
b2o19bobobo15bob4o3bo9bo17b2o2bob3o$27bo5bo2bo13b2o2b3o9bob2o13b3o16bo
2b3o5b2o2bo4bobo3bobobo2b2obo41b6o5bo22b7o23bobo4bob3o19bobo$28b2o25b
2o8bobo13bob3o14bo4b3ob2o2bobo4bo4b2o3bo3b2obo43bo11b3o17bo6bo14bo2bo
3bo3bo5bo2bo20b2obobo$27b2o25b2o8bo14b3o3b2o12bo5b2o2bo2b2ob6o3bob4ob
2obo47b3o11bo17b2o3bo16bobobobo3bo3bo3bo18b3o3bobo$28bo34b2o35b2o3b3o
4b2o11bo3bob3o49bo11b3o15b2o4bo21b4o6bo2bo20bo6bo$29bo33bo7b2o15bo5bo
7bo2b2o4bo3b8o3bobobobo60bobo2bo14bob6o12bob2o3bo5b2o23b4o5bobo$62bo6b
o3b2o7bo6bo4bo10bo3bobo7bo3bobo2bo4bo85b3o10bo2b2o5bob3o4bobo19bo8bo$
31bobo29bobo3bobob2o7bo3b2o2b3o10bo2bo8bob2o3bo3b2o2bo2bo58bobob3o15bo
3bo2bo9b2obo3b2o4b3o4bob4o15b2o6bo$33b2o29bo4bo21b2o11b3o8bobo4bo8bob
2o58b3o3bo14bo3bo2bo9b2obo4bo14b2obo14bo8b2o$31bobo37b3o32b2o24b2o59bo
4bo14b2o17bo2b2o2b2o2bo3b3o7b2o12bo9b2o$32b2o40bo33bo21bo67bo15b2o3b2o
13b2o2bo4bob3o2bo6bo22bo$30bo42b3o30b3o20bobo3bo59b2o17bo2bobo18b2o5bo
2b3o5bobo$31bo2bo14bobo12b2o5bobo2bo14b5o9bo3b2o24b2o61b2o11bo25bobo5b
ob3o8bo$35bo13bob2o9bo3b2o23b2o2b2o2b3o5bob2o17b2obobo64bo11bo5bo20bob
o7bo11bo$35b2o13b2o10bobob2o2bobob3o13b2obob2o2b3o3bo25bo2b3o59b3o13b
3o2b2o28bo9bobo$34bobo25bo8b3o3bo13bobobobobo5bob3o18b3o4b2o60bo14bo3b
o2bo18b2o3bo2bo9bo2bo$36b2o26b3o4bo4bo11bo2bob2o3b2obo4b3o20bo65bo16bo
b3o3bo19bobo$57bo9bo8bo11bo4b2obo4bo24b3o6b3o58b2o12b2obo5bo17b3o4b2o
11b3o$36bo19bobo7b3o4b2o12b2ob2obo3b2ob2o4b3o16bo2bo7b2o58b2o12b2o3b6o
22bobo12b2o$34bobo21b2o4bobo2bo6b2o9bobob3o6bo5b2o2b2o15bo7bo59bo15b3o
2bo3b2o15bo2bo4b2o10bo$34bobo19bobo17bo10bobobo2bo8bo6bobo12bobo8b2o
74bo2bo3bo2bo17bo2bobo12b2o$35bo21b2o4bobob3o4b3o10b2obobobo3bo4bo6bob
o13bo7bobo76bobo5b2o14bo2b2o2bo11bobo$55bo8b3o3bo4bo13bo4bo3b3obobo7bo
22bo76b3o6bo14b4o17bo$56bo2bo4bo4bo3bo15bo10bo2b3o6b2o97b2o6b3o14b2obo
$60bo8bo4b2o17b2o5bo10bobo96bobo7bo16bobo$60b2o4b2o6b2o16b3o6b2o110bo
4bo18b3o$59bobo7b2o2bo26b2o10b3o96bo2bobo2b2o17b2o$61b2o6bo22b3o3b3o
11bobo99bo4b2o14b2obo$67b3o24bo2bobo11bobo104bo16bo$61bo6bo22bob2o2bob
o13b2o98b3obo17bo$59bobo4bo26bo6bo114bo19b3o$59bobo5b2o23b3o4b2o12bo
100b2o22b2o$60bo6b2o24b3o2bobo10bobo100bo20bo2b2o$66bo25bo2bo3bo11bobo
99bo22bo$92b2obo16bo124b2o$92bo143b3o$92bo2bo$93b2o$89bo3bo$88bo2b2o$
91b2o$91bo$91b2o$89bo3bo$90b2ob2o$93bo$92b2o$92bo$91bo!
@Hunting so we're making a referential signature chain?
Stop being mean to MathAndCode!
LeapLife has fun drifters!

User avatar
calcyman
Posts: 2352
Joined: June 1st, 2009, 4:32 pm

Re: Thread for basic questions

Post by calcyman » January 8th, 2021, 1:06 pm

toroidalet wrote:
January 7th, 2021, 7:29 pm
Using 3 gliders in the rectifier loop, we can get 8n+6 for n≥19 (lowest period is the disappointingly high 158):

Code: Select all

x = 101, y = 79, rule = B3/S23
8bo$7bobo$8bo2$6b5o$5bo4bo20b2o$4bo2bo23bo$bo2bob2o21bobo$obobo5bo18b
2o$bo2bo4bobo7bo3bobo$4b2o2bo2bo5bo2b2obobo$9b2o9bo3bo$16bo23b2o$16bo
2bo20bo$15bo2b2o18bobo$16bo3b2o16b2o$16bo3b2o$15bo3b2o$14bobo$14bobo$
15bo$38bo$39bo$37b3o7$30bo$29bobo$29bobo$30bo2$42b2o$41b2o$43bo8$70bo$
69bobo$69bobo$70bo11$75bo$74b2o$73bo$74b2o$61b2o12bo$60bobo$60bo$59b2o
$90b2o$89bo2bo2b2o$89bobo4bo2bo$70b2o18bo5bobobo$69bobo21b2obo2bo$69bo
23bo2bo$68b2o20bo4bo$90b5o2$92bo$91bobo$92bo!
And 8n+2 for n≥20 (lowest period 162):

Code: Select all

x = 143, y = 121, rule = B3/S23
8bo$7bobo$8bo2$6b5o$5bo4bo20b2o$4bo2bo23bo$bo2bob2o21bobo$obobo5bo18b
2o$bo2bo4bobo$4b2o2bo2bo$9b2o$40b2o$40bo$38bobo$38b2o$24b2o$25b2o$24b
2o$21bo11$30bo$29bobo$29bobo$30bo9$57bobo$58b2o$58bo12$63b2o$63bobo$
63bo24$98bo$99b2o$98b2o3$112bo$111bobo$111bobo$112bo7$103b3o$103bo$
104bo$127bo$126bobo$126bobo$122b2o3bo$121b2o3bo$103b2o16b2o3bo$102bobo
18b2o2bo$102bo20bo2bo$101b2o23bo$118bo3bo9b2o$117bobob2o2bo5bo2bo2b2o$
117bobo3bo7bobo4bo2bo$112b2o18bo5bobobo$111bobo21b2obo2bo$111bo23bo2bo
$110b2o20bo4bo$132b5o2$134bo$133bobo$134bo!
At this point, reflector loops get us all periods that are not multiples of 8, which are much easier due to being composite.

In response to Moosey's variation, it seems like the way to go is period multipliers, Mersenne loops, and composite oscillators (we can then trivially bring the stator up by using more complex catalysts or maybe adding barberpoles).
p150 from jslife:

Code: Select all

x = 43, y = 56, rule = B3/S23
15bo$15bo11bo$14b3o10bo$26b3o2$14b3o$15bo10b3o$15bo11bo$15bo11bo$15bo
11bo$14b3o10bo$26b3o2$14b3o$15bo10b3o$15bo11bo$27bo4$2bo4bo$2ob4ob2o
25bo4bo$2bo4bo25b2ob4ob2o$35bo4bo$24bo$25bo$23b3o$14b2o12b2o$14b2o12b
2o$23b3o$25bo$24bo$35bo4bo$2bo4bo25b2ob4ob2o$2ob4ob2o25bo4bo$2bo4bo4$
27bo$15bo11bo$15bo10b3o$14b3o2$26b3o$14b3o10bo$15bo11bo$15bo11bo$15bo
11bo$15bo10b3o$14b3o2$26b3o$14b3o10bo$15bo11bo$15bo!
Boring p154:

Code: Select all

x = 33, y = 19, rule = B3/S23
25b2o$25bo$7b3o13bobo$6bo3bo8bo3b2o$5bo4bo6b2obo$6bob2o6bo4bo7b2o$2b2o
3bo8bo3bo8bo$bobo13b3o10bo$bo27b2o$2o26bo$27b4o$25b2o4bo$23bobob3o2bo$
21b3o6b2o$20bo4b2ob2o$21b4o4bo$25b4o$23bo2bo$23b2o!
Other than multiples of 8 (which should be easy), the smallest unsolved periods are 146, 142, 139, 134. Any takers?
What do you do with ill crystallographers? Take them to the mono-clinic!

Donald K Trump
Posts: 42
Joined: November 19th, 2020, 11:13 pm

Re: Thread for basic questions

Post by Donald K Trump » January 12th, 2021, 2:15 am

bubblegum wrote:
January 5th, 2021, 12:46 pm
Donald K Trump wrote:
January 5th, 2021, 2:09 am
I've been watching ColorfulGalaxy's activity lately, and there's something that I really don't understand.
What's "minimum covering convex polygon"?

His wiki articles also listed the unstablised wick "xq1_3cc3z3cc3z" and "xp0_196609966099660".
Do unstabilized wicks have apgcodes?
Also, "xp0_14" leads to "MWSS spark". But the MWSS doesn't have this spark.

Also, can tagalong be made up of gliders?
The Wiki said that the tagalong is not a spaceship.

What should a person do to become a Life enthusiast?
Will ColorfulGalaxy become a Life Enthusiast in the future?

By the way, how did he get the pixel characters and the fake stub message?
A MCCP is the smallest convex polygon (a shape with only straight sides and angles less than 180°) that completely covers the pattern.

No.
It does, but the MWSS is moving up.

A tagalong is a spaceship component that can be attached to the side or back of another spaceship to create a larger spaceship without interfering with the base. Yes, if the tagalong glider(s) is modified somewhat during the interaction each period, otherwise it's just considered an interaction.

They need to be interested in cellular automata.
They are already.

The pixel characters are in Braille and the fake stub message was copied and modified from the real template.
Are his MCCP calculations correct?
Why do some polyominoes have a lifespan of "0"? For example, the block
Why did he list the unstabilised wicks?
What is Euclidean distance?
Why did he call the pi-heptomino and the r-pentomino "Unknown reaction" in his Wiki article?
Why is "Lumps of muck" put in parentheses?
Why did he end the pentomino list with ellipsis like "....."?

What is a "Cyclotronic park"? Are there any other examples?

What is a Turing-complete rule?
bubblegum wrote:
January 5th, 2021, 12:46 pm
They are already.
He hasn't made any useful discoveries yet.

Also, Braille letters can't be 4 cells high.

bubblegum
Posts: 735
Joined: August 25th, 2019, 11:59 pm
Location: click here to do nothing

Re: Thread for basic questions

Post by bubblegum » January 12th, 2021, 2:16 am

Donald K Trump wrote:
January 12th, 2021, 2:15 am
He hasn't made any useful discoveries yet.
To critique useful discoveries, you must first make useful discoveries.
Each day is a hidden opportunity, a frozen waterfall that's waiting to be realised, and one that I'll probably be ignoring
bubblegum wrote:
July 2nd, 2020, 8:33 pm
conwaylife signatures are amazing[citation needed]
part-time stator reducer

User avatar
JP21
Posts: 1297
Joined: October 26th, 2019, 5:39 am
Location: PH

Re: Thread for basic questions

Post by JP21 » January 12th, 2021, 2:18 am

What does "Donald trump" with his 3 accounts have to do with ColorfulGalaxy?

bubblegum
Posts: 735
Joined: August 25th, 2019, 11:59 pm
Location: click here to do nothing

Re: Thread for basic questions

Post by bubblegum » January 12th, 2021, 2:28 am

JP21 wrote:
January 12th, 2021, 2:18 am
What does "Donald trump" with his 3 accounts have to do with ColorfulGalaxy?
One of them's been shooting at the other ever since Trump#1 joined. Also Colo{u}rfulGalaxy's Chinese.
Each day is a hidden opportunity, a frozen waterfall that's waiting to be realised, and one that I'll probably be ignoring
bubblegum wrote:
July 2nd, 2020, 8:33 pm
conwaylife signatures are amazing[citation needed]
part-time stator reducer

User avatar
yujh
Posts: 1852
Joined: February 27th, 2020, 11:23 pm
Location: CHINA

Re: Thread for basic questions

Post by yujh » January 12th, 2021, 5:38 am

bubblegum wrote:
January 12th, 2021, 2:28 am
JP21 wrote:
January 12th, 2021, 2:18 am
What does "Donald trump" with his 3 accounts have to do with ColorfulGalaxy?
One of them's been shooting at the other ever since Trump#1 joined. Also Colo{u}rfulGalaxy's Chinese.
I would say at least one of the Donald trumps is Chinese, or even another account of cg.(off-topic!)

Schiaparelliorbust
Posts: 2270
Joined: July 22nd, 2020, 9:50 am
Location: Acidalia Planitia

Re: Thread for basic questions

Post by Schiaparelliorbust » January 14th, 2021, 6:15 am

Is the glider synthesizability of any given pattern computable?
Hunting's language (though he doesn't want me to call it that)
Board And Card Games
Colorised CA
Alien Biosphere

User avatar
dvgrn
Moderator
Posts: 7580
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » January 14th, 2021, 7:55 am

Schiaparelliorbust wrote:
January 14th, 2021, 6:15 am
Is the glider synthesizability of any given pattern computable?
Technically, by the classic definition of "computable function", an algorithm is allowed to run forever if no such glider synthesis exists. So I think glider synthesizability _is_ computable -- there's a program that will return a glider synthesis for an input pattern in a finite number of steps, if a glider synthesis exists.

It's not a sane or usable algorithm; at least the one I'm thinking of isn't. To get let's say a seven-glider recipe for a loafer (if one exists) in a reasonable time, you'd probably have to pack the entire solar system with computronium.

Example algorithm (EDIT: I mean, "procedure" -- see next post):
  • Start with an NxN bounding box -- 10x10, let's say.
  • Enumerate all patterns that consist of gliders inside that bounding box.
  • Run each pattern, checking each generation to see if it matches your target pattern.
  • Also test each generation to see if it stabilizes (matches a previous generation). If so, discard that pattern and continue the enumeration.
  • If any cells leave the bounding box, discard and continue.
  • If the target pattern is matched, rewind all gliders in the starting configuration for 4N ticks, re-run, and see if you still get the target pattern. If not, discard and continue. (EDIT: fixed this -- used to say "until outside bounding box", whch is not always far enough.)
  • When all glider-only patterns at NxN have been tested, increase N by 1 and restart the enumeration.
We could actually complete a cycle of this algorithm at 10x10 with current computing resources, I suppose, but it probably wouldn't find anything we were interested in. By the time we hit 20x20 we might need more computers than we currently have on Earth -- just guessing about that, though, haven't done any decent estimates.

mniemiec
Posts: 1222
Joined: June 1st, 2013, 12:00 am

Re: Thread for basic questions

Post by mniemiec » January 14th, 2021, 7:27 pm

Schiaparelliorbust wrote:
January 14th, 2021, 6:15 am
Is the glider synthesizability of any given pattern computable?
dvgrn wrote:
January 14th, 2021, 7:55 am
Technically, by the classic definition of "computable function", an algorithm is allowed to run forever if no such glider synthesis exists. So I think glider synthesizability _is_ computable -- there's a program that will return a glider synthesis for an input pattern in a finite number of steps, if a glider synthesis exists.
Technically, a "procedure" (or "function") is a series of steps that may or may not terminate, and an "algorithm" is a procedure that is guaranteed to terminate in a finite amount of time. Determining whether or not every particular procedure does, in, fact, terminate is one of the known problems that is not computable by certain well-known computing models (e.g. Turing machines), and since these can both emulate and be emulated by Life, Life cannot determine this either; it's only computible in certain edge cases (and those tend to be the minority).

One may consider a more restrictive problem: i.e. are all finite still-lifes constructible? One way to prove that this is possible is to construct an algorithm that essentially 2D-prints still-lifes, one row at a time, where everything above a certain key point, and everything on the same row and to the left, are part of the desired still-life. The key point and everything below it and to the right on the same row are mutable scaffolding.

All one needs to do is to develop a grammar for a small finite set of scaffolding that can be used to support any combination of cells above it, plus a series of converters that can mold scaffolding locally to flip the key cell (if it differs from its desired state), moving the location of the key cell one cell to the right. If this can be done for every local arrangement of scaffolding, one would have an induction proof that all still-lifes are glider-constructible. Unfortunately, constructing all possible scaffolding pieces, plus all necessary converters, would be a daunting task, and nobody has attempted it (since I first postulated this hand-waving argument in 1998).

One could similarly extend this idea to oscillators of period n, for any n, but the kinds of scaffolding required would be much more complicated, as would be the necessary converters. Various search engines we have currently available are good at finding stators (which are essentially the scaffolding necessary to hold rotors in place), but finding converters that could convert every stator (from a necessary and sufficient subset) to every other would be quite a feat of engineering.

If this could be done for a few small values of n (e.g. 2-4), one might more clearly how it might be generalized to all n.


The NxN bounding box algorithm has a problem that (in your example), N is finite and small. E.g. due to long-running patterns (e.g. methuselahs), there are many patterns buildable from n gliders that can be non-trivially and usefully be perturbed by a glider arriving very late, so your choice if N would have to be quite large, and it would have to grow with every n.

One way to do this robustly is to start with n=2, and compute all possible collisions of 2 gliders, without limit, and determine how long it takes for them all to reach a stable result, say g generations, plus how far away (G) from the center the result (excluding spaceships) extends. You are thus guaranteed that all non-trivial results from will fit in an 2N[n]+1 square box, where N[n]=ceil(g/4+G), and that adding an extra glider anywhere in a slightly larger box that is 5 cells larger on each side is guaranteed to find all possible collisions of n+1 gliders (excluding ash that emits spaceships).

This doesn't deal with escaping spaceships, but one could special-case those. I.e. We already know which 2-glider collisions emit gliders, and given N[2], we can determine how far away an incoming glider can come in to an ash cloud to guarantee that if it hits an escaping glider, its own ash won't affect the other ash non-trivially. So, we can just add N[2] to N[n].

It gets a bit more complicated if the ash emits spaceships other than gliders, or pairs of spaceships, but again, one glider can be collided with each of these to see the size of the maximum non-trivial resulting ash, and add that to N[n] rather than N[2].

Unless, of course, the ash from one of the above secondary collisions shoots a glider back at the original ash, at which point my brain is starting to melt, so I'll allow others to plug this particular hole.

It's doable, but it's not trivial.

User avatar
dvgrn
Moderator
Posts: 7580
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » January 14th, 2021, 9:50 pm

mniemiec wrote:
January 14th, 2021, 7:27 pm
dvgrn wrote:
January 14th, 2021, 7:55 am
... by the classic definition of "computable function"...
Technically, a "procedure" (or "function") is a series of steps that may or may not terminate, and an "algorithm" is a procedure that is guaranteed to terminate in a finite amount of time.
I figured I would mess up some of the terminology somewhere. The article I linked to called the defining computable-function procedure an "algorithm", and then went on to say that it was okay if it didn't terminate. But the Wikipedia algorithm article does say that

"The informal definitions of algorithms generally require that the algorithm always terminates."
mniemiec wrote:
January 14th, 2021, 7:27 pm
The NxN bounding box algorithm has a problem that (in your example), N is finite and small. E.g. due to long-running patterns (e.g. methuselahs), there are many patterns buildable from n gliders that can be non-trivially and usefully be perturbed by a glider arriving very late, so your choice [of] N would have to be quite large, and it would have to grow with every n.

One way to do this robustly is to start with n=2, and compute all possible collisions of 2 gliders, without limit...

It's doable, but it's not trivial.
Looking at it again, I still think it's not very easy to shoot any holes in my candidate computable function.

I didn't mention a value for n (number of gliders) at all, only for N (bounding box edge). The enumeration will simply pack gliders into the NxN bounding box in all possible ways, until it runs out of options... and then go on to the next larger bounding box. The check for rewindability is a separate step, guaranteed to terminate, so not a problem for computability.

Every glider synthesis fits in some NxN box -- including any temporary sparks and other reactions involved in the synthesis. So this algorithm will eventually find a synthesis where the entire reaction fits in the smallest possible bounding box -- if a synthesis exists at all. If it doesn't exist, the definition of "computable function" allows the procedure to run forever and not find anything.

It all adds up to a spectacularly inefficient way to find a glider synthesis of, e.g., Sir Robin -- but it's still computable!

It Sure Ain't Optimal...
As written, the procedure almost certainly wouldn't find the recipe with the smallest number of gliders that fits inside that NxN bounding box. A few more lines could be added to the algorithm to finish the enumeration at that NxN level and pick the option with the fewest gliders.

There's still absolutely no guarantee that the recipe found by this revised procedure has the minimum number of gliders, out of all possible syntheses of the target object. That kind of minimization wasn't part of the original question, and as you say it's a lot harder to deal with in a computable way -- so my intention was to dodge that whole question completely.

User avatar
toroidalet
Posts: 1212
Joined: August 7th, 2016, 1:48 pm
Location: My computer
Contact:

Re: Thread for basic questions

Post by toroidalet » January 14th, 2021, 10:56 pm

A more "efficient" (or at least simpler) algorithm/procedure/method/whatever involves enumerating all single-channel recipes by binarily counting, except that you carry a 1 whenever another one is 13 digits or less behind it, with 1's representing gliders. (one digit to the left is 1 digit further away from the initial target).
Creationism is an insult to God. He would have done a much better job.

MathAndCode
Posts: 2763
Joined: August 31st, 2020, 5:58 pm

Re: Thread for basic questions

Post by MathAndCode » January 15th, 2021, 1:19 am

dvgrn wrote:
January 14th, 2021, 7:55 am
  • Also test each generation to see if it stabilizes (matches a previous generation). If so, discard that pattern and continue the enumeration.
Simply checking whether a pattern matches a previous generation would keep delivering false negatives if the final pattern has two spaceships with different velocities or both a spaceship and a still-life or oscillator. Rakes and patterns emitting sparks (including constructed "sparks") in weird directions complicate any effort to get around this.
dvgrn wrote:
January 14th, 2021, 7:55 am
  • If the target pattern is matched, rewind all gliders in the starting configuration until they're outside the bounding box, re-run, and see if you still get the target pattern. If not, discard and continue.
Simply rewinding the gliders to outside the N×N bounding box isn't always sufficient. Here's an example:

Code: Select all

x = 37, y = 34, rule = LifeHistory
4.A12.A.A12.A$5.A9.2A3.2A9.A$3.3A10.2A.2A10.3A$3.4BD6BD7BD6BD4B$3.5BD
3B2D9B2D3BD5B$3.3B3D4B2D7B2D4B3D3B$3.31B$3.31B$3.3D25B3D$3.2BD25BD2B$
3.BD27BDB$3A31B3A$2.A31BA$.A.31B.A$3.31B$3.31B$3.31B$3.31B$3.31B$3.
31B$3.31B$3.31B$3.31B$3.31B$3.31B$3.31B$3.31B$3.31B$3.31B$3.31B$3.31B
$3.31B$3.31B$3.31B!
I think that a 2N×2N bounding box would be sufficient, though, and it may to possible to reduce that slightly.

Also, I think that I once read that a general algorithm that could determine whether a particular pattern would ever evolve from another particular pattern in Conway's Game of Life would imply the existence of a general algorithm capable of solving the halting problem. (This makes sense, as one could simply create a Turing machine in Conway's Game of Life and program it to self-destruct, leaving a complete vacuum, if and only if it halts.)
I have reduced the cost of universal construction to seventeen gliders and probably to sixteen. All that remains is for the universal operations to be found.

User avatar
wwei23
Posts: 2451
Joined: May 22nd, 2017, 6:14 pm
Location: The (Life?) Universe

Re: Thread for basic questions

Post by wwei23 » January 15th, 2021, 1:41 am

MathAndCode wrote:
January 15th, 2021, 1:19 am
dvgrn wrote:
January 14th, 2021, 7:55 am
  • Also test each generation to see if it stabilizes (matches a previous generation). If so, discard that pattern and continue the enumeration.
Simply checking whether a pattern matches a previous generation would keep delivering false negatives if the final pattern has two spaceships with different velocities or both a spaceship and a still-life or oscillator. Rakes and patterns emitting sparks (including constructed "sparks") in weird directions complicate any effort to get around this.
Solution: Run it through apgsearch.
@Hunting so we're making a referential signature chain?
Stop being mean to MathAndCode!
LeapLife has fun drifters!

mniemiec
Posts: 1222
Joined: June 1st, 2013, 12:00 am

Re: Thread for basic questions

Post by mniemiec » January 15th, 2021, 2:41 am

MathAndCode wrote:
January 15th, 2021, 1:19 am
Simply checking whether a pattern matches a previous generation would keep delivering false negatives if the final pattern has two spaceships with different velocities or both a spaceship and a still-life or oscillator. Rakes and patterns emitting sparks (including constructed "sparks") in weird directions complicate any effort to get around this.
I don't know if he was the first to do so, but I remember that back in the '70s, Peter Raynham suggested a method of determining if any pattern became periodic with any period, by just running two copies of it, one a step at a time, and one two steps at a time. If the two were ever identical, say at generation n, it meant that the result was periodic with a period of n, or possibly some factor of n.

This doesn't account for spaceships, but if one computes generation 2n ^ generation n, one will at some point get a field that is empty except for shadow signatures of escaping spaceships, and those are easy to scan for. The only time this doesn't occur is if one has a pattern that exhibits infinite growth.

User avatar
dvgrn
Moderator
Posts: 7580
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » January 15th, 2021, 8:08 am

MathAndCode wrote:
January 15th, 2021, 1:19 am
dvgrn wrote:
January 14th, 2021, 7:55 am
  • Also test each generation to see if it stabilizes (matches a previous generation). If so, discard that pattern and continue the enumeration.
Simply checking whether a pattern matches a previous generation would keep delivering false negatives if the final pattern has two spaceships with different velocities or both a spaceship and a still-life or oscillator. Rakes and patterns emitting sparks (including constructed "sparks") in weird directions complicate any effort to get around this.
This actually isn't a problem, as far as I can see. The goal of this procedure is to find a glider synthesis for Pattern P, if one exists. If Pattern P consists of multiple different velocity spaceships / spaceship plus still life / sparky rake / whatever, then any problems are taken care of by the rules before and after the one you quoted:
Run each pattern, checking each generation to see if it matches your target pattern.
...
If any cells leave the bounding box, discard and continue.
The procedure will stop if it sees an exact match with the target pattern -- which is really the only goal here.

Rakes and spaceships will leave the NxN bounding box in a finite number of steps, so there's no way that the procedure can keep delivering false negatives.

Sure, in some of these cases the procedure might enumerate, for example, a perfectly valid synthesis of Pattern P except that there's a spark that extends momentarily one cell outside the NxN box. Not to worry -- the procedure will find that synthesis with no problem when it's enumerating the next larger sized bounding box. (!)
MathAndCode wrote:
January 15th, 2021, 1:19 am
dvgrn wrote:
January 14th, 2021, 7:55 am
  • If the target pattern is matched, rewind all gliders in the starting configuration until they're outside the bounding box, re-run, and see if you still get the target pattern. If not, discard and continue.
Simply rewinding the gliders to outside the N×N bounding box isn't always sufficient...
Good point. I've amended my procedure in the post above... not that anyone is ever actually going to _use_ this procedure for anything. Computability is a very strange game sometimes.

MathAndCode
Posts: 2763
Joined: August 31st, 2020, 5:58 pm

Re: Thread for basic questions

Post by MathAndCode » January 15th, 2021, 10:00 am

dvgrn wrote:
January 15th, 2021, 8:08 am
Run each pattern, checking each generation to see if it matches your target pattern.
...
If any cells leave the bounding box, discard and continue.
The procedure will stop if it sees an exact match with the target pattern -- which is really the only goal here.

Rakes and spaceships will leave the NxN bounding box in a finite number of steps, so there's no way that the procedure can keep delivering false negatives.

Sure, in some of these cases the procedure might enumerate, for example, a perfectly valid synthesis of Pattern P except that there's a spark that extends momentarily one cell outside the NxN box. Not to worry -- the procedure will find that synthesis with no problem when it's enumerating the next larger sized bounding box. (!)
Ah; I forgot about that part. Thank you for reminding me of it.
I have reduced the cost of universal construction to seventeen gliders and probably to sixteen. All that remains is for the universal operations to be found.

User avatar
C28
Posts: 28
Joined: December 8th, 2020, 12:23 pm
Location: 1/0

Re: Thread for basic questions

Post by C28 » January 18th, 2021, 3:40 pm

how small can a spaceship predecessor get population-wise? and is it affected by the population of said spaceship?
25P3H1V0.2 is my favorite c/3

User avatar
dvgrn
Moderator
Posts: 7580
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

Re: Thread for basic questions

Post by dvgrn » January 18th, 2021, 4:06 pm

C28 wrote:
January 18th, 2021, 3:40 pm
how small can a spaceship predecessor get population-wise? and is it affected by the population of said spaceship?
I can't think of a good general answer to this question. It's hugely dependent not only on the population of the spaceship, but also on its structure.

For example, predecessors can easily be found for Corderships that are less than half the population of the full Cordership. Here's 41 cells vs. a 2EC's minimum population of 100, and no doubt it's easy to cut that down some more:

Code: Select all

x = 35, y = 38, rule = B3/S23
18bo$17bo$10bo6b3o$9bobo13b2o$10b2o13bo3$10bo$9bobo$10b2o2$33b2o$33bo
5$15b2o$15bo$3b3o$4bo$4bo2bo$4bo2bo$5bobo5$11bo$11b2o$12bo6$2o$o!
This is possible because Corderships are mostly generated by their engines -- behind the leading switch engines, really the back parts of the spaceship have only two tasks: mutually annihilate, and don't get in the way.

For most other spaceships, at least ones that aren't based on switch engines or rakes or self-constructing circuitry, it's often very difficult to find a predecessor that's smaller in either population or bounding box than the full spaceship. Most of the cells in most spaceships have to be where they are for the spaceship to work, with maybe a few sparks at the edges being the exception that proves the rule.

In those cases, the information stored in the specific arrangement of cells is usually not very compressible. You can often get rid of a small percentage of the ON cells with a predecessor search, but you hit a wall pretty quick -- you can't just keep backtracking and reducing the population, for obvious reasons.

MathAndCode
Posts: 2763
Joined: August 31st, 2020, 5:58 pm

Re: Thread for basic questions

Post by MathAndCode » January 18th, 2021, 4:43 pm

dvgrn wrote:
January 18th, 2021, 4:06 pm
For example, predecessors can easily be found for Corderships that are less than half the population of the full Cordership. Here's 41 cells vs. a 2EC's minimum population of 100, and no doubt it's easy to cut that down some more:
I reduced the population to 35.

Code: Select all

x = 35, y = 38, rule = B3/S23
18bo$18bobo$10bo7b2o$9bobo13b2o$10b2o13bo3$10bo$9bobo$10b2o2$33b2o$33b
o6$4bo$3bobo2$3bo2bo$5b2o$6bo3$13b2o$13bo9$2o$bo!
Also, I'd like to point out that technically, any constructible spaceship can be built by a RCT-based universal constructor. The seventeen-glider version reaches a minimum population of 64 cells, which probably can be reduced a little more by replacing some stabilizing gliders with preblocks or blinkers, and I have been intermittently working on a sixteen-glider version.



Edit: Here's a 32-cell predecessor:

Code: Select all

x = 39, y = 35, rule = B3/S23
29bo$29b2o2$12bobo$11bo$12bo2bo$14b3o2$37bo$10bo26b2o$10bobo$10b2o$bo
$obo$b2o3$bo$obo$b2o14$4b2o$4bo!
I have reduced the cost of universal construction to seventeen gliders and probably to sixteen. All that remains is for the universal operations to be found.

User avatar
C28
Posts: 28
Joined: December 8th, 2020, 12:23 pm
Location: 1/0

Re: Thread for basic questions

Post by C28 » January 18th, 2021, 5:01 pm

MathAndCode wrote:
January 18th, 2021, 4:43 pm
dvgrn wrote:
January 18th, 2021, 4:06 pm
For example, predecessors can easily be found for Corderships that are less than half the population of the full Cordership. Here's 41 cells vs. a 2EC's minimum population of 100, and no doubt it's easy to cut that down some more:
I reduced the population to 35.

Code: Select all

x = 35, y = 38, rule = B3/S23
18bo$18bobo$10bo7b2o$9bobo13b2o$10b2o13bo3$10bo$9bobo$10b2o2$33b2o$33b
o6$4bo$3bobo2$3bo2bo$5b2o$6bo3$13b2o$13bo9$2o$bo!
Also, I'd like to point out that technically, any constructible spaceship can be built by a RCT-based universal constructor. The seventeen-glider version reaches a minimum population of 64 cells, which probably can be reduced a little more by replacing some stabilizing gliders with preblocks or blinkers, and I have been intermittently working on a sixteen-glider version.



Edit: Here's a 32-cell predecessor:

Code: Select all

x = 39, y = 35, rule = B3/S23
29bo$29b2o2$12bobo$11bo$12bo2bo$14b3o2$37bo$10bo26b2o$10bobo$10b2o$bo
$obo$b2o3$bo$obo$b2o14$4b2o$4bo!
dvgrn wrote:
January 18th, 2021, 4:06 pm
C28 wrote:
January 18th, 2021, 3:40 pm
how small can a spaceship predecessor get population-wise? and is it affected by the population of said spaceship?
I can't think of a good general answer to this question. It's hugely dependent not only on the population of the spaceship, but also on its structure.

For example, predecessors can easily be found for Corderships that are less than half the population of the full Cordership. Here's 41 cells vs. a 2EC's minimum population of 100, and no doubt it's easy to cut that down some more:

Code: Select all

x = 35, y = 38, rule = B3/S23
18bo$17bo$10bo6b3o$9bobo13b2o$10b2o13bo3$10bo$9bobo$10b2o2$33b2o$33bo
5$15b2o$15bo$3b3o$4bo$4bo2bo$4bo2bo$5bobo5$11bo$11b2o$12bo6$2o$o!
This is possible because Corderships are mostly generated by their engines -- behind the leading switch engines, really the back parts of the spaceship have only two tasks: mutually annihilate, and don't get in the way.

For most other spaceships, at least ones that aren't based on switch engines or rakes or self-constructing circuitry, it's often very difficult to find a predecessor that's smaller in either population or bounding box than the full spaceship. Most of the cells in most spaceships have to be where they are for the spaceship to work, with maybe a few sparks at the edges being the exception that proves the rule.

In those cases, the information stored in the specific arrangement of cells is usually not very compressible. You can often get rid of a small percentage of the ON cells with a predecessor search, but you hit a wall pretty quick -- you can't just keep backtracking and reducing the population, for obvious reasons.
thanks for answering my question. i asked it because i found this 9-cell predecessor of a LWSS and wondered if that was the smallest LWSS predecessor.

Code: Select all

x = 6, y = 4, rule = B3/S23
3bobo$o4bo$ob2obo$2bo!
25P3H1V0.2 is my favorite c/3

MathAndCode
Posts: 2763
Joined: August 31st, 2020, 5:58 pm

Re: Thread for basic questions

Post by MathAndCode » January 18th, 2021, 5:05 pm

C28 wrote:
January 18th, 2021, 5:01 pm
thanks for answering my question. i asked it because i found this 9-cell predecessor of a LWSS and wondered if that was the smallest LWSS predecessor.

Code: Select all

x = 6, y = 4, rule = B3/S23
3bobo$o4bo$ob2obo$2bo!
Here are two eight-cell predecessors:

Code: Select all

x = 8, y = 15, rule = B3/S23
2bo$bo$bo3bo$b4o8$3b4o$2bo4bo$bo$o!
There are several threads made for cataloguing small predecessors of various objects. I used to be working on one, but I stopped because no one else seemed to be using it.
I have reduced the cost of universal construction to seventeen gliders and probably to sixteen. All that remains is for the universal operations to be found.

Post Reply