Thread for advanced questions

[PK22]

Can/does there exist an isotropic CA which supports universal construction but not universal computation? In other words, building a Turing machine should be provably impossible, but building a universal constructor should be provably possible.

[b-engine]

Can/does there exist an isotropic CA which supports universal construction but not universal computation? In other words, building a Turing machine should be provably impossible, but building a universal constructor should be provably possible.

Probably not. One may invent logic by colliding self-constructing spaceships.
Running CA involves decisions (a.k.a transitions). Decision is a key to Turing machine.

[dvgrn]

Can/does there exist an isotropic CA which supports universal construction but not universal computation? In other words, building a Turing machine should be provably impossible, but building a universal constructor should be provably possible.

I'm hesitant to try to answer this one definitely, because it hinges on the definition of "universal construction" which doesn't necessarily mean the same thing in every isotropic CA.

It seems like it might be possible -- somehow, not sure how! -- to technically check the box of "construct anything that's constructible" for a given CA, with some mechanism that's designed in and highly specific to the CA, that doesn't allow for the existence of logic gates.

[PK22]

I'm hesitant to try to answer this one definitely, because it hinges on the definition of "universal construction" which doesn't necessarily mean the same thing in every isotropic CA.

For the purpose of the question, a rule that supports universal construction is one which features a pattern capable of creating an unlimited variety of patterns given the right input, including itself.
EDIT:

Running CA involves decisions (a.k.a transitions). Decision is a key to Turing machine.

I don't see how this proves or disproves anything, since not all CA are Turing complete - class 1 CA cannot be, even though they can involve transitions.

In terms of an actual design for universal construction in this hypothetical rule, I think that it will have to be done using wire-based construction, similar to JVN29. If there is spaceship-based construction, it likely implies the existence of splitters, reflectors, and probably spaceship logic as well. A custom rule similar to Wireworld, but with construction capabilities and something to prevent signal logic (e.g two signals mutually destruct if they get too close) might work.

[dvgrn]

For the purpose of the question, a rule that supports universal construction is one which features a pattern capable of creating an unlimited variety of patterns given the right input, including itself.

Now I'm thinking it's "the right input" that needs a little clarification. XOR rules are kind of a degenerate case where an empty universe creates itself, and you can certainly make an infinite variety of other patterns by just scattering whatever cells you want into empty space.

I'm not saying that that's an interesting solution to the non-Turing-complete universal-construction-supporting problem.

However, there might be a way to design a CA somewhat based on that idea, that would be somewhat interesting -- depending on what you mean by "isotropic CA". I'm thinking maybe something along the lines of PrintLife2, but printing in a rule that doesn't support logic gates. I'm not seeing yet either how to provably prevent Turing machines, or how a universal constructor pattern could print a copy of itself with the right input -- and also PrintLife2 isn't even isotropic, of course! -- but the space of clever possibilities is huge enough that it's not clear that those specs can't both be satisfied.

Read literally, "isotropic CA" just means a CA where patterns work the same no matter how your rotate or reflect them. Grids other than square grids, ranges greater than 1, neighborhoods other than Moore, and any number of states can still support isotropic CAs.

Is that the CA-space you meant? Or did you mean specifically two-state range-1 Moore-neighborhood CAs (for example)?

[Resu]

Would viewtopic.php?p=213137#p213137 actually be a moving sawtooth, as it moves in two directions, not just one?

[PK22]

Would viewtopic.php?p=213137#p213137 actually be a moving sawtooth, as it moves in two directions, not just one?

I think so - all of its parts are moving, and it is a sawtooth. Therefore, it can be called a moving sawtooth.

Now I'm thinking it's "the right input" that needs a little clarification. XOR rules are kind of a degenerate case where an empty universe creates itself, and you can certainly make an infinite variety of other patterns by just scattering whatever cells you want into empty space.

In this case, I would define 'input' as a signal or set of signals that can approach from infinity, with each signal moving in a single direction (which can be oblique, orthogonal, or diagonal). The type of signal does not matter provided it can be interpreted by the constructor - it could be spaceships, wire signals, peturbations in an agar, etc.
It also makes sense to add the limitation that the constructor must have population > 0.

