Shrinking The 0E0P Metacell

[Anivec]

Here are several ideas on how to reduce the 0E0P Metacell and improve the speed of the metacell:
(1)Improve the current single channel recipe
Using new tools for slow salvos has greatly improved over the past few years, current programs are more likely to find cheaper solutions than more expensive ones. This idea makes more room for both population, bounding box, and speed improvements to the 0E0P. Using the more recent design DOGun SaGaQR, the length of the recipe can be reduced significantly by completely eliminating the need for several rows of snarks on the form of a loop. This will make it more HashLife friendly as noted by Pavgran, but will also increase the bounding box.
(2)Optimize circuitry
The circuitry can be improved as well due to more recent discoveries. The "circuitry" refers to all of the above (e.g. signal circuitry, timing circuitry, self-destruction circuitry, ect.). It might be necessary to take a further look into the circuitry before trying this. Reducing this also improved on recipe length
(3)Change/improve the metacell cycle
The metacell cycle has 22 steps divided across about 2^36 generations meaning that average of each step is about 2^31.5. If someone can get rid of a few steps, then that would subtract a whole lot of generations off of the metacell cycle. This may lead to a change in circuitry but it is worth it.

Feel free to add more thoughts to this because I am willing to do so.
edit on 6/13/24:
Added a suggestion from Pavgran, thanks again for reminding me.

[Pavgran]

As I see it, the 0E0P metacell would be more practical if we get rid of the recipe nucleus and just store the recipe in one loop at the boundary of the cell. That was not an option before, because fast crab-stretching technology has not been invented at the time of 0E0P construction. But now, with the trick similar to the one used in my quadratic replicator (explained a bit in the last part in my post) and better construction technology, we can build a much bigger (in bounding box), but much more Golly-runnable cell.
Not that it would be an easy project, though.

[Anivec]

As I see it, the 0E0P metacell would be more practical if we get rid of the recipe nucleus and just store the recipe in one loop at the boundary of the cell. That was not an option before, because fast crab-stretching technology has not been invented at the time of 0E0P construction. But now, with the trick similar to the one used in my quadratic replicator (explained a bit in the last part in my post) and better construction technology, we can build a much bigger (in bounding box), but much more Golly-runnable cell.
Not that it would be an easy project, though.

Thanks for reminding me of this mechanism used in one of your projects, I completely forgot about this until you brought it up. I’ll add this to my first post in a few minutes.

[Anivec]

I am going to start reworking the stable signal circuitry, then I suggest trying to reduce static population after that, then we work out the timing details, especially for the clock gun(s) or glocks for short. We finally try to reduce the recipe of the whole entire metacell.

[dvgrn]

I am going to start reworking the stable signal circuitry, then I suggest trying to reduce static population after that, then we work out the timing details, especially for the clock gun(s) or glocks for short. We finally try to reduce the recipe of the whole entire metacell.

This is an ambitious project, not at all easy to complete. Before any work is done it would be a good idea to figure out the likely period of the resulting metacell -- and to do that, it will be important to decide whether to hugely shrink the population first -- by implementing Pavgran's suggestion above of creating a prokaryotic 0E0P instead of the current eukaryotic model.

A simple prokaryotic diamond with no nucleus would run an awful lot faster in Golly, no question! It would also make it possible to hugely simplify the master 0E0P clock's current highly convoluted switching system, which currently has stages for building and then populating the Snark chains that line the nucleus, and so forth and so on.

It seems like it might make sense to make a higher priority of maximizing Golly's ability to run the metacell, rather than just arbitrarily shrinking the bounding box.

[Anivec]

This is an ambitious project, not at all easy to complete. Before any work is done it would be a good idea to figure out the likely period of the resulting metacell -- and to do that, it will be important to decide whether to hugely shrink the population first -- by implementing Pavgran's suggestion above of creating a prokaryotic 0E0P instead of the current eukaryotic model.

