Page 1 of 2

Things to be discovered

PostPosted: March 3rd, 2017, 4:20 pm
by Mr. Missed Her
Post ideas for CGOL inventions/discoveries here. Maybe you could get some extra people working on it that way. I'll do my best to update the list here.

Mr. Missed Her:
  • The almost not knightship.
  • The 0E0P unit cell, a unit cell for which the off state is a void. 0E0P is a massive contraction of “Off [0] state encoded with zero cells.”
  • A “wall” or “shield,” an extendable eater that can eat spaceships/other patterns regardless of it’s positioning/trajectory. Bonus: A way to connect sections at an angle without the corners being vulnerable.
  • A “tank,” a spaceship which has “armor” not necessary to the ship’s movement but can absorb gliders and other potentially threatening patterns without sustaining permanent damage.
  • A fully working "twitching ants" telegraph. (With or without max bandwidth.)
Saka:
  • A machine that can receive and "store" gliders in a closed loop and release them when given a signal.
  • A period ≠2 phoenix.
  • A puffer which synthesizes unusual still lifes.
  • A non-oscillating heisenburp.
muzik:
  • Non-trivial oscillators of all periods not yet discovered.
  • Elementary spaceships of speeds c/8-9o and c/8-11d.
  • Elementary knightship, does not neccesarily have to be a derivative of the almost knightship.
  • Elementary 1-D and 2-D replicators.
Kiran:
  • Period 7 rake.
