Thread for basic questions

[dvgrn]

Is this an emu?

Code: Select all

x = 32, y = 34, rule = B3/S23
10bo6bo$9b2o6b2o$8b3o6b3o$9b2o6b2o$bo8bo6bo$b3o$4bo$3bobo$4bo4b3o$9bo$
10bo$5b2o$5b2o$25b2o$25b2o$bo10b3o11bo$o3b3o5bobo2b3o4b5obo$bob5o4b3o
2bobo5b3o3bo$5bo11b3o10bo$5b2o$5b2o$25b2o$25b2o$21bo$22bo$20b3o4bo$26b
obo$27bo$28b3o$14bo6bo8bo$13b2o6b2o$12b3o6b3o$13b2o6b2o$14bo6bo!

I'd say no -- not by the classic definition anyway. Even if you modernize the definition a bit and make it a "signal loop" instead of a "Herschel loop" (which would bring things like p43 Snark loops into the "emu" category") there's still an obvious clear difference between a glider-producing oscillator where the gliders can't quite escape, and a glider-producing signal loop where the gliders can't quite escape. I think the "signal loop" detail is an important distinction.

It's certainly a very "emu-like" oscillator, quite similar to Simkin's p60, as Wyirm points out. But you can change the number of signals in Simkin's p60 (take one signal out); there's nothing like that that you can do with the oscillator.

[yujh]

Same, I second the point that there's actually no actual signals in this oscillators, or emus will just be capped guns

[dani]

When was the R-pentomino's evolutionary sequence finally fully determined? I seem to recall that Conway and Guy stopped soon after the FNG, and that a later person made it to 1000 with the aid of a computer, without seeing the end. But I don't know when the very final ash would have been seen for the first time.

EDIT: Oh, and while I'm here, is there a good way of getting the apgcode of a linear growth? I found a post from Calcyman that explains how to use "stdin_test" symmetry to find it, but it seems the syntax is different now because it just runs a random soup instead of what I put into it.

[Sokwe]

When was the R-pentomino's evolutionary sequence finally fully determined? I seem to recall that Conway and Guy stopped soon after the FNG, and that a later person made it to 1000 with the aid of a computer, without seeing the end.

I'm not sure where you may have read that. The first natural glider from the R-pentomino would have been identifed at generation 71, but in Martin Gardner's initial Life article it's mentioned that "Conway has tracked [the R-pentomino] for 460 moves." Where would it be mentioned that someone had tracked it to 1000 generations with a computer? This isn't too far short of its 1103-generation lifespan. I don't think the R-pentomino's fate is mentioned in the other two Gardner articles that mention Life (or are there more than 3 total?) In Lifeline Volume 1 from March 1971 Wainwright says that "by now we all know the fate of the notorious R-pentomino", and the lifespan is mentioned on page 6. I'd be shocked if the R-pentomino's fate wasn't known before 1971.

I've attached a .zip file with the three Gardner articles I know of that mention Life. Was any other Life content published anywhere prior to Lifeline Volume 1?

Gardner-Life.zip

(1.41 MiB) Downloaded 100 times

[dvgrn]

Where would it be mentioned that someone had tracked it to 1000 generations with a computer?

Elsewhere on these very forums.

I did a little further correspondence about the possible first-ever Life program, but there didn't seem to be any kind of paper trail documenting either it or the first known fate of the R:

I suspect there won't be any hard evidence left anywhere of when you wrote the first-ever Life program, but with the 50-year anniversary of the Game of Life coming up, I figured I might as well ask!

Conway's biographer Siobhan Roberts dug up some evidence that Conway "rounded up" the initial investigation of the B3/S23 Life rule to 1970, but that the R-pentomino was actually being hand-simulated "late in the fall of 1969". Might you have any way of confirming or denying that detail, or even possibly narrowing the date range a little?

I doubt there are still usage logs available for the IBM 360 at the Institute of Theoretical Astronomy... but if you still happened to have some relevant paper printouts in a box somewhere, that would certainly be interesting!