I'd ask Adam P. Goucher about the switching circuitry in the original 0E0P first, that way we know exactly what we are looking for, and thus what the most optimal design would be for the circuitry, but I am probably getting a head of my self. Is there any good reason why the approximate period of the metacell should be found first and is there any specific method for finding the period?

A simple prokaryotic diamond with no nucleus would run an awful lot faster in Golly, no question! It would also make it possible to hugely simplify the master 0E0P clock's current highly convoluted switching system, which currently has stages for building and then populating the Snark chains that line the nucleus, and so forth and so on.

It seems like it might make sense to make a higher priority of maximizing Golly's ability to run the metacell, rather than just arbitrarily shrinking the bounding box.

I would certainly agree that speed is more prioritized then bounding box, especially if someone want's to see a metacell pattern in Golly.

[dvgrn]

I'd ask Adam P. Goucher about the switching circuitry in the original 0E0P first, that way we know exactly what we are looking for, and thus what the most optimal design would be for the circuitry, but I am probably getting a head of my self.

Nathaniel and I reverse engineered the 0E0P master clock switching system, along with a lot of the other major mechanisms, for the last chapter of the Life textbook. There are a whole lot of details in there. Seems like there's not much point in pestering Adam about anything until you understand all of the details that have been documented already.

Is there any good reason why the approximate period of the metacell should be found first and is there any specific method for finding the period?

If you want to build a prokaryotic 0E0P, then it should be safe to unwind the recipe in the nucleus of the current 0E0P into a huge diamond, find the smallest power-of-two diameter that allows the entire recipe to fit, and figure out what power-of-two period that implies. It would probably be good to then design and build out a master clock at that period.

Eventually it's probably going to be possible to cut the diameter by one or more powers of two, because the recipe will shrink significantly when the extra complexity needed to maintain the nucleus is discarded. So it would be good to include in the master clock design, some way to easily replace pairs of semi-Snarks with regular Snarks -- or maybe remove groups of four semi-Snarks completely? -- to reduce the period of the master clock to match the size of a diamond that fits the actual recipe.

If the new prokaryotic 0E0P still needs to be programmable to emulate any MAP rule, then the 4096-element lookup table is going to stay the same size, and the easiest thing will probably be to keep the part of the current 0E0P mechanism that interprets that lookup table. I mean, you can redesign it if you want, but that would seem like the absolute lowest priority -- first you might as well show that you can complete the redesign of pretty much everything else.

Like I said, this is a very large project.

[Anivec]

I just got the idea to store single channel construction recipes for common circuitry components in the 0E0P metacell, e.g snark, Scrobie splitter. And then if it needs to create a reflector or splitter, it has a whole bunch of them in its memory loops. Although the self destruct sequence may ruin this idea.

Eventually it's probably going to be possible to cut the diameter by one or more powers of two, because the recipe will shrink significantly when the extra complexity needed to maintain the nucleus is discarded. So it would be good to include in the master clock design, some way to easily replace pairs of semi-Snarks with regular Snarks -- or maybe remove groups of four semi-Snarks completely? -- to reduce the period of the master clock to match the size of a diamond that fits the actual recipe.

I’d try finding the period of the new metacell before trying to predict the period of the clock.

If the new prokaryotic 0E0P still needs to be programmable to emulate any MAP rule, then the 4096-element lookup table is going to stay the same size, and the easiest thing will probably be to keep the part of the current 0E0P mechanism that interprets that lookup table. I mean, you can redesign it if you want, but that would seem like the absolute lowest priority -- first you might as well show that you can complete the redesign of pretty much everything else.

Like I said, this is a very large project.

I forgot that the 0E0P metacell had 4096 possible elements, it will take years for that to be completed, unless there is an optimized script for this.

[dvgrn]

I forgot that the 0E0P metacell had 4096 possible elements, it will take years for that to be completed, unless there is an optimized script for this.

