Thread for basic questions

[dvgrn]

One possible notation using this system would be B2a(0246)/S2a(1357), which would only allow for birth on the displayed B2a conditions marked as 0, 2, 4 and 6, and survival on those marked 1, 3, 5 and 7. Like with non-totalistic rules, a - to negate unwanted orientations could also be used.

This notation probably isn't optimal when it comes to the lengths of rulestrings, but at least it could be interpreted a bit easier, and understanding what a rulestring symbolises at a glance is what i'm really after.

Hmm, but how are you going to interpret, say, B3k(12)/S4k(345)? Seems like you'll have to publish a numbered list of orientations for 3k and 4k as you did for 2a.

3k has only four orientations where 4k has eight, and some isotropic bits (e.g., 6n) have only two orientations. Vaguely confusing, but maybe tolerable. Or maybe it would be worth numbering the orientations 0-7 in the same way every time, and then only using the ones that aren't duplicates.

The full list of numbered isotropic bit orientations will have 256 categories in it, instead of the 512 neighborhoods in my suggestion -- the same name can be used for B and S rule bits. Maybe that would be a more sensible arrangement than a simple binary count in MAP-rule order, which is definitely really counterintuitive... mostly due to the center cell being the 2^4 bit, so that B and S rule bits are mixed together annoyingly in the binary MAP string, in length-16 chunks.

It does seem reasonable to name all of the non-totalistic neighborhoods according to their matching isotropic bit. An arbitrary number in parentheses may be a little confusing, but I can't think of any better way to refer to those up-to-eight different orientations.

So maybe the first step is to finish a 256-neighborhood diagram, with labels on every one of the neighborhoods in order -- B0(0), B1a(0), B1a(1), B1a(2), B1a(3), B2a(0), B2a(1)... etc., etc. Maybe just use Alan Hensel's diagram, and always call the displayed neighborhood (0), where (1), (2), and (3) are the same neighborhood rotated 90, 180, and 270 degrees (when that makes sense), then (4) is mirrored across the Y axis and (5), (6), and (7) are rotated copies of (4).

Something like that, anyway? It would then be trivial-but-tedious to write a script that gives you Henselish-muzikal-NT notation for any given MAP rule.

[Apple Bottom]

One possible notation using this system would be B2a(0246)/S2a(1357), which would only allow for birth on the displayed B2a conditions marked as 0, 2, 4 and 6, and survival on those marked 1, 3, 5 and 7. Like with non-totalistic rules, a - to negate unwanted orientations could also be used.

I have several ideas for this.