Also, the question was referring to any rule invariant under rotation and reflection - there might be an INT range-1 Moore rule with universal construction but not computation, but with 2^102 rules to search, we probably will not find it until someone builds a rulegolfing supercomputer. I still think a wire based rule could work, with a set of cellstates to represent operations (e.g extending the wire, turning it, retracting it, leaving a dot, etc.) and a range 2 VN neigbourhood to detect the end of a wire and execute the operation. Signals could mutually annihalate if they got too close, or maybe cause uncontrolled quadratic growth.

EDIT: Fixed potentially unclear meaning.

[dvgrn]

Would viewtopic.php?p=213137#p213137 actually be a moving sawtooth, as it moves in two directions, not just one?

I think so - all of its parts are moving, and it is a sawtooth. Therefore, it can be called a moving sawtooth.

However, it's often a good idea to look at previous uses of a term and see if it looks like the new use really fits the intended meaning.

In this case, moving sawtooth points to sawtooth patterns that actually move, in the sense that the entire patterns eventually travel arbitrarily far from their original locations. That's not true of this "growing-in-two-opposite-directions sawtooth".

Personally I wouldn't apply "moving sawtooth" to a pattern that is growing in this kind of way, any more than I'd call a period-256 glider gun a "moving gun" just because one of its components moves. To make a "moving gun", I think the pattern as a whole needs to change location (but then "rake" is the traditional term for that anyway). Same for a "moving sawtooth" (in my opinion).

EDIT: I suppose a better example would be that it wouldn't seem very appropriate to call a volatility-1 oscillator a "moving pattern" just because it doesn't have any permanent stationary pieces.

[dbell]

There is a sense that a sawtooth of the type in my recent post really is moving.

No matter what finite region you specify in the Life plane, the pattern will move totally outside of it. It's true that for some regions it will come back inside again. But then it always goes back outside again.

So I would therefore definitely call such a pattern moving, it just has two parts.

But I agree it's not as elegant as a pattern that leaves any area forever.

Maybe a new term could be used such as a 'sawtooth spaceship', similar to the existing term 'growing spaceship', for the nicer types of sawtooths.

BCNU,
-dbell

[dvgrn]

There is a sense that a sawtooth of the type in my recent post really is moving.

No matter what finite region you specify in the Life plane, the pattern will move totally outside of it. It's true that for some regions it will come back inside again. But then it always goes back outside again.

So I would therefore definitely call such a pattern moving, it just has two parts.

But I agree it's not as elegant as a pattern that leaves any area forever.

Well, with this definition of "moving sawtooth" as justification, the latest record-minpop moving-in-two-opposite-directions sawtooth has gotten added to the moving sawtooth page. It still seems kinda like comparing apples and oranges to me, but I won't bother my head about it any more ... after I say this:

For other types of moving sawtooths (sawteeth?), if you pick a bounding box in the Life plane that initially contains the sawtooth, the moving sawtooth's bounding box will eventually move permanently out of that bounding box, and stay out. For everything that was previously labeled a "moving sawtooth", the bounding box center is actually moving. For this "growing sawtooth", the bounding box center is pretty much stationary. It just doesn't seem to me like the pattern as a whole is really "moving".

[dbell]

> Well, with this definition of "moving sawtooth" as justification ...

The new moving sawtooth is not changing the definition of moving.