dvgrn:
  • Small (<25x25) stable period-changing 90-degree glider reflector
  • Small (<25x25) Spartan stable 90-degree glider reflector
  • 90-degree elbow for 2c/3 signal wire
    (this would probably solve the unknown oscillator periods and prove omniperiodicity)
  • Double 2c/3 signal to single 2c/3 signal converter
    (would also solve the omniperiodicity problem)
  • Stable small direct G-to-2G
    (would make a good fraction of the gun collection obsolete again)
  • Stable small direct two-state G-to-G switch
    (alternate output gliders sent in different directions)
  • Glider construction recipes for the remaining 16-bit still lifes for which no efficient construction is known
  • Glider construction recipe for an edge-repair spaceship
    (just to make the Heisenburp detector in the link actually "useful"...)
  • Explicit N-glider construction recipe for a mechanism that can construct any glider-constructible object, no matter how large, using a fixed number of gliders.
  • Complete list of all possible distinct three-glider collisions (different sparks or ash)
    (with hashes of each of the ashes, please...)
  • A seed string for a C1 Catagolue soup that produces a loafer or any new spaceship type
  • A freeze-dried waterbear
  • A Garden of Eden with fewer than 45 ON cells, or a proof/search results showing that no such object exists
  • An orphan with fewer than 88 defined cells, or a proof/search results showing that no such object exists
  • A pattern that has great-great-great-grandparents but no great-great-great-great-grandparents
  • 4-cell-high Garden of Eden, or proof that this is impossible
  • quadratic-growth pattern with fewer than 23 cells
  • Compact hot-swappable glider timing adjustment circuits with a continuous range of timings
  • Direct reflector for some *WSS (no intermediate B/glider/Herschel/pi/QB/R stage)
  • Direct small B/glider/Herschel/pi/QB/R to switch engine (swimmer) converter
    [i](swimmers are so slow that this might actually help reduce higher prime-period guns)
  • Direct small HWSS to B/glider/Herschel/pi/QB/R converter
  • Direct small B/glider/Herschel/pi/QB/R to HWSS converter
  • Direct small B/glider/Herschel/pi/QB/R to LWSS converter
  • Direct small B/glider/Herschel/pi/QB/R to MWSS converter
    (no separate signal needed to kill the Annoying Beehive(TM) that usually seems to be inevitable
  • Direct small B/glider/Herschel/pi/QB/R to switch engine (swimmer) converter
Goldtiger997:
  • synthesis of a c/4 orthogonal spaceship
  • syntheses of all oscillators up to 16 bits (2 left)
  • syntheses of any other new speeds of spaceships
  • syntheses of the remaining 20-bit pseudo still-lifes

Re: Things to be discovered

PostPosted: March 4th, 2017, 2:58 am
by calcyman
I'm working on the 0E0P unit cell. I've designed all of the circuitry other than the one-time self-destructions.

Re: Things to be discovered

PostPosted: March 4th, 2017, 1:52 pm
by Mr. Missed Her
calcyman wrote:I'm working on the 0E0P unit cell. I've designed all of the circuitry other than the one-time self-destructions.

Cool! One advantage 0E0P cells would have is that in addition to the state of the metacells being easily visible, very large patterns and the state of metametacells would also be visible. If you were okay with Golly lagging a lot. Also, a 0E0P metaglider could be said to be an actual spaceship.

Re: Things to be discovered

PostPosted: March 4th, 2017, 3:54 pm
by dvgrn
Mr. Missed Her wrote:
calcyman wrote:I'm working on the 0E0P unit cell. I've designed all of the circuitry other than the one-time self-destructions.

Cool! One advantage 0E0P cells would have is that in addition to the state of the metacells being easily visible, very large patterns and the state of metametacells would also be visible. If you were okay with Golly lagging a lot. Also, a 0E0P metaglider could be said to be an actual spaceship.

And a single metacell programmed for B123/S012345678 or any number of similar rules (mostly rather boring rules otherwise...) could be said to be a quadratic-growth replicator. A 0E0P metaspacefiller would fit the bill, too, I suppose, though it seems a little weird somehow that any interruption in the precise pattern of replicators around the edges would interrupt the quadratic growth.

I remember a number of other strange things would also become possible, like a reflectorless rotating oscillator.

It's going to be mighty hard to build a 0E0P metacell that can emulate B0 rules, though...!

Re: Things to be discovered

PostPosted: March 4th, 2017, 4:15 pm
by gameoflifemaniac
When we finally create the 0E0P unit cell, we can create 2D replicators and EVERYTHING!







Wow.

Re: Things to be discovered

PostPosted: March 4th, 2017, 10:55 pm
by Saka
Program it to do B1/S...
----------------------------------
-A machine that can recieve and "store" gliders in a closed loop and release them when given a signal
-Another phoenix
-A puffer which synthesizes unusual still lifes
-Stable Heisenburp

Re: Things to be discovered

PostPosted: March 5th, 2017, 8:05 am
by muzik
- Period 19 oscillator
- Period 23 oscillator
- Period 38 oscillator
- Period 41 oscillator
- True period 34 oscillator
- Elementary c/8 orthogonal spaceship
- Elementary c/9 orthogonal spaceship
- Elementary c/8 diagonal spaceship
- Elementary c/9 diagonal spaceship
- Elementary c/10 diagonal spaceship
- Elementary c/11 diagonal spaceship
- Elementary knightship, does not neccesarily have to be a derivative of the almost knightship
- Elementary clean 1D replicator
- Elementary clean 2D replicator

Re: Things to be discovered

PostPosted: March 5th, 2017, 12:57 pm
by Mr. Missed Her
Saka wrote:-Another phoenix

Suppose you mean one of a period other than 2.
Saka wrote:-Stable Heisenburp

Non-oscillating, right? Then, you could send gliders through whenever you want. It'd be a lot more flexible.
muzik wrote:- Period 19 oscillator
- Period 23 oscillator
- Period 38 oscillator
- Period 41 oscillator
- True period 34 oscillator
- Elementary c/8 orthogonal spaceship
- Elementary c/9 orthogonal spaceship
- Elementary c/8 diagonal spaceship
- Elementary c/9 diagonal spaceship
- Elementary c/10 diagonal spaceship
- Elementary c/11 diagonal spaceship
- Elementary knightship, does not neccesarily have to be a derivative of the almost knightship
- Elementary clean 1D replicator
- Elementary clean 2D replicator

Wow, that's a lot. Hope you're okay if I do some combining.

Re: Things to be discovered

PostPosted: March 5th, 2017, 1:29 pm
by gmc_nxtman
Stable heisenburps already exist. See golly's heisenburp.py, and I also believe that Calcyman constructed one based off a result by Guam in 2013, but I can't seem to find the post.

Re: Things to be discovered

PostPosted: March 5th, 2017, 8:49 pm
by Kiran
Period 7 rake.

Re: Things to be discovered

PostPosted: March 7th, 2017, 7:19 am
by muzik
"All periods not yet discovered" - this should be easy since conduits and the like exist.

Re: Things to be discovered

PostPosted: March 7th, 2017, 8:59 am
by Mr. Missed Her
muzik wrote:"All periods not yet discovered" - this should be easy since conduits and the like exist.

Yeah, but the periods are low periods, being 19, 23, 38, 41, and 34. You'd need some pretty low period conduits, probably even for 34.

Edit: Meant "even for 41," because that's the highest period, but the ordering threw me off.

Re: Things to be discovered

PostPosted: March 7th, 2017, 5:13 pm
by muzik
Mr. Missed Her wrote:
muzik wrote:"All periods not yet discovered" - this should be easy since conduits and the like exist.

Yeah, but the periods are low periods, being 19, 23, 38, 41, and 34. You'd need some pretty low period conduits, probably even for 34.

Meant to say it would be trivial for everything else above those periods.

Re: Things to be discovered

PostPosted: March 7th, 2017, 7:35 pm
by dvgrn
  • Small (<25x25) stable period-changing 90-degree glider reflector
  • Small (<25x25) Spartan stable 90-degree glider reflector
  • 90-degree elbow for 2c/3 signal wire
    (this would probably solve the unknown oscillator periods and prove omniperiodicity)
  • Double 2c/3 signal to single 2c/3 signal converter
    (would also solve the omniperiodicity problem)
  • Stable small direct G-to-2G
    (would make a good fraction of the gun collection obsolete again)
  • Stable small direct two-state G-to-G switch
    (alternate output gliders sent in different directions)
  • Glider construction recipes for the remaining 16-bit still lifes for which no efficient construction is known
  • Glider construction recipe for an edge-repair spaceship
    (just to make the Heisenburp detector in the link actually "useful"...)
  • Explicit N-glider construction recipe for a mechanism that can construct any glider-constructible object, no matter how large, using a fixed number of gliders.
  • Complete list of all possible distinct three-glider collisions (different sparks or ash)
    (with hashes of each of the ashes, please...)
  • A seed string for a C1 Catagolue soup that produces a loafer or any new spaceship type
  • A freeze-dried waterbear
  • A Garden of Eden with fewer than 45 ON cells, or a proof/search results showing that no such object exists
  • An orphan with fewer than 88 defined cells, or a proof/search results showing that no such object exists
  • A pattern that has great-great-great-grandparents but no great-great-great-great-grandparents
  • 4-cell-high Garden of Eden, or proof that this is impossible
  • quadratic-growth pattern with fewer than 23 cells
  • Compact hot-swappable glider timing adjustment circuits with a continuous range of timings
  • Direct reflector for some *WSS (no intermediate B/glider/Herschel/pi/QB/R stage)
  • Direct small B/glider/Herschel/pi/QB/R to switch engine (swimmer) converter
    [i](swimmers are so slow that this might actually help reduce higher prime-period guns)
  • Direct small HWSS to B/glider/Herschel/pi/QB/R converter
  • Direct small B/glider/Herschel/pi/QB/R to HWSS converter
  • Direct small B/glider/Herschel/pi/QB/R to LWSS converter
  • Direct small B/glider/Herschel/pi/QB/R to MWSS converter
    (no separate signal needed to kill the Annoying Beehive(TM) that usually seems to be inevitable
  • Direct small B/glider/Herschel/pi/QB/R to switch engine (swimmer) converter

Re: Things to be discovered

PostPosted: March 7th, 2017, 8:03 pm
by dvgrn
Saka wrote:-A machine that can recieve and "store" gliders in a closed loop and release them when given a signal
-Another phoenix
-A puffer which synthesizes unusual still lifes
-Stable Heisenburp

gmc_nxtman wrote:Stable heisenburps already exist. See golly's heisenburp.py, and I also believe that Calcyman constructed one based off a result by Guam in 2013, but I can't seem to find the post.

Maybe because it was earlier -- 2011? It could be made a lot smaller nowadays -- but so could the 2c/3-wire-based one... just like every other piece of stable circuitry built before 2013.

Actually I think everything on Saka's list already exists, depending on how you define the terms. E.g., if "another phoenix" means "another phoenix found by Catagolue" (in C1?), then yes, we might have to wait a while for that -- but technically there's always another phoenix.

There are lots of puffers that synthesize still lifes of varying rarity and complexity -- need more specifics there too.

If a true stable Heisenburp for gliders is wanted, it doesn't seem like that is ever going to happen -- a stable object can't be made to collapse as a glider goes by it, without disrupting the glider's travel at least temporarily. So the best we're going to do is stable pseudo-Heisenburps for gliders. Things with sparks like *WSSes, especially MWSSes and HWSSes, have a lot more potential for being successfully stable-Heisenburped.

The glider-storage machine could be designed very easily. Its details would depend on the spacing between the input gliders, what the maximum number of input gliders is, etc., etc. But it would probably include a glider/Herschel/maybe-MWSS signal loop, plus a universal regulator if the signal couldn't be trusted to come in at a "safe" time.

There's a sample glider-storage unit in Patterns/Life/Signal-Circuitry/constructor-memory-loop.rle, for example, minus the part about a signal to release the gliders. That could be done by adding a single eater, though, and arranging for a stray glider to hit it after N cycles of the gliders in the storage unit. Or use the universal-regulator mechanism if you don't care which glider comes out first, but want to be able to safely knock out the eater at absolutely any possible time.

Re: Things to be discovered

PostPosted: March 7th, 2017, 10:39 pm
by wildmyron
dvgrn wrote:
  • Glider construction recipes for the remaining 16-bit still lifes for which no construction is known
    (i.e., the 999s not mentioned below that point in the thread)
  • Glider construction recipes for the remaining 16-bit still lifes for which no construction is known
    (i.e., the non-999s not mentioned below that point in the thread)

Is the second point here meant to be "Glider construction recipes with < 16 gliders"?

As for the first point, it's already done. The 999 ones only have no construction recipe in chris_c's database. As I referenced in a question on the Basic questions thread, all 16-bit still lifes are synthesisable, as are 17-bit still lifes and 18-bit still lifes - It's just not clear how and where to find a known synthesis for all of these objects. I'm sure you remember those projects :P.

Re: Things to be discovered

PostPosted: March 7th, 2017, 11:05 pm
by dvgrn
wildmyron wrote:Is the second point here meant to be "Glider construction recipes with < 16 gliders"?

As for the first point, it's already done...

Oops, yeah. I meant to fix those. Thought I had. Now I definitely have. Too many ideas in one list, I guess.

But if that's the only mistake you caught, I figure I'm doing pretty well. Thanks!

Re: Things to be discovered

PostPosted: March 8th, 2017, 2:53 am
by Sokwe
I suggest changing the title of this topic to "Open problems". This would only slightly expand the scope of the discussion. Honestly, I thought we already had an open problems topic, but I can't seem to find it.

Edit: the Game of Life status page and the spaceship search status page give an idea of what still needs to be discovered in various categories.

Re: Things to be discovered

PostPosted: March 8th, 2017, 7:58 am
by dvgrn
Sokwe wrote:I suggest changing the title of this topic to "Open problems". This would only slightly expand the scope of the discussion. Honestly, I thought we already had an open problems topic, but I can't seem to find it...

A search on "grandfather" turned it up -- it was a short-lived thread from back in 2013, when the grandfather problem hadn't been solved yet.

Here's the list, with items removed if they've been discovered since 2013:

from the old 2008 open-problems list, dvgrn wrote:- Find a stable pattern that cannot be constructed from gliders, or prove that, for any stable pattern, there exists a sequence of gliders that interact with it leaving zero live cells.

- Closer to reachable: find p7 and p9 fountains or a p6 superfountain. There are many similar problems of "find an oscillator with this period and a spark that looks like this" that remain unknown.

- A 3c/6 (c/2) spaceship that's entirely period 6.

- A constructed c/3 rake of around period 144 or less.

- More c/4 orthogonal puffers based on Paul Tooke's p168 puffer.

- Ways convert diagonal signals (lightspeed or otherwise) to/from orthogonal signals.

- A period 8 c/4 diagonal glider stream "fuse" that accepts gliders from a p8 backward rake, and emits an equivalent stream. [I've edited this a bit, maybe wrongly, but I think it makes sense...]

- How much can the population grow in n generations? I.e. if generation 0 has population P and generation n has population Q, how large can Q/P be? For n=1, Q/P can be arbitrarily close to, but not equal to, 3. Unknown for any larger n.

- Consider a particular cell within a pattern, and look at the sequence of its states in gen 0, gen 1, ... Can every finite sequence of bits occur as such a sequence? (If every finite sequence can occur, then so can every infinite
sequence.)

- Is there a still-life which is annihilated by any single glider which hits it? How about just every glider from one particular direction? (Such a thing would be useful for protecting a pattern from random glider attacks.)

- Very ambitious: find a termination for a 2c/3 signal wire that emits a glider directly.

- There's also a whole bunch of minimization problems: the "smallest" patterns with particular properties. "Smallest" can be taken to mean initial number of on cells, area of bounding rectangle, diameter..., restrictions can be imposed (symmetries, confinement to a single row/column, consisting only of gliders), and pattern properties include being a spaceship with a specific velocity, growing for ever, growing for ever in various ways (quadratically, sublinearly, with t log(t)...), being a GoE, being grandfatherless... A few of these are solved, but most are not.

Re: Things to be discovered

PostPosted: March 8th, 2017, 6:42 pm
by gmc_nxtman
dvgrn wrote:
gmc_nxtman wrote:Stable heisenburps already exist. See golly's heisenburp.py, and I also believe that Calcyman constructed one based off a result by Guam in 2013, but I can't seem to find the post.

Maybe because it was earlier -- 2011?


Oops... :oops:

Re: Things to be discovered

PostPosted: March 14th, 2017, 4:44 am
by Saka
Glider spacer machine
For example, feed this to the machine:
x = 12, y = 12, rule = B3/S23
10bo$10b2o$9bobo4$4b3o$6bo$5bo$2o$b2o$o!

To turn it into this:
x = 11, y = 11, rule = B3/S23
8b3o$10bo$9bo2$4b3o$6bo$5bo2$3o$2bo$bo!

Re: Things to be discovered

PostPosted: March 14th, 2017, 9:54 am
by Mr. Missed Her
dvgrn wrote:
  • Small (<25x25) stable period-changing 90-degree glider reflector
  • Small (<25x25) Spartan stable 90-degree glider reflector
  • 90-degree elbow for 2c/3 signal wire
    (this would probably solve the unknown oscillator periods and prove omniperiodicity)
  • Double 2c/3 signal to single 2c/3 signal converter
    (would also solve the omniperiodicity problem)
  • Stable small direct G-to-2G
    (would make a good fraction of the gun collection obsolete again)...

Wow, that's a lot. So much that I didn't include it all in the quote.
Anyways, with people adding this many items, we might need to pick a few that we want to focus on before we're sifting through seas of suggestions.

Re: Things to be discovered

PostPosted: March 14th, 2017, 11:35 am
by drc
What about a Universal Constructor-based Life Chess game? Okay that's too complicated scratch that.

Re: Things to be discovered

PostPosted: March 14th, 2017, 3:06 pm
by gameoflifeboy
Saka wrote:Glider spacer machine
For example, feed this to the machine:
x = 12, y = 12, rule = B3/S23
10bo$10b2o$9bobo4$4b3o$6bo$5bo$2o$b2o$o!

To turn it into this:
x = 11, y = 11, rule = B3/S23
8b3o$10bo$9bo2$4b3o$6bo$5bo2$3o$2bo$bo!


There is something called a regulator, which takes gliders in arbitrary positions (along the same lane, unlike your example), and from what I can tell, "rounds" the generation of each glider to the nearest multiple of n, so that they come out multiples of n generations apart.

Recently a stable universal regulator was constructed. It can be fed with a gun (from the NW) and turn an input stream of gliders spaced sufficiently far apart (from the SW) into a stream with any period at least 1177, depending on the period of the gun provided.

Re: Things to be discovered

PostPosted: March 14th, 2017, 4:14 pm
by dvgrn
gameoflifeboy wrote:
Saka wrote:Glider spacer machine...

There is something called a regulator, which takes gliders in arbitrary positions (along the same lane, unlike your example)...

There's another something called a highway robber.

A big enough bank of highway robbers, with a regulator for each, could catch any number of gliders traveling in the same direction inside a specific bounding box (size of box and number of gliders chosen when the Glider Spacer Machine is built). The regulated outputs could trivially be interleaved to produce a safe p30- or p46-reflectable stream, or whatever you want.

Would need a very specific use case to build an example of one of these things, though. It would get very large and silly-looking very fast.

Also I think we don't have a completed highway robber that's "safe" for gliders following each other at 14 ticks. There are bait still lifes that can handle that spacing, but the circuit needed to reconstruct the bait would be painfully large and slow, compared to existing highway robbers that are _almost_ as good anyway...!