I went up to Cambridge in 1968, and graduated in 1971. Conway's date of "late 1969" for hand tracking the R-pentomino would fit in well with my recollection - by that time I was in my second year, and would have had time to discover (and hang around) the common room where Conway et al. spent quite a bit of time on recreational mathematics. It was definitely before Martin Gardner's October 1970 Scientific American column that introduced Life to a wider audience.

I'm pretty sure there's no real evidence lying around by now...

[Ian07]

EDIT: Oh, and while I'm here, is there a good way of getting the apgcode of a linear growth? I found a post from Calcyman that explains how to use "stdin_test" symmetry to find it, but it seems the syntax is different now because it just runs a random soup instead of what I put into it.

Here's what I did:

1. Run the following commands to create the executable:

   Code: Select all

   ./recompile.sh --rule b3s23 --symmetry stdin_test
   mv apgluxe apgluxe-stdin_test

2. Inside the apgmera folder, create "test.py" which contains only a single print() with an RLE of your choice:

   Code: Select all

   print("""x = 33, y = 14, rule = B3/S23
   2o5b2o$2o5b2o2$4b2o$4b2o5$22bo3bo$21bo4b2o$20b2o5b2o2b2o$21b2o4bo3b2o
   $22bo!
   """)

3. Run the following command:

   Code: Select all

   python test.py | ./apgluxe-stdin_test -t 1 -L 0 -n 1

This should print out the following result for the Simkin glider gun:

Code: Select all

Linear-growth pattern detected: yl60_1_5_caed21b47aa93fc91475b6fbf49cc7df

This also works as a method to census a single RLE in general, although you'll want to do "-L 1" in that case so you can get a full log.

[dani]

Thank you, Ian07. I'll dump a few linear growths' apgcodes here for those who can't use apgsearch:

Puffers:
Puffer 1 - yl128_1_26_ca608988cdf47a55a0ca90e80c540752 (documented)
Puffer 2 - yl70_1_220_bcda2d6374b4e65cf6929b5954a30a44
Forward space rake - yl20_1_5_27adc8ec75c3641b29686def8d9ee345
Backward space rake - yl20_1_5_155d12213f4ea735f95599fa04c025c0
mystical's 56c/112 puffer - yl112_1_82_80f81a62f15402811599fd17dd27ab8b
Sakapuffer - yl96_1_9_5ac029549cd1cca54f53e422caa3035a
Backrake 1 - yl8_1_5_0bf50c3cfec98dda4b4f2bf48b24c165
Backrake 1 variation 1 - yl224_1_124_dba48dad464bf68d57e23f0f518d5fa5
Backrake 1 variation 2 - yl80_1_190_b00160e814b1a0471ef09fc27f75f26a
Blinker puffer 1 - yl8_1_3_5b4e3057e73f3d3fc97a9d7a9030acc2
Blinker puffer 2 - yl8_1_3_894f1cf325579f51a48665a70730457b
Doo-dah attachment - yl21_1_6_676aa474b99e4d513f419211b337dc23

Guns:
Bi-gun - yl46_1_10_ace82e6a60e972a3a224b998d5e29b17 (documented)
New gun 1 - yl46_1_5_84f2c43017f3d669c3d66228977aad02
Former smallest p46 gun - yl46_1_5_53ae3c3b75dee9e380af03c4ab4aa796
Smallest p46 gun - yl46_1_5_6e8d2e260f6611e0c10d378d936de933
AK-94 - yl47_1_5_4884ca8828b7f43a6234dcc4b649c4a8
p46 edge shooter - yl46_1_5_69b89d3781c81b8a235645dd57ada145

And some natural puffers which were formerly just labeled by their date or lumped into a zz class:
Birthday puffer - yl2304_1_986_8e2bd7437df913dfe2dc05491a8f02e5
yl2304_2016_08_07 - yl1152_1_406_55fc3043e0cfc8b080c84d4800ee3c05
b3s23/C1 zz_LINEAR #2 - yl1152_1_338_65c01b6efd2fb4d5a399e00a6cc73f1a
b3s23/C1 zz_LINEAR #4 - yl2304_1_1553_7ddf2125170b121a099d591e2588e1fb
b3s23/C1 zz_LINEAR #5 - yl1152_1_332_ce5c623ad49c2712d55df5b89c87da86
b3s23/C1 zz_LINEAR #6 - yl1152_2_1026_bc233ec792703ddced3e30ec0cf9e954