I originally built one like it in 2017 (viewtopic.php?f=2&t=576&p=53092&hilit=m ... oth#p53092), and several other ones since then.

Nobody complained about the old ones, so why now?

I repeat, maybe adding a definition something like 'sawtooth spaceship' would be useful.

Then the more desirable sawtooths could be separated out into their own category.

BCNU,
-dbell

[Resu]

Should there be a distinction between sawtooth with no stationary parts, and a sawtooth that moves in one direction as a whole (leaving any area forever) , and without any stationary parts? However, any patterns that fit in the second category will also fit in the first category.

[dvgrn]

I originally built one like it in 2017 (viewtopic.php?f=2&t=576&p=53092&hilit=m ... oth#p53092), and several other ones since then.

Nobody complained about the old ones, so why now?

No good reason, I guess. Maybe in 2017 there wasn't the same focus on minimum-population moving sawtooth patterns, so the exact boundaries of the category didn't make any difference to the record-setting side of things.

Should there be a distinction between sawtooth with no stationary parts, and a sawtooth that moves in one direction as a whole (leaving any area forever) , and without any stationary parts? However, any patterns that fit in the second category will also fit in the first category.

Yup, David Bell has suggested "sawtooth spaceship" for growing spaceships with sawtooth population patterns. Just plain "sawtooth" can mean any kind of sawtooth, so maybe "expanding sawtooth" would be a way to specify the non-sawtooth-spaceship category?

[Resu]

Yup, David Bell has suggested "sawtooth spaceship" for growing spaceships with sawtooth population patterns. Just plain "sawtooth" can mean any kind of sawtooth, so maybe "expanding sawtooth" would be a way to specify the non-sawtooth-spaceship category?

Well, this is a sawtooth, and the bounding box is forever expanding ...

Code: Select all

x = 68, y = 76, rule = B3/S23
3o56b2o$o58b2o$bo2$56b2o$56b2o8b2o$7b2o57bo$7b2o50b2o6bo$59b2o5b2o2$10b
2o54b2o$2o8b2o55bo$bo61bo$o6b2o53bo3bo$2o5b2o55b2o2$2o$o$4bo43b3o$bo3b
o41bo2bo$2b2o43bo3bo$46b2obobo$46b2ob2o$47b3o$17b3o$17bo2bo$16bo3bo29b
2o$16bobob2o27bo2bo$17b2ob2o25b5o$18b3o25b2ob3o$46b3o$47bobo$16b2o22b
o7b2o$15bo2bo10bo8b3o$16b5o8bobo5bo$16b3ob2o7b2o6b2o$19b3o$18bobo$18b
2o15bo$34bobo$29bo3bo3bo$27b2o5b3o$28b2o2b2o3b2o11$7b4o24b2o$5b2o4b2o
22b2o$5b2o5bo$7b2obobo$12bo9bo4bo$8bo3bo7b2ob4ob2o$8bo4bo8bo4bo$10b3o
3bo$10b2o4bo$16b2o$18bo$18b3o3$21bo$20bob5o$19b2o5bo$19b2o3bo2bo$27bo
$21b2obo2bo$24bo2bo$25b2o$25b2o!

The term "expanding sawtooth" could cause some confusion.
(Sawtooth 177 with a gilder)

[dvgrn]

The term "expanding sawtooth" could cause some confusion.
(Sawtooth 177 with a gilder)

... Yeah ... but only in the same sense that pretty much any CA terminology could cause come confusion. There are very often edge cases that are hard to decide, but that doesn't necessarily make a term not-useful.

In this case, yes, the bounding box of your pattern is forever expanding -- and if the glider were going NE instead of NW, the bounding box would be forever expanding in all directions, just like an expanding sawtooth.

But the sawtooth's bounding box is still doing the same thing it always does -- it's tethered at one corner and expanding indefinitely in the opposite corner. Adding a glider doesn't make a sawtooth into an expanding sawtooth -- it just means the pattern actually is a sawtooth-plus-a-glider, exactly as you described it.

EDIT: Aha, I've discovered some more minor evidence that I'm not the only one likely to be confused by a label of "moving sawtooth" for a sawtooth where the parts move in opposite directions. The moving sawtooth article written by Nathaniel in 2009 starts with

Moving sawtooth is an orthogonal sawtooth with expansion factor 3 that was found by David Bell on July 10, 2005. Its minimum infinite repeating population is 1239, and it is notable because it and its slight modifications are the only known sawtooths that move.

This could just be my own personal interpretation, but I'm suspecting that "move" is used there in the sense of "the entire pattern moves in the same direction".* Otherwise it would likely have been described more like "the only known sawtooth made up entirely of parts that move".

In any case, that last clause isn't true any more -- will need some kind of update to match current reality.

* It should be possible to make a sawtooth with two parts that are receding from each other at 90 degrees -- right? Not an easy trick, though. I don't think I've seen that variation in practice yet.

[b-engine]

Is there any 60x period multiplier besides combination of 5x and 12x multipliers?

[dvgrn]

Is there any 60x period multiplier besides combination of 5x and 12x multipliers?

Are there any other restrictions on this question, besides that it can't be composed of a 5x mechanism combined with other multipliers?

For specific periods I think that "elementary" 60x multipliers could be constructed -- in particular there might be an LCM-type solution for any sufficiently large period that's relatively prime to 60. Is it a requirement that the period multiplier has to work for any sufficiently large period, or might an LCM solution be interesting? Are you assuming glider inputs?

[b-engine]

Are there any other restrictions on this question, besides that it can't be composed of a 5x mechanism combined with other multipliers?

More broadly, it shouldn't be composed by other multipliers.

Is it a requirement that the period multiplier has to work for any sufficiently large period, or might an LCM solution be interesting?

The 60x multiplier would accept p60 and p3600 input.

Are you assuming glider inputs?

Yes. This would be connected to a p60 glider gun.

[dvgrn]

The 60x multiplier would accept p60 and p3600 input.

Maybe someone can come up with a clever trick, but I'm thinking the p60 requirement might make things a bit tricky -- it's just a little too low a period to allow an easy engineered solution, starting with a conversion to a non-glider signal type that might be more amenable to building a direct x60 pulse divider. Even a speed tunnel is just barely too slow to recover.

Similarly, confocaloid's and EvinZL's experiments with stable crystal variants stop working around period 72, if I remember right. It might be possible to extract a glider faster somehow with period-60 technology -- e.g., a suppressed p60 gun that gets un-suppressed momentarily when the crystal grows to the right spot. But then I don't remember if there's a way to hack the crystal sequence to get a 60x pulse divider, so that might require some more bolt-on engineered adjustment mechanisms.

[Resu]

What would this pattern be considered to be? is it a waveguide?

Code: Select all

x = 52, y = 102, rule = B3/S23
50bo$49bobo$48bobo$47bobo$46bobo$45bobo$44bobo$43bobo$42bobo$41bobo$40b
obo$39bobo$38bobo$37bobo$36bobo$35bobo$34bobo$33bobo$32bobo$31bobo$30b
obo$29bobo$28bobo$27bobo$26bobo$25bobo$24bobo$23bobo$22bobo$21bobo$20b
obo$19bobo$18bobo$17bobo$16bobo$15bobo$14bobo$13bobo$12bobo$11bobo$10b
obo$9bobo$8bobo$7bobo$6bobo$5bobo$4bobo$3bobo$2bobo$bobo$obo$obo$bobo
$2bobo$3bobo$4bobo$5bobo$6bobo$7bobo$8bobo$9bobo$10bobo$11bobo$12bobo
$13bobo$14bobo$15bobo$16bobo$17bobo$18bobo$19bobo$20bobo$21bobo$22bob
o$23bobo$24bobo$25bobo$26bobo$27bobo$28bobo$29bobo$30bobo$31bobo$32bo
bo$33bobo$34bobo$35bobo$36bobo$37bobo$38bobo$39bobo$40bobo$41bobo$42b
obo$43bobo$44bobo$45bobo$46bobo$47bobo$48bobo$49bobo$50bo!

[PK22]

1). How do self-constructing patterns such as the 0E0P metacell and SSOL construct a storage mechanism large enough to store their recipe?

2). What would be the easiest/simplest (in terms of knowledge, skill, and effort required) method to create a quadratic replicator smaller (in bounding box and/or population) than the 0E0P metacell? It seems like we have the technology to create a smaller quadratic replicator.