There isn't any kind of "optimized script", no. And yes, "years" is a good estimate for the size of this project. For calcyman the original 0E0P was a five-year project (2014-2018) -- absorbing various contributions from other people along the way, like the Snarkmaker recipe or the Cordership-push recipe. But calcyman completed the high-level design for the 0E0P metacell, very nearly singlehandedly.

The metacell's transition tables are awfully important to the functioning of the current 0E0P metacell. It seems like if you want to make any progress on shrinking the design, then before you can really get started you're going to need a thorough checklist of all the pieces that you're intending to optimize. Without a checklist it would be hard to figure out what makes sense to work on first.

If you want to post a candidate checklist here, I can certainly look through it and suggest pieces that might be missing from the checklist.

[apg]

I just got the idea to store single channel construction recipes for common circuitry components in the 0E0P metacell, e.g snark, Scrobie splitter. And then if it needs to create a reflector or splitter, it has a whole bunch of them in its memory loops.

The idea of subroutines is a very appealling one: it features in the original 0E0P metacell for building long lines of Snark pairs to form the boundary of the 'nucleus' that stores the main memory tape.

As far as I know, this is the only project in CGoL to have used subroutines: the overhead of supporting them is sufficiently large that it only becomes worthwhile if you reuse them many times. (The subroutines in the 0E0P metacell are each reused 1024 times if I remember correctly.)

[dvgrn]

As far as I know, this is the only project in CGoL to have used subroutines: the overhead of supporting them is sufficiently large that it only becomes worthwhile if you reuse them many times. (The subroutines in the 0E0P metacell are each reused 1024 times if I remember correctly.)

Theoretically a "Stable Storage 0E0P" design might be able to make efficient use of much smaller subroutines that are used much more often -- along the lines of the "Now build a [Snark|Scorbie Splitter] in orientation such-and-such at (x,y)" that AlbertArmstain mentioned.

Or really large subroutines could become worthwhile even if they're used just a few times each, like "Now build a Complete Metacell Corner starting from the current single-channel arm position".

The thing is, this really will require a complete redesign from the ground up, producing a completely new type of 0E0P -- a general-purpose self-constructing computer with a 2D memory array, with data in the 2D memory that tells it to construct itself.

... And the other thing is, reading a 2D stable memory to retrieve single-channel salvo information is very likely going to be painfully slow. The new Stable Storage 0E0P would need a lot less data to build a copy of itself, because it could use subroutines so much more efficiently -- but compared to the current 0E0P, it might well take a larger number of ticks, to run, and might be no easier to simulate in Golly.

If the goal is an 0E0P metacell that can be run in Golly in a reasonable amount of time, then -- rather counterintuitively -- the odds are quite good that we should go in the opposite direction -- build the huge diamond-shaped metacell that Pavgran has suggested, and just inline everything -- no subroutines at all. (!)

[Anivec]

The thing is, this really will require a complete redesign from the ground up, producing a completely new type of 0E0P -- a general-purpose self-constructing computer with a 2D memory array, with data in the 2D memory that tells it to construct itself.

... And the other thing is, reading a 2D stable memory to retrieve single-channel salvo information is very likely going to be painfully slow. The new Stable Storage 0E0P would need a lot less data to build a copy of itself, because it could use subroutines so much more efficiently -- but compared to the current 0E0P, it might well take a larger number of ticks, to run, and might be no easier to simulate in Golly.

I’ve tried making a spartan version of the Turing machine simulator. The thing is that the time it takes grows slower by O(2^x) for the amount further a bit needed to read is, and that the Turing machine probably doesn’t even work in the first place. I suppose we could use a ECCA so that it accepts input from the memory array, and as a bonus, the ECCA can be periodic because the bits are passed down at a linear rate (unless my O(2^x) design will be used).

[apg]

... And the other thing is, reading a 2D stable memory to retrieve single-channel salvo information is very likely going to be painfully slow.

Yes, if you're using a stable storage mechanism then an ECCA would be a better choice of construction arm than a single channel aimed at a SPEBOE. Single-channel technology is really only worthwhile with a dynamic tape; as soon as you have a stable memory then it would be both easier and more efficient to use a binary encoding scheme.