[m00sehead]

I've just downloaded the mobile version of golly, and created a .rule file for a custom rule. However, when I go to the rule section of the app, the change algorithm to rule loader, there is no option to load a file from my files. Does anyone know how I can load a .rule file from my devices files into golly mobile app (I'm on Android, in case that matters) or if there is some forum specific to golly where I should post this instead?

[confocaloid]

Is there a way to make Golly automatically stop when the population becomes zero? Something like "Life ended at generation N" in LifeViewer, so that a long-living pattern such as the one below can be run at high speed exactly until it dies out:

Code: Select all

#C [[ ZOOM 8 ]]
x = 6, y = 3, rule = B3/S23
3b2o$3b3o$3o2bo!

If not, is there a way to add this feature by a script running in background?

The same question for patterns that eventually become constellations of still lives - how to auto-stop Golly as soon as the pattern is p1?

Code: Select all

#C [[ ZOOM 4 ]]
x = 16, y = 30, rule = B3/S23
8$2b5o$2b2o2bo$bo2b3o!

[dvgrn]

Is there a way to make Golly automatically stop when the population becomes zero? Something like "Life ended at generation N" in LifeViewer, so that a long-living pattern such as the one below can be run at high speed exactly until it dies out...
The same question for patterns that eventually become constellations of still lives - how to auto-stop Golly as soon as the pattern is p1?

(Moved this to the Basic Questions thread, since it seemed a little more like a question than a suggestion.)