[dvgrn]

1). How do self-constructing patterns such as the 0E0P metacell and SSOL construct a storage mechanism large enough to store their recipe?

2). What would be the easiest/simplest (in terms of knowledge, skill, and effort required) method to create a quadratic replicator smaller (in bounding box and/or population) than the 0E0P metacell? It seems like we have the technology to create a smaller quadratic replicator.

1) construction of memory loops --
0E0P
The 0E0P was completed in 2018, before we had fast crabstretcher technology, which can push the construction site away from the source at speeds approaching c/4. In the 0E0P, long-distance target and elbow pushes were done by building and shooting down Corderships, which travel at c/12. This meant a lot of gaps in the recipe that were basically just waiting for a Cordership to get far enough away -- and for that and other reasons, the recipe ended up being very long.

The 0E0P had to build its storage mechanism with a pair of subroutines that were repeated many times to construct a tightly packed "nucleus", a back-and-forth glider path with Snark reflectors along its edges. The size of the 0E0P was chosen to be the smallest possible size that was big enough for a diamond-shaped nucleus to fit inside that could hold the entire recipe.

0E0P's Smaller Sibling?
There's been enough progress in self-constructing circuitry since 2018 that a significantly smaller-in-bounding-box 0E0P metacell could be constructed, especially if it was designed to be simpler and less ambitious about the number of different rules it could be programmed to emulate. But it still wouldn't run in Golly well, because the tightly packed back-and-forth streams in the nucleus can't be simulated efficiently in HashLife.