[Pavgran]

My intuition says that subroutine-based 0E0P would be unnecessarily complicated. All that switching, recipe-retrieving and recipe-storing circuitry, etc that would itself need to be built.
If the design consists of only symmetric shell, (maybe symmetric) glider loop recipe storage, and a core consisting of clock, a bunch of OTTs switching between different recipe targets (building and injecting recipe for 4 neighboring cells), (quite possibly unchanged) state decision circuitry, and a bunch of OTTs controlling destruction, it isn't that big overall. I'd guess 10-50 times bigger than DoGun recipe.
The only new logic I'd add is the ability to adjust the time the cell spends 'looking like a cell', depending on the state. So for the case of emulating 1-state rule cells that represent actual cells stay alive longer than cells that help compute transitions. That additional logic would cost only a few additional OTTs checking for state and triggering early destruction, if necessary. If the design indeed happens to be Golly-runnable, that would be a very nice feature to have.

I've tried to start that project a while ago, actually, and the first and the biggest hurdle I met was designing the exact form of the shell and the loop. As soon as you start thinking about hashlife-friendliness, a lot of restrictions appear. The only way non-parallel glider paths can meet is at single point. So, for example, recipe loops have to be approximately the same order of distance apart as the side length of the loop. All the timings and distances have to be power-of-two compatible. No 180-degree turns anywhere.
As soon as the design of the shell and the loop is established, all the rest is fairly technical engineering work.

[Anivec]

If you want to post a candidate checklist here, I can certainly look through it and suggest pieces that might be missing from the checklist.

What do you think is most important in order? I'd like to see what you think! I already have what I want reduced in order at the very top.

[dvgrn]

What do you think is most important in order? I'd like to see what you think! I already have what I want reduced in order at the very top.

'
Heh, I guess I think of it as the opposite order:

(3) Change/improve the metacell cycle
(2) Optimize circuitry
(1) Improve the single channel recipe

In particular, probably start by just rebuilding the master clock from the ground up. It will still have to activate the transition-table-reading circuitry (and it probably makes a whole lot of sense to just keep that circuitry exactly as it is -- at least, it's not immediately clear to me how to improve it, so that's one less optimization problem to solve! See section 12.8.8 of the Life textbook).

The current 0E0P master clock does all kinds of stuff that a new BigDiamond 0E0P won't have to do -- send signals to activate and deactivate copying mechanisms to fill two memory loops with sub-recipes that build the two sides of the nucleus Snark chains, for example.

Toward the end of each cycle, the master clock puts out a whole series of separate signals, one at a time, to clean up various bits of circuitry. I don't think there's any particular reason why this has to be done in separate stages. I mean, sure, sometimes one piece has to get cleaned up to give access to another piece. But once the cleanup stage is reached, I suspect it would be just a little bit simpler and cheaper -- or, at the very least, conceptually easier to understand -- to build a self-destruct network that cleans up the entire structure (including the master clock) starting from a single output signal.

An obvious place to reduce the period of the metacell is to carefully cut down on the wait time between the "apoptosis" stage and the beginning of the next cycle -- see section 12.8.9. We have to wait _some_ amount of time with the extra von-Neumann-neighborhood helper metacells gone, to get a phase where the metapattern looks like the pattern that's being emulated -- but it's not clear that the delay has to be as large as 112 * 2^29 ticks!

I'm curious about whether there's some clever way to redesign the 0E0P outer shell to reduce the amount of circuitry that has to be built. See section 12.3: "Only one of these arms is actually used; the other three exist only to enforce the rotational symmetry."

... There's a lot more to think about here. But maybe an interesting starting point would be to design an adjustable master clock that will cleanly self-destruct in response to a single (carefully timed) input signal, no matter how it's adjusted or what state its semi-Snarks are in.