The answer is that there's definitely a way to run a script to find the moment when a pattern becomes p1, or when the population goes to zero. However, you specified "at high speed", and that's not so easy (though it's still sort of possible).

Golly's blazing speed is in large part due to its ability to take shortcuts, jumping past large numbers of generations in one step. If you have to check population or for a matching pattern hash at every step, it's going to slow things down a lot compared to its normal speed.

That said, for the example patterns that you've given, a script could find the key point so quickly that you'd never notice that it was slower.

For really long-running patterns -- like, a pattern that self-destructs after 2^64 ticks or some such -- you'd have to write a more complex script, that experimentally tries running the pattern at higher and higher step sizes, until it finally steps too far and reaches stability... and then gradually steps down the size until it finds the exact point of transition.

The real difficulty comes when a pattern emits gliders or spaceships, or worse, glider-producing or block-laying switch engines, and those have to be ignored when calculating the point of stability. Catagolue/apgsearch has census code that does a pretty efficient job of this, except for the switch-engine cases, so that might be a good place to look if you want something along those lines.

[muzik]

Are there any ways to synthesise four eaters (https://catagolue.hatsya.com/object/xs2 ... oge2/b3s23) that isn't just literally synthesising four literal eaters? The predecessor must be able to be created somehow with less than 8G.

[dvgrn]

Are there any ways to synthesise four eaters (https://catagolue.hatsya.com/object/xs2 ... oge2/b3s23) that isn't just literally synthesising four literal eaters? The predecessor must be able to be created somehow with less than 8G.

Maybe there's a way, if someone can find a 4G collision that makes half of the key object. Here are a couple of sets of six gliders that abjectly fail to be a proper synthesis (and these were the best that synthesise-patt.py could provide):

Code: Select all

x = 19, y = 34, rule = LifeHistory
4.3D5.3D$3.D3BD3.D3BD$2.D4BD3.D4BD$2.DCBD3C.CBCDB2D$.3BCBCDB.B2C5B$.B
3C2BC3.C6B$8B3.8B$.6BC3.C2B3CB$.5B2CB.BDCBC3B$2.2DBDCBC.3CDBCD$2.D4BD
3.D4BD$3.D3BD3.D3BD$4.3D5.3D9$4.3D5.DCD$3.D3BD3.D2BCD$2.D4BCBC.D3CBD$
2.2DBDB2CBD2BDB2D$.5B2DC2.2D5B$.2BC4B4.3B2CB$.CBC4B3.4BCBCB$.B2C3B4.
4BC2B$.5B2D2.C2D5B$2.2DBD2BDB2CBDB2D$2.DB3CD.CBC4BD$3.DC2BD3.D3BD$4.D
CD5.3D!

The octohash database has a few suggestions, but the best one is this

Code: Select all

x = 16, y = 15, rule = B3/S23
5bo$4bo$bo2b3o$obo6bobo$bo8b2o$10bo$3bo$2bobo$2bo2bo$3b2o9b2o$13b2o$
15bo$7b2o$6bobo$8bo!

and there's no 3G recipe for that constellation (and here again the gliders interfere no matter what you do anyway.)

EDIT: Fired up popseq, and yes indeedy there was just barely a 7G solution hiding in there (now boxed):

Code: Select all

x = 65, y = 63, rule = B3/S23
4bo$5bo$3b3o33$20bo$21bo$19b3o9$28bo$26bobo$27b2o$22b3o$24bo$23bo6$62b
2o$20b2o40bobo$21b2o39bo$2o18bo$b2o$o!

[hotdogPi]

I'm not sure why four eaters is even a thing. It comes from the Life digits article, but as far as I know, nobody here has seen it occur naturally.

[Wyirm]

Why can rules with s4w or s5a support c/3d spaceships, while others can't? I thought information transmission speed is solely limited by birth transitions.

[toroidalet]

Consider the following pattern:

Code: Select all

x = 3, y = 3, rule = LifeHistory
D.A$.2A$3A!

If the red cell is born in generation 2, then it should be able to advance at c/3. However, if we lack B2e, S4w and S5a, then it cannot be turned on in that generation.

Code: Select all

x = 3, y = 3, rule = B3/S235aHistory
D.A$.2A$3A!

Birth transitions play a key role in information speed transmission (no rule without B1e or B2a can advance at c orthogonally), but survival transitions are important too in allowing births to take place near the front. The maximal speed limit in non-lightspeed rules is c/2 orthogonal and c/3 diagonal, but some rules cannot achieve this due to lacking certain survival transitions (for another example, B3/S cannot have c/2 spaceships).


All patterns in non-lightspeed rules cannot expand faster than this pattern:

Code: Select all

x = 3, y = 3, rule = B2-a345678/S012345678
bo$3o$bo!

All patterns in rules without B2e, S4w and S5a cannot expand faster than this pattern (the speed limit proof for Life works in any rule without these transitions):

Code: Select all

x = 3, y = 3, rule = B2-ae345678/S01234-w5-a678
bo$3o$bo!

[GUYTU6J]

We have more composers that are born in 3G:

Code: Select all

#C [[ GRID MAXGRIDSIZE 14 THEME Catagolue ]]
#CSYNTH xp2_4a96069a4zy07 costs 3 gliders (pseudo).
#CLL state-numbering golly
x = 10, y = 7, rule = B3/S23
4bo$4bobo$4b2o$bo$2bo4bobo$3o4b2o$8bo!

Code: Select all

#C [[ GRID MAXGRIDSIZE 14 THEME Catagolue ]]
#CSYNTH xp2_25acxca52zy17 costs 3 gliders (pseudo).
#CLL state-numbering golly
x = 9, y = 8, rule = B3/S23
o$b2o$2o5b2o$6b2o$8bo$2b2o$bobo$3bo!

What are their names?
Also, do these four-object constellations count?

Code: Select all

#C [[ GRID MAXGRIDSIZE 14 THEME Catagolue ]]
#CSYNTH xp2_s01110szw252 costs 3 gliders (pseudo).
#CLL state-numbering golly
x = 14, y = 7, rule = B3/S23
4bo$4bobo$4b2o2$2bo10bo$obo8b2o$b2o9b2o!

Code: Select all

#C [[ GRID MAXGRIDSIZE 14 THEME Catagolue ]]
#CSYNTH xp2_s01110szw696 costs 3 gliders (pseudo).
#CLL state-numbering golly
x = 14, y = 11, rule = B3/S23
2bo$obo$b2o2$4bo$4bobo$4b2o2$11b3o$11bo$12bo!

Code: Select all

#C [[ GRID MAXGRIDSIZE 14 THEME Catagolue ]]
#CSYNTH xp2_s01110szwcic costs 3 gliders (pseudo).
#CLL state-numbering golly
x = 12, y = 7, rule = B3/S23
2bo$obo6b2o$b2o6bobo$9bo$4b2o$5b2o$4bo!

EDIT:

The 3Glider database I have shows only 5 collisions where the results contain a Snake:

Code: Select all

x=35, y=35
32bo$32bobo$32b2o27$o$b2o$2o$5bo$4b2o$4bobo!

...

This one can be cleaned up with a single glider, so now there is at least one two-stage four-glider synthesis for a snake!

Code: Select all

x = 17, y = 16, rule = B3/S23
o$b2o$2o3$3b3o2$bo5bo$bo5bo$bo5bo3$6b2o5b2obo$5bo2bo4bob2o$5bobo$6bo!

[Wyirm]

I have trouble understanding non-polynomial growth rates. Caber tossers make sense, they are logarithmic. Sqrt guns are slightly more complicated though, they work by linearly increasing the distance between the gun and the block, resulting in a recursive function 1+x/a, where a=1+x/a, which when iterated enough make something that looks like sqrt. Furthermore, replacing a with y and graphing it results in a clear parabola, and inversing the function results in y=-x^2-x. However, other stuff is absolutely bizarre. HOW does summating (x-n)/n result in tlog(t) growth? How do recursive and exponential filters work together to result in hyperlinear growth? Am I just wasting my time trying to make rigorous mathematical proofs on block cellular automata? It gets worse when you consider that none of these model actual functions, but repeated summation functions. someone tell me why and how all of these growth rates are created.

[toroidalet]

t*log(t) growth
The t*log(t) pattern produces guns, where the nth gun has a period of p*n. In other words, it produces gliders 1/n of the time compared to gun 1. If the period of the gun puffer is c, then after c*n generations there will be n guns, with a growth rate of (1+1/2+1/3+...1/n)*O(t)=O(t*log(t)).
(Note that all guns are not created at the same time, but in doing so the nth gun only misses out on c*n/p*n=c/p=O(1) gliders for O(t) total, which does not affect the asymptotic growth rate)
Filters
The quadratic filter is the same mechanism as the parabolic sawtooth. A block or other still life n cells out is pushed out to n+1 while making another block which has to be pulled the n cells back, then it repeats with n+1. Each time, it creates a glider, so that when n gliders are created, it will have taken n^2 gliders in. In other words, its growth is the square root of the input device.
The exponential/recursive filter is more complicated. After the block (loaf) is pulled all the way in at generation g, it then makes another one all the way at c*g cells, so that if the input device produces the nth glider at f(n) (i.e its growth rate is f^-1(n)), the next glider will be produced when c*g gliders have been consumed, which will take f(c*g) generations, then f(c*f(c*g)), and so on (this is why it's called the recursive filter). The growth rate is therefore the inverse of O(f^n).

In general, it's easier to find the f(n) than the growth rate.

[confocaloid]

Is it known whether one can always determine (destructively or not) the phase of a glider-constructible oscillator?

As an example, xp4_caab88gz354kkldzw32 is glider-constructible, so the question applies to it. The following setup can distinguish all four phases of it: the possibilities are (a) no gliders escaping and the population remains nonzero, (b) a SW glider escapes, (c) the population becomes zero, (d) a SE glider escapes.

Code: Select all

#C [[ THEME LifeHistory ]]
x = 165, y = 15, rule = B3/S23
bo49bo49bo49bo$2bo49bo49bo49bo$3o47b3o47b3o47b3o$10b2o48b2o48b2o48b2o$
10bo49bo49bo49bo$11b3o47b3o47b3o47b3o$14bo49bo49bo49bo$9b6o44b6o44b6o
44b6o$8bo2bo46bo49bo49bo2bo$8b3ob3o43b3ob3o43b2o3b2o43b2o3b2o$11bo2bo
49bo49bo46bo2bo$8b6o44b6o44b6o44b6o$8bo49bo49bo49bo$9b3o47b3o47b3o47b
3o$11bo49bo49bo49bo!

[mniemiec]

Is it known whether one can always determine (destructively or not) the phase of a glider-constructible oscillator?

As an example, xp4_caab88gz354kkldzw32 is glider-constructible, so the question applies to it. The following setup can distinguish all four phases of it: the possibilities are (a) no gliders escaping and the population remains nonzero, (b) a SW glider escapes, (c) the population becomes zero, (d) a SE glider escapes. ...

I such cases, it should be possible to construct a mechanism to detect the phase of this oscillator (that is assumed to exist in that particular location) by shooting a glider at it, and seeing if a glider is emitted. Unfortunately, there's no easy way to distinguish between gliderless ash and no ash without shooting an additional glider at it. There may also be some oscillators where shooting a glider at them in multiple phases may yield the same result.

[dvgrn]

Unfortunately, there's no easy way to distinguish between gliderless ash and no ash without shooting an additional glider at it. There may also be some oscillators where shooting a glider at them in multiple phases may yield the same result.

In other words, the (c) case in the original sample pattern doesn't really look like a valid way to distinguish phases of that oscillator. We could add circuitry to catch the SW or SE gliders, or to record the absence of both of those gliders -- but some additional tests are needed for circuitry inside the Life universe to distinguish (a) from (c).

No "indistinguishable" oscillators are currently known, and I suspect that such things would be very hard to find. There are a lot of destructive tests that could be run, even for a maximally protected billiard-table oscillator. But it seems very difficult to prove definitively that no indistinguishable oscillator exists.

[mniemiec]

No "indistinguishable" oscillators are currently known, and I suspect that such things would be very hard to find. There are a lot of destructive tests that could be run, even for a maximally protected billiard-table oscillator. But it seems very difficult to prove definitively that no indistinguishable oscillator exists.

I think that they might be easier than you think. E.g. an oscillator that is mostly P2 space dust, with a small fragile P4 (mod 2) rotor core. Touching the space dust in any way could cause the whole thing to implode like a burst balloon, and the rotor could just vanish without ever being able to determine which phase it is in. (This argument is somewhat similar to the "mutually erasable" cells in the original Garden of Eden proof; e.g. if you have an otherwise empty 5x5 square, it's impossible from outside that square to determine whether or not the middle square was initially empty, because by the time you could get close enough to administer any tests, the difference would have long disappeared.)

[dvgrn]

I think that they might be easier than you think. E.g. an oscillator that is mostly P2 space dust, with a small fragile P4 (mod 2) rotor core. Touching the space dust in any way could cause the whole thing to implode like a burst balloon, and the rotor could just vanish without ever being able to determine which phase it is in.

Heh, as usual I will be happy to be proved wrong, but I think it might be harder than you might think. If you kill off a cell in P2 space dust you might get the "implode like a burst balloon" behavior" -- but what if there's an attack that consists of a wave of overpopulation at multiple points? How do you prove that there's no possible angle of attack that can retain some information about the phase of the rotor core?

To be clear, I don't think that it's hard to find reasonable candidates for "indistinguishable oscillators" -- I just think that it's hard to complete a proof that any of them really are definitely indistinguishable.

[Book]

I'm working on a new page (https://conwaylife.com/wiki/List of natural spaceships). The intention is to replace "List of common spaceships" with this, since few spaceships in the list can be considered common however generous one is with the definition of "frequently." It has everything listed in Catagolue as of today. But I have some questions about objects that do not appear in the census:

"MWSS and HWSS dragging block" is in wiki category "Natural periodic objects" but not in Catagolue census. Is it natural, and why not in Catagolue?
"58P8H4V0" is not in any naturalish wiki category, nor is it in Catagolue census. Why not?
"Big A" is in wiki category "Semi-natural periodic objects" but not in Catagolue census. Is it (semi-)natural, and why not in Catagolue?
"x66" is in wiki category "Semi-natural periodic objects" but not in Catagolue census. Is it (semi-)natural, and why not in Catagolue?
"Puffer 1" is in wiki category "Semi-natural periodic objects" but not in Catagolue census. Is it (semi-)natural, and why not in Catagolue? (but it's not a spaceship)
"29P3H1V0 " is in wiki category "Natural periodic objects" but I cannot find anything that supports that it is natural.
"30P3H1V0 " is in wiki category "Natural periodic objects" but I cannot find anything that supports that it is natural.

[hotdogPi]

By the way, frequency class can be calculated up to 42-43 or so.