So ... there's a rebuild of the 0E0P metacell somewhat in progress at the moment, but one big idea being investigated is actually to make the bounding box enormously larger, not smaller -- in such a way that there don't have to be any tightly packed boustrophedonic streams, and so it will run well in Golly regardless of the size.

SSOL
The self-synthesizing oblique loopship uses pretty much the latest technology to build its memory loops. c/4 crabstretchers can extend a construction arm at nearly the same speed as the glider-stream data that the loop will eventually contain. So it's fairly easy to set up a single-channel recipe that creates a diamond-shaped loop -- you don't have to wait around for a long time for the construction to be finished before you can start using it.

The SSOL design follows the common pattern where a second copy of the recipe follows directly behind the first. The second copy of the recipe enters the loop, goes around it twice while emitting two copies of itself in two different directions -- and then the memory loop blocks itself off, shuts down and self-destructs.

2) other options for quadratic replicators --
We do already have a smaller-by-population quadratic replicator, Pavgran's DOGun SaGaQR. It uses double crabstretchers in a clever way to quickly create all of the target objects needed for universal construction -- see the animation in the last RLE block in Pavgran's post here.

DOGun SaGaQR is 64 times larger in bounding box area than the 0E0P metacell, but it has less than a twentieth of the population, and runs enormously faster in Golly.

It's definitely possible now to build a quadratic replicator smaller than DOGun SaGaQR. We could save a tiny bit by removing its ability to shapeshift. But we could save a lot more by doing some fresh research into making single-channel recipes more efficient, in a number of different ways. Besides the ones mentioned in the link, it would probably be helpful to rebuild Snarkmaker recipes -- there are known ways to cut the current cost of a Snarkmaker by more than half.