If we can get a simplified master clock wired up to existing transition-table-reading circuitry, and make that work equally well for arbitrarily large Hashlife-friendly diamond-shaped memory loops, then it becomes easy to defer the question of exactly how big the memory loop will have to be. It would be nice to be able to make the memory loop smaller at the last minute, after we've sorted out how long the Single Channel Recipe 2.0 really has to be.

[Anivec]

What do you think is most important in order? I'd like to see what you think! I already have what I want reduced in order at the very top.

'
Heh, I guess I think of it as the opposite order:

(3) Change/improve the metacell cycle
(2) Optimize circuitry
(1) Improve the single channel recipe

In particular, probably start by just rebuilding the master clock from the ground up. It will still have to activate the transition-table-reading circuitry (and it probably makes a whole lot of sense to just keep that circuitry exactly as it is -- at least, it's not immediately clear to me how to improve it, so that's one less optimization problem to solve! See section 12.8.8 of the Life textbook).

The current 0E0P master clock does all kinds of stuff that a new BigDiamond 0E0P won't have to do -- send signals to activate and deactivate copying mechanisms to fill two memory loops with sub-recipes that build the two sides of the nucleus Snark chains, for example.

Toward the end of each cycle, the master clock puts out a whole series of separate signals, one at a time, to clean up various bits of circuitry. I don't think there's any particular reason why this has to be done in separate stages. I mean, sure, sometimes one piece has to get cleaned up to give access to another piece. But once the cleanup stage is reached, I suspect it would be just a little bit simpler and cheaper -- or, at the very least, conceptually easier to understand -- to build a self-destruct network that cleans up the entire structure (including the master clock) starting from a single output signal.

An obvious place to reduce the period of the metacell is to carefully cut down on the wait time between the "apoptosis" stage and the beginning of the next cycle -- see section 12.8.9. We have to wait _some_ amount of time with the extra von-Neumann-neighborhood helper metacells gone, to get a phase where the metapattern looks like the pattern that's being emulated -- but it's not clear that the delay has to be as large as 112 * 2^29 ticks!

Makes sense to rebuild the clock first. I’m thinking we could simply get away with a Simkin glider gun instead of a p256 gun.

I'm curious about whether there's some clever way to redesign the 0E0P outer shell to reduce the amount of circuitry that has to be built. See section 12.3: "Only one of these arms is actually used; the other three exist only to enforce the rotational symmetry."

I can’t think of anything right now, but I’ll see if there’s anything that could potentially work in the future.

[dvgrn]

I’m thinking we could simply get away with a Simkin glider gun instead of a p256 gun.

That might save a few bits on the tape if your only goal is to reduce the size (or maybe the complexity) of the 0E0P's Little Brother. But the resulting pattern will probably run quite a lot slower in Golly, and speed seems more important than absolute size.

-- I'm not sure how much of a difference it would make, actually, as long as the period of the entire pattern can still be arranged to be a power of two. But it's a lot harder to build a non-power-of-two clock to enforce a power-of-two overall period, so I suspect that the extra complexity of doing that would more than make up for the tiny savings from using a Simkin gun instead of a p256 as the source of clock pulses.

[Anivec]

I believe it’s possible to construct all of the children replicators by simply using splitters and reflectors. Now, if the recipes are not all the same, an activation glider can be used to poke holes into a recipe and/or reconstruct the alternative missing parts.

EDIT
Opps… I realized that if two metacells nearby both need to construct a metacell in the same spot, this idea would not work. We could potentially make it work using some clever method to signify what metacell is allowed to construct in a certain spot. A metacell could have a transparent lane that can be blocked by an eater, but that may ruin the self destruct sequence.

[dvgrn]

I believe it’s possible to construct all of the children replicators by simply using splitters and reflectors. Now, if the recipes are not all the same, an activation glider can be used to poke holes into a recipe and/or reconstruct the alternative missing parts.

Why would the recipes not be all the same?

