simsim314 wrote:This one has no historical or other value, no extreme novelty in the construction and nothing that was too impressive
No, what Alexey
et al have done is
very impressive, has historical value (rediscovering and deepening concepts discussed by Gabriel Nivasch and Dean Hickerson in 2006) and is extremely novel. It is quite a deep concept and deserves to be explained clearly and pedagogically. I shall attempt to do so in the remainder of this post, after first addressing a slight attribution issue:
Alexey Nigin wrote:Well, in my humble opinion, this is the first constructive proof that Life supports infinitely many asymptotic growth rates.
No, Gabriel Nivasch did that in 2006. He constructed patterns with growth rate O(t^(1/2^n)) for all n. His idea (which he named the
quadratic filter) was similar to (but simpler than) yours, and will make an excellent illustrative example. So, without further ado, allow me to begin:
How slow can you grow?
Let's consider patterns which emit gliders very slowly. One familiar example is the caber tosser, which emits the nth glider at generation f(n) = Θ(2^n). Another is Dean Hickerson's sqrtgun, which emits the nth glider at generation f(n) = Θ(n^2). The most trivial example is an ordinary glider gun, with f(n) = Θ(n). We'll call this function the
slowness rate, which we will denote by S.
Notation note: The big theta Θ means 'is asymptotically proportional to'.
For instance, we could write:
- S(caber tosser) = f, where f(n) := Θ(2^n)
Notation note: The symbol := means 'is defined to be'.
Now this is quite verbose and annoying, and is easier to encapsulate in a single expression. The following two are alternative ways to express this:
- S(caber_tosser)(n) = Θ(2^n)
- S(caber_tosser) = λn.Θ(2^n)
The first of these is what we get by doing a literal replacement of f by its definition. The second is a way to 'rearrange the equation' to express S(caber_tosser), using
lambda notation.
Notation note: λx.y means 'the function mapping x to y'.
S is a higher-order operator mapping patterns to growth rates. There's also something that we can do to certain patterns, called
piping by analogy with Unix. This simply sends the output of the thing on the left to the input of the thing on the right. Gabriel designed a 'quadratic filter' which can be piped onto the end of a pattern to create a slower growth rate. Specifically, it has the following property:
- S(X | quadratic_filter) = S(X)^2
And here's an example constructed by Gabriel:
- S(sqrt_gun | quadratic_filter) = S(sqrt_gun)^2 = λn.Θ(n^2)^2 = λn.Θ(n^4).
For explicitness, you may want the actual RLE of the pattern, a working sqrtsqrtgun:
Code: Select all
x = 640, y = 464, rule = B3/S23
116b2o21b2o$115bobo21bo$114bo13bobo6bobo$102bo11bo2bo6b2o2bo2bo5b2o$
99b4o11bo8bobo5b2o$90bo7b4o13bobo3bo3bo3bo3b2o$89bobo6bo2bo14b2o2b2ob
3o5b2o$88bo3b2o4b4o21b2o3bo2bo25b2o$77b2o9bo3b2o5b4o25bobo26b2o$77b2o
9bo3b2o8bo$89bobo$90bo23bo$99bobo12bobo$100b2o12b2o$100bo$117b2o$108b
2o7b2o$108bo$105b2o3bo7bo$104b2ob2obo6bobo$106bob2o6bo2bo$115bo2bo2$
91bo23bo2bo$90b4o23b2o$89b2ob4o5b2o$78b2o8b3ob2o3bo3bo2bo$78b2o9b2ob2o
3bo7bo8bobo$90b5o3bo6bo9b2o$91bo3b3o7bo9bo$101bo2bo5b2o$101b2o7bobo$
112bo$60b2o27bo22b2o$60b2o25b2o$88b2o2$63bo$62bo$46b2o14bo$46b2o$80bob
o$47bo10b2o3b2o15b2o$46bobo12bo19bo$46bobo9bo5bo36b2o$47bo11b2ob2o36b
2o$60bobo39bo$61bo$44b2obob2o10bo$26b2o16bo5bo367bo$26b2o17bo3bo367bob
o$46b3o368bobo$418bo$64b2o$413b2o7b2o$64bo2bo344bo2bo5bo2bo$58b3o352b
2o7b2o$57bo3bo4b2o76bobo241b3o$45bo10bo5bo82b2o241b3o27bo$44bo11b2obob
2o82bo243bo27bobo$44b3o342bo27bobo$24b5o360bo28bo$23bob3obo29bo328bobo
$24bo3bo29bobo100bo$25b3o30bobo98b3o$26bo20b5o7bo98bo229bobo$37bo8bob
3obo106bo229bo$37bobo7bo3bo7b2o95bo2bo229bo$37b2o9b3o8b2o94bo233bo$24b
o17b2o5bo105bobo218bo11b3o$8b2o14bo17b2o112bo218b3o10b3o$8b2o13bobo5bo
10b2o7b2o$22b2ob2o2bobo11bo7bo$21bo5bo2b2o10bobo7b3o19b2o77b2o3b2o215b
3o$6bo17bo16b2obo9bo19bo78bobobobo$7bo13b2o3b2o26bobo5bo9bobo79b5o216b
obo$7bo47b2o4bobo8b2o12bo68b3o217bobo$42b2o16bob2o23b2o67bo$23bo18b2o
15b2ob2o22b2o287b3o$5b2o3b2o11bo36bob2o$8bo13bo38bobo$5bo5bo50bo69b2o
241b3o$6b2ob2o23b2o95b3o237bo4bo$7bobo14b2o8b2o92bob2o238bobo$8bo15b2o
95b2o5bo2bo24b2o200b2o9bo3b2o6b2o$8bo112b2o5bob2o24b2o200b2o9bo3b2o5bo
bo$35bo95b3o6b2o227bo3b2o7bo10bo$34bobo95b2o6bobo227bobo19b3o$33bo3bo
104bo228bo19b2obo$33b5o8bo95b2o232b2o13b3o$32b2o3b2o7b2o327bobo14b2o$
10bobo20b5o7bobo20b3o282b3o21bo48b2o$11b2o21b3o33bo283bo71bo$5b3o3bo
23bo33bo284bo61b2o6bobo$4bo3bo344b3o59bobo5b3o$3bo5bo395b2o7bo6b3o$3b
2obob2o75b2o266b3o49b2o7bo2bo2bo2bo$72b2o10b2o267b3o58bo6b2o$18bo52bob
o12bo328bobo$19b2o52bo279b3o60b2o$16b2obo334bo$32b2o27bo292bo$18b2o13b
o25bobo291b3o$2b2o14bo11b3o15b2o10b2o287bo$30bo17b2o298bobo$336b2o10b
2obo7bo$116bo219b2o10b2ob2o6b2o$117b2o229b2obo6bobo$10b2o99bo4b2o230bo
bo$9bobo8b4o51b2o34b3o235bo$2o3b2o4bo3b2o7bo50b3o36bo217bo$2b3o10b2o2b
2o3bo52b2obo32b2o217bo$bo3bo13b2o2bo53bo2bo250b3o19b3o$2bobo72b2obo
274bo$3bo63b2o6b3o6b2o268bo$66bobo6b2o7bobo244b3o34bo$4b3o8bo10b2o38bo
19bo245bo35b2o$4b3o8b3o4b2o2b2o2b2o4b2o22b2o3b2o19b2o27b3o214bo34bobo$
18bo3b2o2bo2bobo3bobo22bobo51bo3bo213bo$17b2o9b3o6bo22bo52bo5bo212bo$
28b2o44b2o37b2obob2o20bo190b3o$2b2o3b2o31bobo27b2o2b2o2b2o58b3o$3b5o
33b2o27bobo2bo2b2o57bo$4b3o34bo29b3o9b2o8bo22bo21bo192b3o$5bo46bo19b2o
9b2o8b3o19bobo17bo2bo187bo5bo$19b3o28bobo43bo18bobo16bo191bobo3bo80b2o
$18bo3bo4b2o19b2o45b2o19b3o15bobo177b2o11bobo83b2o$17bo5bo3b2o19b2o12b
2o48b2o4b2o15bo178b2o11bo2bo5b3o$17b2obob2o24b2o12b2o47bobo4bo208bobo
8bo$43b2o5bobo60bo5b3o204bobo8bo$30b3o9bobo7bo68bo10b2o3b2o187bo$23bo
6bo11bo89bobobobo254bo$5b2o15b2o7bo9b2o32b2o56b5o171b3o80b3o$5b2o68bob
o5b3o48b3o255bob2o9bo8bo$21bob2o50bo6bo3bo48bo172bo3bo18b2o60b3o2bo5b
2o7b3o$20bo2b2o56bo5bo8b5o207bo3bo17bobo60b2o3b3o3bobo5b5o$20b4o57bo5b
o7bob3obo230bo68bo9bobobobo$38b2o32b2o22bo3bo18bo189b3o88b2o9b2o3b2o$
38bobo20b2o8bobo7bo15b3o18bo226b2o$19b2o3b2o12bo22bo11bo7b2o15bo19b3o
225b2o$22bo26bo9bobo19b2o226b3o33bo65b2o$19bo5bo21b4o8b2o19b2o2bo50b2o
274b2o$20b2ob2o12bobo6bobob2o29bobo11b2o38b2o171bo3bo97bo$21bobo13bo3b
o3bo2bob3o29b2o12bo211bo3bo97b3o$22bo18bo4bobob2o41b3o289b2o13b2o3b2o
7bo$22bo4b2o8bo4bo4b4o13b3o26bo209bo5b3o73b2o14b5o4b5o$27b2o12bo7bo16b
o12b2o3b2o217bobo87bo7b2ob2o6b2o$37bo3bo23bo13b2o3b2o206b2o12b2o84b3o
6b2ob2o$37bobo62bo189b2o12b2o6b2o69bo5b2obo7b3o$51b2o28b3o18bobo39bo
161b2o7b2o67b3o4b3o15b2o3b2o$22b2o27b2o4bo23b3o19bobo36b3o158bobo8bo
68bo3bo4b2o16b5o$22b2o16b2o6b2o6b5ob2o18bo7b2o11bo2bo34bo145bo15bo81bo
24b2ob2o$40b2o5b3o5bo2b2o4bo25b2o11bobo35b2o144b3o92bo5bo21b2ob2o$48b
2o5b2o8bo36bobo4b2o179bo91bo5bo22b3o6b2o$51b2o4bo7bo8b2o26bo6bobo177b
2o92bo3bo32b2o$51b2o12bo8b2o35bo272b3o12bo$64bo46b2o148bo137bobo3bo$
62b2o17b2o176bobo46b3o78b2o8b2o3b3o$81b2o167bo7bobo49bo79b2o11b5o$249b
2o6bo2bo11b2o35bo79bo12bobobobo2b2o$248b2o4b2o2bobo11b2o18bo30bo78b2o
3b2o2b2o7b3o$238b2o7b3o4b2o3bobo29b3o29b2o70b2o22b2ob2o$238b2o8b2o4b2o
5bo28b5o27bobo70bobo21b2ob2o$249b2o38b2o3b2o99bo23b5o$250bo167b2o3b2o$
262bo124bo$262b2o122b3o18b2o$108b2o142bo6b2ob2o27b3o92b3o18bo$108b2o
21b2o117bobo38b3o114b3o$123b2o6b2o110b2o4bobo6bo2bo122b2o3b2o11b3o5bo
8b2o$124b2o117b2o3bo2bo7bobo27b2o5bo87b2o3b2o11bo$123bo125bobo7bo2bo
27bo4b2o106bo9bo$250bobo7bo2bo23b3o5bobo114bobo$252bo10bo23bo99bo12bob
o8bob2o$261bo124bobo11bo2bo6b2ob2o$131bo253b2o4b2o10b2o6bob2o105b2o$
130b3o252b2o4b2o8bo3b2o5bobo104bo2bo$108bo8bo12b3o114bobo135b3o8b2o5b
2o8bo105bo$107b3o6b2o128bo2bo3b2o131bobo6bo4bo2bo115bo$106b5o7b2o8b2o
3b2o102b2o6b2o5b3ob2o2b2o24b2o99b2o11bobo116bobo$105b2o3b2o8bo7b2o3b2o
102b2o4b2o3bo3bo3bo3bobo14bo7bobo231bobo$106b5o7bobo124b2o5bobo8bo14bo
8bo232bo$106b5o8bo126bo2bo2b2o6bo2bo7b2o3b3o$107bo2bo17b2o117bobo13bo
7b2o27b2o$107bo3bo15bobo49bo80bobo38b2o214b2o3b2o$111bo14b2o49b3o80b2o
38bo216bo5bo$108b2obo7bo7b2o47bo$110bo7b3o6b2o47b2o151b2o187bo3bo$117b
5o8b3o125bo62bo7bo2bo186b3o$116b2o3b2o135b3o59bo3b2o7bo9bobo$107b2o3b
2o3b5o139bo58bo5bo6bo7bo3bo$107bo5bo3bo3bo138b2o59b5o7bo7bo$118bobo
208bo2bo7bo4bo8b2o$108bo3bo6bo6b2o3b2o165b2o18b2o9b2o10bo12b2o$109b3o
185bobo17b2o22bo3bo176b2o$127bo3bo164b3o20bo12bobo8bobo176bo$118b2o8b
3o164b3o34b2o189b3o$118b2o8b3o165b3o34bo191bo$288b2o7bobo5b2o$287bobo
8b2o5bobo28bo$287bo19bo27bobo$110b2o174b2o19b2o24b2o3bo$110b2o16b2o13b
2o118b3o67b2o3bo9b2o$128b2o13b2o21b2o77b2o18bo67b2o3bo9b2o$158bo7b2o
76bobo17bo70bobo$158b2o70bo12b3o4b2ob3o80bo$157bobo65bo4b4o8b3o4bo2b4o
$225bo5b4o8b3o4b2o$220b2o9bo2bo9bobo86b2o9b2o$220b2o9b4o10b2o85b2o9bob
o$230b4o8bo84bo6bo7b3o4b2ob3o$166bo63bo12bo82bobo12b3o4bo2b4o$149bobo
13b3o73b3o75b2o3b2o3bo12b3o4b2o$149bob2o11b5o150b2o3b2o3bo13bobo$141b
5o5b2obo8bobobobo154b2o3bo14b2o$140bob3obo5bo2bo7b2o3b2o69bo5b2o79bobo
$141bo3bo6bo2bo82bobo4b2o80bo$142b3o9bo83b2obo$143bo19b2o61b2o10b2ob2o
$144b2o17b2o33bo27b2o10b2obo$144bobo15bo33bobo39bobo$144bobo15b3o32b2o
40bo$145bo20bo$152b5o5b5o$151bob3obo6b2o64b2o9b2o$142b2obob2o3bo3bo73b
obo7bobo$142bo5bo4b3o65b2o2b2o6bo8bo5bo$143bo3bo6bo6b2o3b2o53b2obo2bo
2bo2bo13bobo$144b3o15b5o58b2o6bo13b2obo4b2o$162b2ob2o63bobo14b2ob2o3b
2o$162b2ob2o63b2o15b2obo$153b2o8b3o81bobo$153b2o93bo4$145b2o$145b2o16b
2o$163b2o18$295bo$293bobo$284bo7bobo$283b2o6bo2bo11b2o161b2o162bo$282b
2o4b2o2bobo11b2o159bo2bo161bobo$272b2o7b3o4b2o3bobo170bo7b5o153bobo$
272b2o8b2o4b2o5bo170bo6bo5bo153bo$283b2o181bo7b2o3bo$284bo172b3o7bo2bo
7bo149b2o7b2o$296bo159b2ob2o8b2o156bo2bo5bo2bo$297bo158b2ob2o38bo128b
2o7b2o$286bo8b3o158b5o37b4o$284bobo168b2o3b2o19b2o14b2obobo130bo$277b
2o4bobo195bo2bo11b3obo2bo2b2o124bobo$277b2o3bo2bo187b5o7bo11b2obobo3b
2o124bobo$283bobo171b2o13bo5bo6bo12b4o131bo$284bobo169b5o11bo3b2o7bo7b
o5bo$286bo169bo6b2o8bo7bo2bo9bo$293b2o163b3o3bo16b2o9b3o$293b2o165bo3b
obo9bo$458b2o5b2o8b4o$281bobo174b2o14b2ob4o5b2o$280bo2bo3b2o184b3ob2o
3bo3bo2bo$271b2o6b2o5b3ob2o2b2o178b2ob2o3bo7bo$271b2o4b2o3bo3bo3bo3bob
o156b2o3b2o15b5o3bo6bo10bo$279b2o5bobo8bo155bobobobo16bo3b3o7bo8bobo$
280bo2bo2b2o6bo2bo7b2o147b5o5bobo19bo2bo5b2o3b2o$281bobo13bo7b2o148b3o
7b2o19b2o7bobo$294bobo159bo8bo31bo$294b2o201b2o$270bo201bo$270bobo202b
o$253b2o18b2o44bo4b2o146bo14bo2bo15bob2o7bo2bo86bo2bo$251bo3bo17b2o4b
2o36bobo4b2o149bo15bo13bo3bo11bo41b4o44bo$245b2o3bo5bo16b2o4b2o37b2o
154bob3o8bo3bo10bo4b2o8bo3bo40bo3bo40bo3bo$245b2o2b2obo3bo8bo4bobo183b
2o14b4o2bo9b4o13b2o11b4o44bo41b4o$250bo5bo9bo3bo185b2o19bo24bo2bo56bo
2bo$251bo3bo5bo2b3o198bo155b8o$253b2o209b2o155bob4obo$453b2o8b2o4b2o5b
o144b8o$453b2o7b3o4b2o3bobo130b2o$261bo201b2o4b2o2bobo11b2o119b2o$261b
obo200b2o6bo2bo11b2o118bo$250b2o12b2o199bo7bobo$250b2o12b2o208bobo$
264b2o210bo125b2o$261bobo5b2o332b2o$261bo7b2o331bo3$265b2o343bo4bo$
253b2o9bobo341b2ob4ob2o$253b3o10bo343bo4bo$244b2o9b2obo11bo69bo235b2o$
244bo5bo4bo2bo10b2o70bo233bobo$249bo5b2obo9b2o4b2o62b2o5b2o230bo$245bo
3bo3b3o11b3o4b2o2b2o58b3o4b3o$247bo5b2o13b2o4b2o2b2o51bo7bo7b2obo251b
3o$269b2o17bo40bobo15bo2bo5b2o243bo3bo$270bo15bobo33b2o4bobo9b3o4b2obo
5b2o242bo5bo$287b2o33b2o3bo2bo8b2obo2b3o252b2obob2o$328bobo7bo3bo2b2o$
269b2o58bobo6bo2bo244b2o$269bo2bo58bo8b2o243bobo15bo$587bo14bobo$273bo
328bobo$336b2o265bo$271b2o63b3o241bo$270bo11b3o42b2o9b2obo238b2o21b2o$
284bo42bo5bo4bo2bo237bobo21b2o$283bo48bo5b2obo$267b2o3b2o54bo3bo3b3o7b
2o$267b2o3b2o56bo5b2o8b2o147b2o91bobo2bobo$268b5o204b2o16b2o87b2obo2bo
2bo2bob2o$269bobo205b2o109bobo2bobo2$269b3o58b2o9b2o210b3o$283bo46bobo
7bobo152b3o57bo$283b2o36b2o2b2o6bo8bo5bo136b2o8b3o56bo$282bobo36b2obo
2bo2bo2bo13bobo127bo7b2o7bo3bo83bo$325b2o6bo13b2obo126bo15bo5bo81b3o$
267b2o61bobo14b2ob2o3b2o119bobo7bo7bo3bo81b5o$268bo61b2o15b2obo4b2o
118b2ob2o5bobo7b3o81b2o3b2o$265b3o79bobo124bo5bo4bobo$265bo82bo128bo8b
o78bo$379bo94b2o3b2o84b2o$378bobo183bobo14b3o$370b2o5bo3b2o100b2obob2o
6bobo82b3o$254bo108bo5bo2bo4bo3b2o3b2o87b4o4bo5bo5bo2bo$252bobo107bobo
5b2o5bo3b2o3b2o87bo2b2o4bo3bo4bob2o$242b2o6b2o12b2o84b2o9bo3b2o11bobo
95bob2o5b3o69b2o23b2o$241bo3bo4b2o12b2o18bo15bo49b2o9bo3b2o3bo8bo116bo
61b2o22b2o$240bo5bo3b2o31b2o13bobo60bo3b2o2b2o106b2o14b2obo60bo$230b2o
8bo3bob2o4bobo28bobo5b2o4bobo17bo44bobo4bobo106bo16bo$230b2o8bo5bo7bo
36b2o3bo2bo16b2o45bo200bo2b2o4b2o2bo$241bo3bo51bobo15b2o4b2o240bo3b3o
2b3o3bo$242b2o54bobo13b3o4b2o2b2o145b2obob2o16b2o3b2o62bo2b2o4b2o2bo$
300bo4bobo7b2o4b2o2b2o51bo7bo85bo5bo9b2o6b5o$305b2o9b2o59b4o5bobo84bo
3bo10b2o6b2ob2o30b2o$306bo10bo54b2o2bo2b2o8b2o4b2o77b3o19b2ob2o29bobo$
247b2o11b2o110b2o2b2o11b2o4b2o100b3o32bo$245bo2bo12b2o106b2o10bo7b2o$
244bo7b2o6bo107b3o10bo4bobo171b3o$236b2o6bo6bo2bo45b2o8b2o35bo21b2o10b
o4bo172bo3bo$236b2o6bo7b2o46b2o8b2o4b3o28b3o13b2o7b2o184bo5bo$245bo2bo
58b2o6b5o30bo11bobo7b2o184bo5bo$247b2o57b3o5bo3bobo28b2o11bo135b2o61bo
$253bo53b2o6bo3b2o40b2o112b2o21b2o43b3o13bo3bo$253b2o55b2o41bo121b2o
68bo14b3o$241bobo8bobo55b2o41bo190bo16bo$241bo3bo106bo$231b2o12bo10b2o
$231b2o8bo4bo7bo2bo7bo41bo7bo183bo35bo25b2o$245bo7bo7b2o3bo39b4o5bobo
31b2o3b2o144bo34b2o24b2o$241bo3bo7bo6bo5bo34b2o2bo2b2o8b2o4b2o23bo5bo
142b3o33bobo$241bobo9bo7b5o35b2o2b2o11b2o4b2o$254bo2bo32b2o6b2o10bo7b
2o30bo3bo188b2o3bo2bo3b2o$256b2o32b2o5b3o10bo4bobo33b3o189b5o4b5o$298b
2o10bo4bo227b2o3bo2bo3b2o$301b2o184bo$301b2o184b3o$490bo17b3o$349b2o
138b2o19bo$350bo158bo$347b3o190bo$347bo144bo46b3o$492bo45b5o$491bobo
43b2o3b2o$490b2ob2o43b5o$489bo5bo26b2o14bo3bo$492bo30b2o14bobo$489b2o
3b2o26bo17bo$527b2o$527b2o$524b2o14b2o$512b2o9b3o14b2o$513b2o9b2o$512b
o4b2o8b2o5b2o$489b2o25bobo8b2o5bobo$490bo25bo19bo$487b3o25b2o19b2o$
487bo$397b2o$395bo3bo$394bo5bo101bo$381b2o10b2obo3bo8b2o90b2o$379bo3bo
10bo5bo8b2o90bobo$373b2o3bo5bo10bo3bo$373b2o2b2obo3bo12b2o$378bo5bo$
379bo3bo$381b2o$395b3o$395bo$396bo9bo121b2o$405bobo97b2o21b2o$393bobo
8bob2o10b2o85bo2bo$393bo2bo6b2ob2o10b2o70bo$396b2o6bob2o82b2o17bo19bo$
394bo3b2o5bobo81bobo36b3o$370bo25b2o8bo100b2o18bo3bo$370b3o13b2o5bo2bo
109bo22bo$373bo11bobo5bobo130bo5bo$372b2o11bo140bo5bo$384b2o117b2o3b2o
5b2o10bo3bo$503b2o3b2o5b2o11b3o$497b2o5b5o3bo$497bobo5bobo4b2o4bo5b2o$
374b3o122bo11bobo3b3o3b2o$499b2o4b3o8bo3bo4bo$374bobo141bo$373b5o81b2o
54bo5bo$372b2o3b2o80b2o21b2o31bo5bo$372b2o3b2o103b2o32bo3bo$508bo8b3o$
507bobo17bo$506bo3bo15b3o$507b3o16b3o$482bo22b2o3b2o$372b2o108bo41b2o
3b2o$373bo85bo7b2o12bobo40b2o3b2o$370b3o85b3o7b2o10b2ob2o$370bo86b5o5b
o11bo5bo$456b2o3b2o19bo35b2o7bo$474b2o3b2o3b2o32b2o6bobo$474b2o52b2o$
461b2o65b2o$463bo14b3o46b3o$460bo16b2obo45bobo$460bo2bo6bo6b2o29b2o16b
2o$459b2ob2o5b3o6b2o28b2o$460b2o6b5o6bobo$467b2o3b2o5bo2b2o2$458b2o3b
2o$458b2o3b2o$459b5o5b3o$460bobo6b3o$478b5o$460b3o14bob3obo$469b2o7bo
3bo$469b2o8b3o$480bo3$461b2o$461b2o16b2o$479b2o!
So by more piping, we can create extra growth rates. This prompted Dean Hickerson to say the following:
Dean Hickerson wrote:The quadratic filter is a great idea! I wish I'd thought of it.
Anyway, Gabriel Nivasch decided to create an
exponential filter, with the property that:
- S(X | exponential_filter) = 2^S(X)
By piping copies of this, you can get slowness rates of Θ(2^2^...^n), or growth rates of Θ(log log ... log(t)).
For instance, he created a growth rate of log(log(t)) by piping a caber tosser into an exponential filter:
- S(caber_tosser | exponential_filter) = 2^S(caber_tosser) = λn.Θ(2^2^n).
Code: Select all
x = 738, y = 774, rule = S23/B3
397b4o3b2o$396bo6bo2bob3o$396b5o2bo2bo$403bo2bo$404bo$386b2o17bobo$
386b2o18bo3$422bo$422bo$422bo$418bo$378b2o37bo2b3o$378b2o38bo4bo$419bo
3bo$420b3o2$412bo$411b3o7bobo$410bo2bo7bobo$370b2o39b3o7bobo$370b2o39b
3o7bobo$409bob2obo6b2o$408b3o2bo$407b2ob4o$408b3obo10b4o3b2o$408b3o11b
o6bo2bob3o$379bobo26b2o12b5o2bo2bo$379b3o47bo2bo$380b2o48bo$412b2o17bo
bo$410bob2o18bo$378bo31b4o$378bobo30bo$378b3o$377bo$377b5o3$384bo6b3o
20bobo$384bob2o3b2o20bo3bo$384bobo5b2o18bo4bo7b3o$384bob3o23bo4bo6b4o
3b2o$384b2o26bo3bo6bo4bo3b2o$413bo2bo7b2ob2o$425b4o$427bo4$424b2o$424b
2o2$405bobo$405b3o$406b2o3$404bo11b2o$404bobo9b2o$404b3o$403bo$403b5o
4$408b2o$408b2o79$495bo$494bobo$494bobo$495bo2$490b2o7b2o$489bo2bo5bo
2bo$490b2o7b2o2$495bo$494bobo$494bobo$495bo13$440b3o$440bobo$440b3o$
440b3o$440b3o$440b3o$440bobo$440b3o8$441b2o$441bobo$441bo12$439b2o$
440b2o$421bo17bo$421b3o$424bo$423b2o4$463b3o$408b3o52bo$408b3o53bo$
409bo15b3o$409bo15bo2bo$409bo15bo$408bobo14bo$426bobo2$408bobo11bo$
409bo11bobo$409bo$409bo$408b3o6bo$404bo3b3o6b2o$403b4o9bobo$391b2o9b2o
bobo$391b2o8b3obo2bo$402b2obobo$403b4o$404bo2$387bo98b2o$386b3o97bobo$
486bo2$386b3o2$386bobo$386bobo$399b3o$386b3o12bo$400bo2$386b3o$382bo4b
o$381bobo10b2o$369b2o9bo3b2o9b2o$369b2o9bo3b2o8bo$380bo3b2o$381bobo24b
3o$382bo27bo$409bo2$364b3o$365bo142b3o$365bo142bo$364b3o142bo$186bo
238b3o$186b2o176b3o57bo2bo$185bobo176b3o60bo$377b2o48bo$364b3o11b2o44b
obo$365bo11bo$365bo$364b3o$360bo$359bobo$347b2o10b2obo9bo$347b2o10b2ob
2o8b2o$359b2obo8bobo$359bobo223b2o$127b2o231bo25b2o197bo2bo$127b2o214b
o41bobo183bobo15bo$343bo43bo181bo3bo2b3o10bo$342b3o224bo19bo$127bo434b
2o4bo4bo7b2o2bo2bo5b2o$126b3o402b2o29b2o5bo7bobo2bo2b2o7bobo$125bo3bo
212b3o186bobo35bo3bo5b3o14bo$127bo215bo187bo39bobo22b2o$124bo5bo212bo$
124bo5bo212bo$125bo3bo213bo11b2o219b2o7bo$126b3o213b3o9bobo211bo7bo2bo
5bo$356bo210bo3b2o7bo2bobo$567bo5bo6bo2bo$342b3o223b5o7bo3bo$337bo5bo
232bo2bo$129bo207bobo3bo232b2o$325b2o11bobo$325b2o11bo2bo254bo$129bo
208bobo8b2o243bobo$127bobo207bobo10b2o217b2o24b2o$128b2o190bo16bo11bo
217bo3bo5bo2b3o$320b3o238b2o3bo5bo9bo3bo$323bo39b3o195b2o2b2obo3bo8bo
4bobo$322b2o41bo200bo5bo16b2o$122b2o3b2o235bo202bo3bo17b2o4b2o$136bo
156bo275b2o18b2o4b2o$123bo3bo9bo154bobo291bobo$124b3o8b3o144b2o7bob2o
258b3o30bo$124b3o154bobo6b2ob2o10b2o246bo$280bo6b3obob2o10b2o17b3o227b
o$143bo127b2o7bo2bo2bo2bo2bobo28bo3bo5bo91b3o186b2o$118bo8b2o12b3o127b
2o7bo6b2o4bo28bo5bo4b2o90bo2bo185b2o$118b3o6bo12bo140bobo38b2obob2o3bo
bo90bo$121bo6b3o9b2o140b2o141bo$120b2o8bo295bobo17b2o$294bobo28bo120b
2o$284bo10b2o27bobo$123bo159bobo9bo28bobo105b2o$121b2ob2o14bo135b2o4bo
b2o37b3o106bobo$140b3o133b2o3b2ob2o36b2o108bo185bo$120bo5bo16bo138bob
2o37bo3bo291bo$142b2o139bobo34b3o4b2o288b3o$120b2obob2o3b2o152bo35bo5b
obo$292b2o137bo$133bo158b2o47b2o88b3o10b2obob2o$126b2o212bobo82b3o6bo
4b3o$125bobo153bo60bo81bo2bo5b2o4bo4bo5bo$126bo15b2obob2o129b4o3bob2o
63bo74bo6b3o3bo$125b2o15bo5bo121b2o5b4o4bobob2o2b2o55b4o73bo7bobo7b2ob
2o$125b3o15bo3bo122b2o5bo2bo3b2obob2o2bobo48b2o3bobob2o14b2o53bobo7bo
3bo8bo128b2o$126b2o12bo3b3o130b4o3b2o8b3o47b2o2bo2bob3o11bo2bo63b5o
137bobo59bo$124bo14b2o137b4o3b2o8b3o6b2o43bobob2o11bo7b5o54b2o3b2o136b
o59b3o$139bobo139bo12b3o7b2o44b4o12bo6bo5bo54b5o6bo189bo$293bobo56bo5b
o7bo7b2o3bo38b2o15b3o6bobo188b2o$293b2o48b2o12bo9bo2bo7bo39b2o16bo6bo
3bo$125bo217bobo11b3o9b2o72b5o$124b3o216bo98b2o3b2o$123b5o163bo25bo
125b5o$122b2o3b2o14bo147b3o24b2o117bo6b3o$123b5o15bo150bo22b2o44bo70b
2o9bo$123bo3bo14bobo148b2o65b4o4bo48b3o5b3o6b3o196bo$124bobo14b2ob2o
213b4o5bo56bo2bo6b2o195b3o$125bo14bo5bo184b2o26bo2bo9b2o43bobo5bo9bo
17b2o176b5o$143bo145bo14b2o23bo2bo26b4o9b2o42b5o4bo8bobo16b2o167bo7b2o
3b2o$140b2o3b2o141bobo14b2o21bo31b4o51b2o3b2o4bobo5b2o184b2o$125b2o
144b2o14bo3b2o3b2o6bo23bo34bo51b2o3b2o199b2o$125b2o144bobo13bo3b2o3b2o
30bo303bo$144bo121b2o4b3o12bo3b2o28b2o6bo2bo5b2o95b2obob2o190bo$144bo
117b4o2bo4b3o12bobo29bobo8b2o5bobo17bo2bo8bo49b2o22b2o$145bo116b3ob2o
4b3o7bo6bo30bo19bo17bo10bobo48bob2o11bo5bo2b2o189b2o$181bo89bobo9b2o
34b2o19b2o12bo2bo3b2o5bo3b2o3b2o44bo211bo$182bo88b2o9b2o67b4o3b2obobo
4bo3b2o3b2o57b2ob2o195b3o$142b2o36b3o160b2o5b4o14bo3b2o44bob3o8bo6bo
15bo143b3o37bo$142b2o199b2o5bo2bo8b2o5bobo46bo11b2o21b3o142bo$350b4o
16bo47bo11bobo19b5o142bo$277bobo7b2o62b4o85b2o9b2o3b2o$272bo4bo2bo6b2o
65bo85bo11b5o$273b2o5b2o159b3o8bo3bo142b2o$268b2o8bo3b2o159bo9bobo142b
o3bo$268b2o10b2o135b2o3b2o30bo142bo5bo$277bo2bo138b3o16b2o9b2o136b2o8b
o3bob2o10b2o$277bobo138bo3bo14b2o9bobo136b2o8bo5bo10bo3bo$419bobo10bo
6bo7b3o4b2o142bo3bo10bo5bo3b2o$420bo10bobo12b3o4bo2bo142b2o12bo3bob2o
2b2o$271bo9b2o141b2o3b2o3bo12b3o4b2o157bo5bo$270bobo7b4o140b2o3b2o3bo
13bobo163bo3bo$263b2o4bob2o5b3o2bo2bobo140b2o3bo14b2o156bobo5b2o$263b
2o3b2ob2o9b2o2bo2bo130b2o9bobo166b3o5b2o$269bob2o6bo9b2o6b2o121b2o10bo
169bo5bo$270bobo5bo8bo3b2o4b2o292bo9bo$271bo6bo10b2o299bobo$286bo2bo
288b2o10b2obo8bobo$286bobo289b2o10b2ob2o6bo2bo$590b2obo6b2o$377b2o3bo
2bo3b2o199bobo5b2o3bo$377b5o4b5o200bo8b2o$374bo2b2o3bo2bo3b2o210bo2bo
5b2o$373bobo226bobo5bobo$372bo3bo235bo$341bo30b5o235b2o$341b3o27b2o3b
2o$344bo27b5o$343b2o28b3o$374bo354bo$728bobo$728bobo$729bo2$630bo93b2o
7b2o$631b2o90bo2bo5bo2bo$630b2o92b2o7b2o$344b5o$343bob3obo24b2o353bo$
275b2o19b2o46bo3bo25b2o352bobo$276bo19bo48b3o380bobo$276bobo6bobo6bobo
49bo382bo$277b2o6bo2bo5b2o$288b2o$286bo3b2o51b2o$288b2o54bo$285bo2bo
52b3o$285bobo53bo9$316b2o19b2o$317bo19bo314bobo$317bobo6b2o7bobo315b2o
$318b3o5bobo6b2o316bo$320b3o6bo$320bo2bo2bo2bo$321b2o6bo$326bobo$326b
2o4$262bobo$262bo3bo$256b2o8bo132bo$246bobo6bo2bo3bo4bo4b2o123b3o$246b
o3bo5b2o8bo5b2o122bo$236b2o12bo11bo3bo129b2o$236b2o8bo4bo10bobo$250bo
6bo$246bo3bo5b2o$246bobo7bobo2$391b2o3b2o277bo$270b2o122bo281b2o$263bo
b2o3b3o118bo5bo277b2o$259bo2bo3bo5b2obo5b2o109b2ob2o$258b2o2bo4bo4bo2b
o5b2o110bobo$257b2o5b4o4b2obo118bo$256b3o7bo3b3o121bo$257b2o11b2o$249b
2o7b2o$248bobo8bo$248bo147b2o$247b2o147bo$397b3o$399bo10$697bobo$698b
2o$698bo6$377b2o$376b3o$373bob2o$373bo2bo$373bob2o$367b2o7b3o5b2o$366b
obo8b2o5bobo$366bo19bo$365b2o19b2o6$720bo9bo$659b2o6b2o52b2o5b3o$658bo
2bo4bo2bo50b2o5bo$657b6o2b6o56b2o$641b3o14bo2bo4bo2bo$643bo15b2o6b2o
11b2o43bo$642bo30bo5b2o43bobo$671b2ob2o5bo41bo3bo$723b5o$670bo5bo45b2o
3b2o$723b5o$670b2obob2o47b3o$725bo$374b2o$376bo$363b2o12bo$363b2o4bo7b
o8b2o$352b2o6b2o5b2o8bo8b2o$352b2o5b3o5bo2b2o4bo$360b2o6b5ob2o351b2o$
363b2o4bo302b2o53bo$363b2o307b2o54b3o$730bo2$365b2o9b2o315bo8bo$363bo
3bo7b3o315bobo6bobo$357b2o3bo5bo5b2o243b2o75b2o4b2o$357b2o2b2obo3bo3bo
2bo242bobo61b2o12b2o11bo$362bo5bo4b2o245bo61b2o12b2o11bobo$363bo3bo
325bobo16b2o4b2o$365b2o326bo18b2o4b2o$385bo326b2o$383bobo323bobo$384b
2o323bo$360bo8b2o$358bobo6bo2bo323b2o$351b2o4bobo7bo3bo2b2o306bobo10b
2o$351b2o3bo2bo7bo2b2o2b3o305bo2bo8bo$357bobo16b2obo293b2o10b2o11b2o$
358bobo4b3o8bo2bo5b2o286b2o8bo3b2o8bobo$360bo15b2obo5b2o291b2o5b2o9bo$
374b3o300bo4bo2bo10bo2bo$374b2o306bobo11bo$697bobo5b2o$698b2o5bobo$
376b2o329bo$376b2o329b2o8bo$718bo$716b3o$596b3o$377bo220bo$376bobo218b
o129b2o$375bo3bo347b2o4b3o$376b3o334bo10b2o6b5o$374b2o3b2o332bobo7b3o
5bo3bobo$702b2o12b2o6b2o6bo3b2o$702b2o12b2o9b2o$716b2o9b2o$713bobo$
713bo11bo$723bobo$379b3o342b2o$381bo336b2o$380bo337b2o$374b2o331b2o6b
2o6b2o$375bo331b2o5b3o5bo2bo$372b3o340b2o6b2o$372bo345b2o$718b2o$724b
3o$380bo345bo$363b2o15b2o192b2o149bo$123bo238bo3bo12bobo191bobo137bo$
123b3o220b2o13bo5bo3b2o202bo136b2o$126bo212b3o4b2o13bo3bob2o2b2o37bo
290b2o8b2o4b2o5bo$125b2o211b5o6b2o10bo5bo41b2o290b2o7b3o4b2o3bobo$337b
obo3bo5b3o10bo3bo31b2o8b2o11b2o288b2o4b2o2bobo$337b2o3bo6b2o12b2o33b2o
7b3o7bo3b3o288b2o6bo2bo11b2o$346b2o9bobo48b2o5b4o4b2obo286bo7bobo11b2o
$346b2o10b2o49b2o2bo4bo4bo2bo5b2o288bobo$358bo51bo2bo3bo5b2obo5b2o290b
o$414bob2o3b3o$421b2o$353bobo6b2o$125b2o3b2o221bo3bo4b2o37bo$357bo42b
2o$126bo3bo212b2o8bo4bo41bobo14bo$127b3o213b2o12bo59bobo$127b3o223bo3b
o52b2o8b2o$353bobo53bo2bo7b2o4b2o$409b3o8b2o4b2o$125b2o283b2o5bobo$
126bo219bo61bobo6bo$123b3o218b4o6b2o2b2o47b2o$123bo214b2o3bobob2o5b4ob
o2bobo44bo141b3o$338b2o2bo2bob3o5b2obo3bo3bo52b2o132bo$343bobob2o4bo
12bo5b2o43bo3bo130bo$344b4o14bo4bo4b2o34bo7bo5bo8b2o$346bo19bo41bobo4b
2obo3bo8b2o$362bo3bo30b2o12b2o3bo5bo$165b2o195bobo32b2o12b2o4bo3bo$
165b2o4b3o237b2o6b2o$162b2o6b5o233bobo$149b2o7b2ob3o5bo3bobo232bo$149b
2o11b2o6bo3b2o$138b2o6b2o17b2o$138b2o5b3o5b2o10b2o$146b2o9b2o$149b2o$
149b2o3$163b2o9b2o$163bobo7bobo$157bo5bo8bo6b2o2b2o$156bobo13bo2bo2bo
2bob2o$155bob2o13bo6b2o348b2o$154b2ob2o14bobo352bobo$155bob2o15b2o354b
o$151b2o3bobo$150bobo4bo$150bo$149b2o5$26bo$26bobo$9bo17bobo$9b2o16bo
2bo3b2o$4b2o4b2o15bobo4b2o$2o2b2o4b3o13bobo22b2o$2o2b2o4b2o7bobo4bo24b
3o$9b2o9b2o28bo3b2o$9bo10bo30b2o3bo$3b2o23b2o21b2o3bo61b2o88b2o88b2o
88b2o88b2o$3b2o22b4o13b2o7b2o19b2o41b4o43b2o41b4o43b2o41b4o43b2o41b4o
43b2o41b4o$3b2o22b2ob2o10b2ob2o6b3o16b2ob2o40b2ob2o40b2ob2o40b2ob2o40b
2ob2o40b2ob2o40b2ob2o40b2ob2o40b2ob2o40b2ob2o$3bo25b2o11b4o7b3o16b4o
43b2o41b4o43b2o41b4o43b2o41b4o43b2o41b4o43b2o25b3o$2bobo38b2o9bo18b2o
88b2o88b2o88b2o88b2o73bo9b2o$2bobo10b3o36b2o451bo10bobo$3bo13bo33bob3o
464bo$16bo27b2o474b2o$44bo6bo$2o3b2o16b3o9b2o5bobo$obobobo16bo9bo2bo5b
2o$b5o12bo5bo7bo447b2o$2b3o3b2o6b4o12bo448b2o$3bo3bobo5bobob2o11bo89bo
bo355bo$9bo4bo2bob3o11bo2bo6b2o75bo3bo$14b2obob2o14b2o7b2o74bo$12b3ob
4o23bo75bo4bo8b2o$11bobo4bo101bo12b2o$11bo18b2o88bo3bo376bo2bob2obo2bo
$10b2o16bo2bo84bo5bobo375b2o2bo4bo2b2o$19b2o6bo7b3o3bo73b3o372b2o9bo2b
ob2obo2bo$4b3o12b2o6bo6bo3b5o53bo17bobobo372b2o3b3o$3b2ob2o19bo7bo3b2o
b2o9b2o39bobo17bobobo371bo5b3o$3b2ob2o20bo2bo3bo3b2ob3o8b2o37b2o21b3o
377bo3bo$3b5o22b2o5b4ob2o48b2o22bo377bo5bo$2b2o3b2o30b4o49b2o390b2o9bo
3bo$41bo46b2o4bobo8b2o376bobo10b3o$14b2o71bobo6bo8bobo8bo368bo$14bo2bo
69bo19bo7b3o$5b6o7bo6b2o59b2o19b2o5bobobo$4bo6bo6bo6b2o87bobobo$4bo4b
2o7bo96b3o$5b2o7bo2bo98bo$14b2o442bo$458b2o$457bobo$497b2o$497b2o3$
480bo2bob2obo2bo$480b4ob2ob4o$469b2o9bo2bob2obo2bo$468bobo5bo$470bo4b
3o$474bo3bo$473bob3obo$474b5o$461b3o$398b2o63bo$380b2o16b2o62bo$380b2o
16b2o$399bo$398bobo$398bobo$380bo7b2o9bo$379b3o6b2o45b2o$378bo3bo53b2o
$377bob3obo12b2o3b2o32bo40b2o$378b5o8bo4bobobobo73b2o$390bo6b5o$390bo
7b3o$399bo59bo2bo4bo2bo$457b3o2b6o2b3o$386b2o3b2o55bo10bo2bo4bo2bo$
377b2o2bo7bo58b2o5bo$379bobo4bo5bo54bobo4bobo$381b2o4b2ob2o61bo3bo$
382b2o4bobo63b3o$380bob2o5bo6bobo53b2o3b2o$380b3o6bo6b2o41b2o$397bo40b
obo$440bo$375b2o3b2o$378bo12b2o7b3o$375bo5bo9b2o6bo3bo$376b2ob2o17bo5b
o$377bobo19bo3bo$378bo21b3o10bo$378bo21b3o10b2o$412bobo40b2o$455b2o2$
401b2o36b2o6b2o$378b2o21b2o34bo4bo2bo4bo$378b2o57bo4bo2bo4bo$437bo4bo
2bo4bo$381bo44b3o10b2o6b2o$381b3o44bo4b3o$384bo42bo5b3o$383b2o47bo3bo$
402bobo$403b2o26b2o3b2o$403bo12b3o$418bo$417bo$383b2o3b2o$383bobobobo$
384b5o$385b3o$386bo32bo$390b2o27b2o$391b2o21b2o4b2o12b2o$390bo23b2o4b
3o11b2o$414b2o4b2o$411b2o6b2o7b2o$383b2o25bobo6bo8bobo$384bo25bo19bo$
381b3o25b2o19b2o$381bo6$394b2o$393bobo$395bo5$422b2o$399b2o21b2o$399b
2o$407b3o$407bo$408bo3$362b2o$362b2o21b2o$385b2o12b3o13b2o$398bo3bo12b
3o$391b2o4bo5bo8b2o6b2o3b2o$391bobo3b2obob2o7bo3bo6b3o$385bo7bo17bo3bo
5bo3bo$361b3o20b3o6b2o17b2o8bobo$371b3o9bo3bo15bo19bo$361bobo9bo8bob3o
bo13b2o$360b5o7bo10b5o32b3o$359b2o3b2o35bob2o15b3o$359b2o3b2o34bo2b2o$
377b2o21b4o5b2o3b2o$377b2o32b3o$364b2o14b3o27bo3bo3b2o3b2o$364bob2o4b
3o5bo18b2o3b2o5bobo5b5o$367bo13bo20bo9bo7b3o$372bobo24bo5bo15bo$362bob
3o4b5o24b2ob2o$362bo7b2o3b2o24bobo$362bo7b2o3b2o25bo9b2o$402bo9b2o2$
373bo8b3o$374b2o5bo3bo$361b2o3b2o12bo5bo33b2o$363b3o10bo3b2obob2o15b2o
16b2o$362bo3bo35b2o$363bobo6bo2bo$364bo7b2o9bo$382bobo$382bobo$383bo$
364b2o$364b2o16b2o$382b2o!
Gabriel Nivasch, Dean Hickerson and Dan Hoey then wondered about the possibility of slower growth rates, but none made the conceptual leap necessary to do so:
Dan Hoey wrote:There are even slower-growing functions--log**, log***, etc.
Alexey has finally resolved this 9-year-old open problem by constructing what I shall name a
recursive filter. It does the following:
- S(X | recursive_filter) = g, where g(n) := f(f(f(...f(1)))), where the number of 'f's is equal to n, and f := S(X).
If you want to, you can express this with lambda calculus:
- S(X | recursive_filter)(n) = n(S(X))(1) where we treat n as a Church numeral.
Anyway, an explicit example is the log* pattern he posted:
- S(caber_tosser | recursive_filter)(n) = λn.(2 ^^ n).
We can get extra arrows by piping extra recursive filters:
- S(caber_tosser | recursive_filter | recursive_filter)(n) = λn.(2 ^^^ n).
Indeed, for every primitive-recursive function f, we can now obtain a slowness rate S(X) which asymptotically dominates f.
That is what Alexey has done.
So, simsim314, I shall politely request that you do not belittle work that solves a decade-old engineering problem in such a beautiful and elegant manner. You have made many great contributions to Life research (I'm in awe of CatForce, for instance), but that does not give you the right to insult others when they do the same. I think you owe Alexey an apology.