A Hideous Option That Hasn't Been Tried Yet
It's technically possible to build a quadratic replicator that is smaller than the 0E0P metacell and runs about as well in Golly HashLife as DOGun SaGaQR does. The trick would be to build a memory loop that isn't just a simple diamond-shaped loop. But instead of a tight back-and-forth path like the 0E0P (which HashLife can't handle) the idea would be to keep the glider stream circulating in the same direction -- spiraling in toward the center, let's say, and then crossing back to the outside again.

There would be some loss of efficiency from having to be very careful about lining up the gaps in single-channel sub-recipes so that the whole recipe could pass through itself safely. And the place where all the crossings happen would still cause a lot of trouble for HashLife -- but it would be tolerable, unlike a stack of N tightly spaced back-and-forth streams which is about N times as bad as a single set of crossings (in terms of the total number of hashtiles needed).

So the population record and the bounding-box record and maybe the time-for-a-metacell-to-complete-a-cycle-in-Golly record for quadratic replicators could all be broken by the same hypothetical pattern. But the new 0E0P design with just a huge simple diamond-shaped loop seems much more elegant, so nobody so far has really buckled down to finish a new design that minimizes the bounding box.

I think we'd all much rather be able to see the replicator "run away" in Golly ... once you're zoomed out to a scale where you can see a whole replicator, it just doesn't make much difference (either to Golly or to someone looking at Golly) how many powers of two the zoom level is set to.

[Tawal]

Is there an interest to compress Single Lane Channel ?

Example:
This SLC (i.e. Single Lane Channel) used in Spiral growth by Dave Greene has min-max steps 90-341.
Its duplicator appendage has a repeat time time of 84.
So without changing the structure, the Single Lane Channel can be compressed to fit a 'say p84' stream.
This stream can also be compressed to fit a p61 duplicator or at the minimum at p43 (fit Snark RT)

Patterns are in attachments.

Edit: Subsidiary question
I defined Gliders like that (Golly python) :

Code: Select all

# NW Gliders                                    binaries       decimal
GLIDERS = [                    # Table :     XXX     parity     index   -  What is XXX ? It's not 'colour' neither 'phase'
    g.parse("b2o$2o$2bo!"),    #              0        0          0
    g.parse("3o$o$bo!"),       #              0        1          1
    g.parse("bo$2o$obo!"),     #              1        0          2
    g.parse("2o$obo$o!")       #              1        1          3
]

How do you call the most significant bit (i.e. XXX) ?
In order GLIDERS are :

Code: Select all

x = 33, y = 3, rule = B3/S23
b2o7b3o8bo8b2o$2o8bo9b2o8bobo$2bo8bo8bobo7bo!

[dvgrn]

Is there an interest to compress Single Lane Channel ?

Yes, I'd say there's some interest in doing that. I outlined some of the ways to do that in the previous message.

As you mention, for structures like the spiral-growth pattern that use single-channel methods to construct something, but that don't have to construct their own circuitry, we could use minimum 84-tick separation, or now even minimum 61-tick separation if we made careful use of speed tunnels and the fast splitter HRx65R -- there's been some discussion of this in this thread recently.

The biggest optimization to the spiral-growth would involve re-searching for new "SingleChannel61" recipes with 61-tick instead of 90-tick separation -- there will be quite a few more of them, so they'll be more efficient -- and then also search for a more efficient Snarkmaker, by having a small ash cloud directly emit all of the required gliders, instead of emitting just one glider and then working the ash back to a single 0-degree elbow block every time. Going back to a block between every 0-degree glider is an efficiency loss of about 50%.

A spiral-growth pattern could be really significantly smaller with those two optimizations.

I don't _think_ there's much point in doing a similar set of searches with "SingleChannel43" (but somebody can please correct me if I'm wrong). We don't yet have an efficient way to duplicate a glider stream where gliders' minimum separation can be less than 61 ticks. So we could make an impressively compact recipe with "SingleChannel43", but we could only use it once.

... Unless we stored it in two separate glider loops and used a fast inserter like RNE-19T84 to interleave copies of the two sets of gliders (easy to do with syringes or speed tunnels if each loop contains just alternate gliders from the full recipe). That should allow for fairly compact storage, but maybe not quite as compact as a single spiral containing the best possible SingleChannel61 recipe.

Not sure about that, though! Once we have search code that can find single-channel recipes for any chosen minimum separation, maybe we should build libraries for both SingleChannel61 and SingleChannel43. Technically SingleChannel61 is just a filtered subset of SingleChannel43, though, so it probably does make sense to focus on SingleChannel43.

[Tawal]

Is there an interest to compress Single Lane Channel ?

Yes, I'd say there's some interest in doing that. I outlined some of the ways to do that in the previous message.
[…]

OK, I understand that the actual SnarkMaker is not the most efficient.
Until we have better recipes, I've made a python script to compress a Single Lane Channel.