And how exactly is constructing "all the children replicators by simply using splitters and reflectors" any different from what the current 0E0P metacell does? That is, what are you considering not using that the 0E0P metacell uses -- maybe Corderships?

One of the biggest pieces of engineering cleverness in the current 0E0P is the way that all child replicators end up precisely synchronized with each other. They all start their construction cycles at the exact same tick. If they didn't, then great^N grandchildren would get out of sync with each other and eventually catastrophically fail to interact correctly.

Any method you choose of constructing the children is going to have to preserve this precise synchronization feature.

[Anivec]

Any method you choose of constructing the children is going to have to preserve this precise synchronization feature.

The original 0E0P metacell uses trombone slides, correct? It seems pretty easy to synchronize the four children with trombone slides, unless there’s something I’m not seeing.

[dvgrn]

The original 0E0P metacell uses trombone slides, correct? It seems pretty easy to synchronize the four children with trombone slides, unless there’s something I’m not seeing.

Sure -- the trombone slides (and other signal routing tricks) have to be a lot longer for some child locations than for others, but it's certainly not an unsolvable problem. The current 0E0P metacell has already solved it.

I'm just asking what your suggestion of "simply using splitters and reflectors" means. What are you suggesting _not_ using, that the current 0E0P metacell does use? I.e., if it's "simply", then what exactly has gotten simpler?

EDIT
Opps… I realized that if two metacells nearby both need to construct a metacell in the same spot, this idea would not work. We could potentially make it work using some clever method to signify what metacell is allowed to construct in a certain spot. A metacell could have a transparent lane that can be blocked by an eater, but that may ruin the self destruct sequence.

Yup. This is another of the engineering issues that the 0E0P metacell design has already solved. If a metacell builds all of its children simultaneously, then there are really tricky problems to solve when two neighbors both try to build a child in the same place at the same time.

But if a metacell builds its children sequentially, in a fixed order -- clockwise from the top, or whatever) -- then it's quite easy to send a single-channel recipe to each prospective child location. If a child metacell is already present, then the target elbow and the recipe aimed at it get harmlessly absorbed. Single-channel recipes being what they are, that doesn't take much more than an eater in the right place.

[Anivec]

Yup. This is another of the engineering issues that the 0E0P metacell design has already solved. If a metacell builds all of its children simultaneously, then there are really tricky problems to solve when two neighbors both try to build a child in the same place at the same time.

We could use an OR gate to solve this. But most of the OR gates don’t keep the correct timing.

[dvgrn]

Yup. This is another of the engineering issues that the 0E0P metacell design has already solved. If a metacell builds all of its children simultaneously, then there are really tricky problems to solve when two neighbors both try to build a child in the same place at the same time.

We could use an OR gate to solve this. But most of the OR gates don’t keep the correct timing.

Does this really need to be solved to make a smaller 0E0P metacell, though?

At the moment I'm completely unclear on every point you've tried to make recently. I've asked several questions to try to clarify what you're suggesting. If you could respond to these questions, that might make this into an actual back-and-forth conversation that could maybe produce some actionable new ideas.

What are you suggesting _not_ using, that the current 0E0P metacell does use? I.e., if you suggest "simply using splitters and reflectors", then what exactly has gotten simpler?

Why would the recipes that you mentioned several posts back not be all the same? What is the specific purpose of the "activation glider" that you described? "an activation glider can be used to poke holes into a recipe and/or reconstruct the alternative missing parts" is much too vague.

Why would we ever poke holes into a recipe? What are the alternative parts you mentioned? Why did these parts go missing? Why do they need to be reconstructed? How exactly would an activation glider accomplish this?

[Anivec]

I'm just asking what your suggestion of "simply using splitters and reflectors" means. What are you suggesting _not_ using, that the current 0E0P metacell does use? I.e., if it's "simply", then what exactly has gotten simpler?

Ah, sorry, I have taken a deeper look into the 0e0p metacell, and I am not thinking clearly. I am reinventing the wheel with such ideas.