1. For the sake of easy understanding I'd avoid numbers -- which would require a publisher master list to interpret, as dvgrn points out --, and perhaps use compass directions instead, to wit:
   

   Code: Select all

   nw n ne
   w  -  e
   sw s se
   

   "B1(n,w)" is more easily understood than "B1e(1,2)" or so.
   
   In cases like B1, this would also do away with the distinct subconditions that are separately encoded in Alan Hensel's notation, but it would be difficult to ALWAYS do this; you'd generally still want to keep them separate.
   
   Figuring out how to match the possible orientations of a given isotropic subcondition with the compass direction might also be difficult / non-intuitive in general, so when doing this one would probably end up publishing lists again anyway, making this notation semi-mnemonic at best. (Kinda like Alan Hensel's, actually; I can never remember what exactly "4q", "4z" and all those mean without looking them up.)
2. It might actually be better to assign a single letter to each direction, and then directly specify which bits have to be set to satisfy a certain Bx or Sx condition. For example:
   

   Code: Select all

   l  n  r
   w  -  e
   v  s  h
   

   "l(eft)" and "r(ight)" for "nw" and "ne" are probably self-explanatory; I turned to Swedish for "v(änster)" and "h(öger)" for "sw" and "se".
   
   One could try and find other mnemonics in English as well. "c(lockwise)" is tempting; unfortunately "w(iddershins)" clashes with "w(est)"...
   
   In any case, any non-isotropic subcondition could then be expressed by putting together the respective letters. For instance, birth on 3 cells, those being either l, n and r, or alternatively l, e and v, could be expressed as "B3(lnr,lev)". Each non-isotropic subcondition would be represented by one group (which could be in any order, just like with Hensel's isotropic subconditions), and groups would be separated by commas, say.
   
   Negation still works: "B3(-lnr,lev)" is easily understood to mean birth on three live neighbors, UNLESS those neighbors are either l, n and r, or alternatively l, e and v.
   
   It would be possible to do away with the outer-totalistic B/S conditions in this notation and just write e.g. "B(w,e,l,lnr,lev,-nswe)" or so, but I think that's less readable overall. There's a lot of possible configurations that could be present (or negated), and parsing a long rulestring would be easier for humans if it's a organized according to overall neighbor count.
3. One could also stipulate that in this notation, for non-isotropic subconditions for 5 to 8 neighbors, the letters indicate dead cells rather than live ones. "B7(n,w)" is much shorter than "B7(lrwevsh,lnrevsh)", and should be intuitive and easy to understand.
4. Finally, since (as I noted) the labels for the compass directions are essentially arbitrary again, it might actually make sense to use numbers for those after all:
   

   Code: Select all

   1  2  3
   4  -  5
   6  7  8
   

   ...and write "B1(2,4)" instead of "B1(n,w)", and "B3(-123,156)" instead of "B3(-lnr,lev)", and so on. I think this is not quite as intuitive when you're not familiar with the notation at all -- it doesn't really get more intuitive than "B1(n,w)" --, but I think this would be a good alternative if noone can come up with good one-letter mnemonics for the diagonal compass directions. Remembering that the directions are 1 to 8, in order, is pretty easy.
   
   One possible downside is that people might interpret the digit groups as numbers. OTOH that might not actually be downside, since there's probably value in mentally associating e.g. "nw,w,ne" with the number 123, and so on.

All in all I prefer the third option, using "v(änster)" and "h(öger)" from Swedish for the southern diagonal compass directions. Alternatively I could get behind the fourth option, using the digits 1-8 for the compass directions.

Thoughts?

EDIT: referring back to your example:

Code: Select all

x = 38, y = 11, rule = LifeHistory
3D3.D3.3D2.3D2.D.D2.3D2.3D2.3D$D.D3.D5.D4.D2.D.D2.D4.D6.D$D.D3.D3.3D
2.3D2.3D2.3D2.3D4.D$D.D3.D3.D6.D4.D4.D2.D.D4.D$3D3.D3.3D2.3D4.D2.3D2.
3D4.D4$2EB2.B2E2.2BE2.3B2.3B2.3B2.3B2.E2B$BCB2.BCB2.BCE2.BCE2.BCB2.BC
B2.ECB2.ECB$3B2.3B2.3B2.2BE2.B2E2.2EB2.E2B2.3B!

using the "Swedish style" notation, these would be, in order: B2(ln), B2(nr), B2(re), B2(eh), B2(hs), B2(sv), B2(vw) and B2(wl), all very intuitive, self-explanatory, and easy to both create and understand once you know about "v(änster)" and "h(öger)".

I'd also like to christen this notation "Swedish notation" (in line with e.g. Polish notation).

EDIT 2: here's a write-up on the wiki (in my Incubator).

[Naszvadi]

Hi!

I have a basic question.

Wrote this basic c++, yet another game of life implementation, and the basic, which is c++, and the basic, which is c++ itself. (tested well with g++ 5.4.0)

http://vm01.unsoft.hu/~np/basic/latest/yetalife.bas
http://vm01.unsoft.hu/~np/basic/latest/ptsvubas.cc

Usage, compiling/"running"/etc.: in the latter file. (ptsvubas.cc has a co-author). The main c++ file is the basic file.

Where to announce this kind of developments here?

[APPEND] #1
Feel free to convert the next fossie to the basic dialect we implemented above:
http://www.atariarchives.org/basicgames ... p?page=102

[Macbi]

If I'm doing a computer search for something in Life (a p19 oscillator or a knightship or whatever) is there some minimum width for the bounding box that I should use in my search?

Hmm... that's not very clear. Let me rephrase. Nothing interesting can happen inside a strip of cells of width 1. Every row of live cells either dies or immediately goes outside the strip. Likewise, it takes a little bit of time with a pen and paper but you can prove that nothing interesting can happen in a strip of width 2. Eventually everything either dies, goes outside the strip, or becomes some blocks.

Of course in a width 5 strip something interesting can happen: a LWSS can form, running along the strip. So my question is about strips of width 3 and 4: can anything interesting happen here? By interesting I mean things like new ships or oscillator periods, obviously there might be a lot of still lives or perhaps variations on known stators.

I wonder if a computer could somehow enumerate all possible behaviours that could occur for widths 3 and 4?

[muzik]

There has been a bit of research into spaceships that are one cell thick in life, althhough i highly doubt any would be small enough to be conventionally searched for.

[dvgrn]

I wonder if a computer could somehow enumerate all possible behaviours that could occur for widths 3 and 4?

Seems like this question is asking about a minimum width in a sense that's the opposite from the conventional one. Usually when you see "minimum width" associated with spaceships, it's the width of the spaceship's narrowest phase -- like in the hypothetical one-cell-thick spaceship that muzik mentioned.

But for this question you wouldn't care about the one-cell-thick spaceship, because it doesn't stay inside a 1xN rectangle in all phases.

I think there might be something like a good answer to the question. Most spaceship search programs make you specify a speed and a width. So if you put in parameters of "c/2 orthogonal" and "width-5 asymmetric" into something like WLS/JLS or gfind, you'll get an LWSS out. (The settings look a lot different depending on the program, but you can do it in both.)

If you put in width 4 or less, you don't get anything -- at that speed. Basically the search program tries everything until it runs out of workable options for the given width, at the given speed.

In gfind sometimes you find a repeating unit that you can make infinitely long spaceships with -- but the search proves that there's no way to end the spaceship at that width.

If you get to where you really understand [url=hhttp://conwaylife.com/wiki/User:Sokwe/Spaceship_searches]Sokwe's table of spaceship searches[/url], then you'll know a lot more than I do. I believe some of the green boxes are "the narrowest spaceship at such-and-such speed was found at this width", and some of the reddish boxes are "searches have been done for this speed up to this width, with no spaceships found".

This doesn't answer the question of whether something like muzik's mythical c/18 ship might not appear, if someone just tried running gfind at width 3 for every possible individual speed up to c/100 or some such... or until the program crashes... then width 4, then width 5, etc., until the searches started taking too long at each width.

At width 3 the search probably finishes pretty much instantly with no results. It may be possible to prove that that's always going to happen no matter what speed you're looking for (up to "self-constructing slow" speeds in unsearchable-sized rectangles, where anything is possible even down to width 1).

It's quite possible that someone has (or multiple someones have) tried something like this, but I don't know what the limits of such a search might have been. It hadn't been done with any thoroughness as of March of last year, or zdr's c/10 copperhead would have been found sooner.

[Macbi]

Now that I've thought about it a bit, I think I can see how a proof (that nothing interesting can happen in a narrow strip) would go. Let me give an outline for the case of a strip of height 3. In the following when I say "pattern" I'll mean "pattern of height 3" and when I say "pattern of length n" I mean a pattern of height 3 and width n.

The trick will be to prove that every pattern either eventually goes outside the strip, or eventually settles down. The following definitions will be useful:

• Say a pattern P is bad if any pattern containing P as a subpattern eventually evolves into one with live cells above or below the strip. For example any pattern with three live cells next to each other at the top of the strip is bad because on the next generation a cell will be born above the strip, and in fact this will happen no matter what we put on either side of this pattern. Likewise this

  Code: Select all

  ..o..
  .ooo.
  ..o..

  pattern is bad because in two generations it will evolve outside the strip, and the cell outside the strip is in the middle, so nothing we put at either side can stop it.
• Say a pattern of length 2n+1 is good if it evolves for n generations without a cell ever going above or below the strip in the middle collumn, and if the middle collumn is the same in generation n as it was in generation n-2.

The point of these definitions is that we can prove the following:

Lemma

If for some N we have that every pattern of length 2N+1 is either good or bad, then every pattern (of any length) will after N steps either settle down into a period 2 oscillator or still life, or have left the strip.

Proof

Take any pattern. For each column in the pattern consider the subpattern of length 2N+1 centred on that column. If this subpattern is bad then it will eventually evolve outside the strip. So assume it is good. Then that column will be the same in generations N-2 and N. Since this is true of every column, we have a period 2 oscillator or still life. QED

Okay, so it remains to find such an N. I claim that it can be done by a program with the following psuedocode:

Code: Select all

Set n = 1
loop until we're done{
    list every pattern of length 2n+1 not containing any known bad pattern as a subpattern
    for each such pattern{
        evolve it for n steps
        if it has a cell outside the strip in the middle column{
             mark it bad
        }else if the middle column was the same in generations n-2 and n{
             mark it good
        }
    }
    if all patterns are marked good or bad{
        done. break out of loop
    }else{
         add one to n
    }
}

When I get the chance I'll write the code. I bet it halts with n=6, since this pattern:

Code: Select all

......o......
......oo.....
......o......

looks like it takes the longest to prove bad.

[muzik]

Have any notations for non-totalistic triangular rules been invented?

[drc]

When I get the chance I'll write the code. I bet it halts with n=6, since this pattern:

Code: Select all

......o......
......oo.....
......o......

looks like it takes the longest to prove bad.

Wouldn't there be:

Code: Select all

......o......
......o.o....
......o......

instead?

[Macbi]

Code: Select all

......o......
......o.o....
......o......

Oh yeah, well spotted! That means the code will take longer to run. I think it will still be practical though. It wiill take me a while to get around to it thougb.

[gameoflifemaniac]

Is there a bound for how small a B3/S23 quadratic growth pattern can be?

[Naszvadi]

Is there a bound for how small a B3/S23 quadratic growth pattern can be?

yes, because it is a f:N \to {false, true} function, which has the "f(n)==true => f(n+1)==true" property; and f(n) means that is there a QGP with population "n".

[BlinkerSpawn]

Is there a bound for how small a B3/S23 quadratic growth pattern can be?

Yes, but we don't exactly know what it is.

[fluffykitty]

Is there a bound for how small a B3/S23 quadratic growth pattern can be?

yes, because it is a f:N \to {false, true} function, which has the "f(n)==true => f(n+1)==true" property; and f(n) means that is there a QGP with population "n".

TC;DU If there's a quadratc pattern w/n cells, there's a quadratic pattern with n+1 cells. So,

Yes.

[dvgrn]

Is there a bound for how small a B3/S23 quadratic growth pattern can be?

Yes, but we don't exactly know what it is.

The current lower bound should probably be something like 5x6 or 6x6, but maybe someone can improve on that.

All 6x7 patterns have been exhaustively enumerated. The first such effort was Stephen Silver's in March 2000, to check for oscillators inside small bounding boxes. It's not clear that that survey would have noticed a quadratic-growth pattern, though, since that's not what the program was looking for.

More recently, one of A for awesome's hacked apgsearches would actually notice a quadratic-growth pattern if it saw one.

At least it would get labeled as PATHOLOGICAL -- right? Has anyone attempted 5x6 or 6x6 with that hacked apgsearch, and were there no quadratic-growth results as expected?

The only other hard limit we have that I can think of is an upper limit: there is a quadratic-growth pattern inside a 2596-cell bounding box... specifically, EDIT: a 1-by-2596 box. Or, yes, of course, as Calcyman mentions below, one of the old spacefillers gets us a lot smaller than that (though not thinner!)

[calcyman]

The only other hard limit we have that I can think of is an upper limit: there is a quadratic-growth pattern inside a 7242-cell bounding box... specifically, a 1-by-7242 box.

Max is almost an order of magnitude smaller, with a 729-cell bounding box:

http://www.conwaylife.com/wiki/Max

[drc]

Is it known what the nonomino predecessor of the switch engine that it was first found by is? Because I seem to have refound it:

Code: Select all

x = 6, y = 3, rule = B3/S23
4o$bobo$3b3o!

I seem to remember this being a headsccratcher

[dvgrn]

Is it known what the nonomino predecessor of the switch engine that it was first found by is? Because I seem to have refound it:

Code: Select all

x = 6, y = 3, rule = B3/S23
4o$bobo$3b3o!

I seem to remember this being a headsccratcher

Yup, that's the one. The rumor was that it was a decomino that Charles Corderman noticed. But that doesn't seem to make as much sense, if he was systematically going through the ominoes -- the one nonomino that makes a switch engine would have been found first.

On the other hand, it's vaguely possible that he missed that one, and only noticed the switch-engine behavior when it came around again in the decominoes. I don't think anyone has looked through the 4655 decominoes to find how many of them make clean switch-engine descendants -- maybe there's only one decomino that does that.

[gameoflifemaniac]

Is there a bound for how small a B3/S23 quadratic growth pattern can be?

Yes, but we don't exactly know what it is.

The current lower bound should probably be something like 5x6 or 6x6, but maybe someone can improve on that.

All 6x7 patterns have been exhaustively enumerated. The first such effort was Stephen Silver's in March 2000, to check for oscillators inside small bounding boxes. It's not clear that that survey would have noticed a quadratic-growth pattern, though, since that's not what the program was looking for.

More recently, one of A for awesome's hacked apgsearches would actually notice a quadratic-growth pattern if it saw one.

At least it would get labeled as PATHOLOGICAL -- right? Has anyone attempted 5x6 or 6x6 with that hacked apgsearch, and were there no quadratic-growth results as expected?

The only other hard limit we have that I can think of is an upper limit: there is a quadratic-growth pattern inside a 2596-cell bounding box... specifically, EDIT: a 1-by-2596 box. Or, yes, of course, as Calcyman mentions below, one of the old spacefillers gets us a lot smaller than that (though not thinner!)

I meant the smallest number of cells, not bounding box! But thanks.

[dvgrn]

I meant the smallest number of cells, not bounding box! But thanks.

From the Infinite growth article:

The first quadratic growth pattern constructed was the original breeder, found in 1971 by Bill Gosper. Since then, many other breeders have been found, and even some spacefillers have been constructed. It is unknown how small quadratic growth patterns can be, and a race has been taking place since the early 1990's to construct the smallest such pattern. The current record holder is switch engine ping-pong that consists of 23 cells. Previous record holders include catacryst, metacatacryst, mosquitoes, 26-, 25- and 24-cell quadratic growth.

So 23 cells is the current upper bound for population. But switch engine ping-pong is 210,515×183,739 which doesn't seem exactly "small" --!

The lower population bound is 10 or 11 cells, I think. Paul Callahan showed that there are no infinite-growth patterns with 9 cells, and therefore no quadratic-growth patterns. A 10-cell quadratic-growth pattern seems unlikely, based on simsim314's searches, but based on that posting I'm not sure it's absolutely been ruled out. (?)

[drc]

Can a RRO be built in CGOL by crashing LWSSes into some small, cheap slow orthogonal spaceship like the loafer?
What I'm thinking is that two copies of a recipe that creates and destroys a loafer gun by hitting the back of a loafer are placed, and some sort of copy machine takes in the second copy and produces two clones of it, in a convenient position as to keep with the parity/position of the loafer? How big would said pattern be? Is it even possible?
EDIT: Doesn't have to be a gun, just a perpendicular loafer. probably best if it's LWSSes but it could be anything, I guess. Would this count as 'reflectorless' though?

[dvgrn]

[1] Can a RRO be built in CGOL by crashing LWSSes into some small, cheap slow orthogonal spaceship like the loafer?...
[2] How big would said pattern be? ...
[3] Is it even possible? ...
[4] Would this count as 'reflectorless' though?

1. Yes, an RRO could be made this way.
2. It would be big, but Golly could handle it. The recipe would probably be the same order of magnitude as the Orthogonoid recipe -- meaning, not as much as ten times bigger.
3. Yes, it's possible with more-or-less current technology (but see below).
4. Sure -- it's just a bunch of *WSSes aimed at a loafer, there's no reflector in sight (in that phase, anyway).

We don't have any research done yet on direct single-channel MWSS construction. MWSS streams are the only *WSS signals we can currently build copy-machine circuitry for, that a single-channel recipe can reasonably be run through. I mean, we could build something for LWSSes or HWSSes, but it would be pointlessly bigger until someone discovers a direct H-to-LWSS or H-to-HWSS along the lines of Kazyan's H-to-MWSS.

Variations On the Theme
Technically the recipe aimed at the loafer doesn't have to be single-channel MWSS, though. It could be a slow salvo of *WSSes on different lanes. In that case, the copy machine would have to be just slightly more complicated, with a construction arm that shoots those *WSSes. Presumably it would be followed by a single-channel stream of (a lot more) MWSSes, that encode the elbow-move and *WSS recipes. We have recipes for five out of six *WSS types already, and can dig up the sixth (one of the HWSS parities) if we try hard enough.

However, we don't have any research for slow-salvo constructions of Spartan-ish circuitry using multi-lane slow *WSSes, either. The only way I would know how to build Snarks and syringes and such, right now, would be to create a second "slow elbow", hit it with those *WSSes, and produce slow^2 gliders that do a standard slow-salvo construction. Horribly inefficient, but it could be done.

The alternative would be to run all new searches for direct slow-*WSS constructions. This would be much more interesting... but it would also potentially take years to sort out, similar to the length of time it has taken to develop the tools for slow glider salvos.

Why Not Diagonal?
In any case, it may turn out to be easier to make an RRO with a stream of gliders aimed at a Cordership. Basically it would end up being just a variant of the hypothetical single-channel quadratic replicator in the link -- with a small amount of extra self-destruct circuitry added, and with the straight-ahead output disabled.

You could also think of it as a variant of the self-synthesizing spaceship idea, adjusted very slightly so that the ship moves in a loop instead of a straight line or a zig-zag.

Yes, We Have (Pretty Much) All the Pieces Already
We already have the recipes we need to build and launch Corderships, and shoot them down again with a single-channel recipe leaving a usable construction-arm elbow. The tricky part is that Corderships are so slow that your "some sort of copy machine" might need to have an extra delay mechanism built into it, or else your RRO will end up being just an x1 or x2.

-- Not quite sure how the timing would work out there. We figured out that the delay was definitely needed if a true self-synthesizing spaceship was a requirement -- i.e., if the copy machine has to spit out two full clones of the recipe and then self-destruct, before the front of the first cloned recipe hits the receding Cordership and starts constructing the next copy machine.

[Saka]

Do "inner totalistic" rules exist and what are they?

No. (Not to my knowledge anyway!)

@Saka, they exist now that you've brought them into existence by asking that question.

Sorry for a late and short reply, but I made this:
User:Saka/Inner-totalistic Rules

[dvgrn]

@Saka, they exist now that you've brought them into existence by asking that question.

Sorry for a late and short reply, but I made this:
User:Saka/Inner-totalistic Rules

Looks good... but please don't let that definition escape from your user pages out into the rest of the LifeWiki, without changing the name first -- to "inner-only totalistic" or something like that.

A for awesome pointed out that "inner-totalistic" is actually out there in the literature, as a synonym for plain "totalistic". There's some follow-up in this post. It seems like a pointless and confusing synonym, which is probably why the "inner-" prefix has mostly died out -- it would be a shame to accidentally give "inner-" a new lease on Life.

It's bad enough that "non-totalistic" gets used half the time to mean Hensel neighbors2-format rules (isotropic), and the other half of the time it means the much larger space of MAP rules (anisotropic). Probably it's a losing battle to get everyone to say specifically which type they mean when they say "non-totalistic"... but at least it should be possible to keep "inner-" out of the confusion.

[muzik]

Have any rule integers for outer-totalistic Generations rules been devised?

An obvious option would be to calculate the rule integer of the rule, then add 262144 for each "dying" state in the rule. Brian's Brain would be 262148 by this classification.