Improved bit-loop-to-stream copier for Margolus Critters

[pcallahan]

This seems worth its own post (added: and a new thread), since it's an improvement over the clumsier loop bit copier I posted earlier this year, and because it is now viewable with Chris Rowett's LifeViewer enhancements. This is the first CA program I've used that really supports non-trivial pattern development for Critters. I may have found a new hobby (like I need one).

I have posted component details in two other threads, but to summarize, this starts out with a period-32 stream of gliders. Since Critters cannot create new cells from nothing, this stream is given as an input using PASTET. In the Critters universe, you can think of it as a stream going back to infinity. Everything else is part of the pattern.

Code: Select all

x = 203, y = 152, rule = critters
#C [[ RLE input o$bo$bo$o! ]]
#C [[ PASTET EVERY 32 ]]
#C [[ PASTE input -16 50 ]]
23$105b2o$105b2o7$102bo$101bo$53b2o$53b2o$125b2o$125b2o3$55bo2bo2$56b
2o6$89b2o$89b2o3$bo15bo15bo15bo9bo21bo9bo$2bo15bo15bo15bo9bo21bo9bo6b
o$2bo15bo15bo15bo9bo21bo9bo6bo22bo$bo15bo15bo15bo9bo21bo9bo29bo3$83bo
54bo$84bo52bo3$49bo2bo119bo$50b2o119bo3$89b2o20b2o62b2o$89b2o20b2o62b
2o3$167bo2bo2$47b2o119b2o$47b2o3$131b2o$131b2o7$168b2o$167bo2bo17$167b
o2bo2$168b2o12$168b2o$167bo2bo11$127bo12bo$128bo9bo$128bo9bo$127bo12b
o$111b2o62b2o$111b2o62b2o3$116bo54bo$115bo56bo!

The purpose of this pattern is to demonstrate a non-trivial data-manipulation in Critters. It contains a recirculating loop of the bits 01101000 (any other 8-bit loop works). Each bit consists of a pair of gliders phase-shifted to admit 90° turns, so the bit periodicity is 64. The rest of the pattern manipulates the input stream into an appropriate stream of phase-shifted pairs and uses it to read the bit loop as a periodic stream 011010000110100001101000...

Because of glider conservation, there needs to be a glider pair for 0 as well as 1. I have adjusted the output using 90° turns so it is reminiscent of a square-wave signal moving to the right. You can watch it in reverse and see it reconstruct the original uniform stream from the output (note this is not an undo history, but the same rules).

UPDATE: This is fairly trivial, but I didn't think of it until studying the pattern in reverse (and maybe it's known, but I can't find a lot of known results for specific Critters patterns). If two gliders in a stream are out of phase by 8n+4 steps, they can be reflected 90° using a two of the reflectors initially used to convert the stream.

Code: Select all

x = 35, y = 20, rule = critters
6$21bo2bo3$3bo9bo$4bo9bo14bo$4bo9bo14bo$3bo9bo!

I was so fixated on getting 8n+2 and 8n+6 spacing that I missed this. It should be possible to simply the whole design using 8n+4 pairs and avoid all the 8n+2 to 8n+6 conversions (I'm just starting to get an intuition about these things). It would be nice if there was a simple way to reflect 8n streams. I haven't found one yet.

[Layz Boi]

Isn't there already like 1-3 Margolus Critters threads?
This one seems like a MC general thread:? viewtopic.php?f=11&t=3918

[pcallahan]

Isn't there already like 1-3 Margolus Critters threads?
This one seems like a MC general thread:? http://www.conwaylife.com/forums/viewto ... =11&t=3918

Sorry, as I said in my first post, I thought this construction was worth highlighting in its own topic rather than repurposing some threads from last March. The previous threads were mostly resurrected (Side note: I find it an unusual convention on this website that new threads and even new posts are discouraged in favor of editing previous ones; it seems like a recipe for preventing people from seeing anything new unless they go looking for it--and I am not that much of an optimist.)

For instance, I have been pretty disciplined about keeping stream splitters in the (old) thread I opened for that topic, even to the extent of making multiple updates to the same post for days before add a new one.

Chris Rowett reopened the "serious survey of constructions" thread http://www.conwaylife.com/forums/viewto ... =11&t=3918 when announcing his improvements to LifeViewer. Most of my new comments on that thread have been in response to his improvements, including some patterns.

If patterns such as the loop-copier are actually old news, then I'm not sure where to find similar results (please, I'd love to see more advanced work in this direction). Most Critters papers I have seen cover general properties and reversibility rather than engineering design. It is entirely possible that some group is way ahead on this kind of thing and either not publishing or I am not doing a sufficient literature search (I have tried).

My overall project here is to develop a framework for self-replicating universal computers in the Critters universe given the addition of a single uniform glider stream entering from infinity (since any finite pattern is guaranteed to maintain the same cell count*).

I guess there is not all that much interest in Margolus Critters, but I keep hoping anyway. I will avoid spawning any additional threads, but I am a little confused as to why it's an issue.

*A finite bound on the number of cells does not equate to a finite number of states, and e.g. Life with several counters based on block pusher/pullers can simulate a Turing machine tape with a fixed bound on cell count at an exponential cost in time complexity. I do not believe there is such a construction in Critters, my intuition being that there is almost no way to recover all the gliders that might be used for pushing blocks or the equivalent and you can't just make new ones as in Life. That would probably be a harder thing to prove than to find a counterexample, if one exists. If anyone can resolve this, I'm interested. However, block memories don't interest me very much because to the exponential slowdown.

UPDATE (9/28/19): Using the reflector-shifting method (see splitting thread) we can make a loop that is readable but does not require a glider stream as input.

Code: Select all

x = 213, y = 107, rule = critters
#C [[ RLE input o$bo$bo$o! ]]
#C [[ PASTET EVERY 32 ]]
#C [[ PASTE input 1 64 ]]
17$129b2o54b2o$129b2o54b2o7$121b2o70b2o$121b2o70b2o5$188b2o$187bo2bo$
185bo6bo$186bo4bo5$187bo2bo2$188b2o6$37b2o$37b2o5$39bo2bo2$40b2o6$73b
2o$73b2o2$126b2o$bo15bo170b2o$2bo15bo64bo41bo2bo58bo2bo$2bo15bo64bo$b
o15bo$113bo$114bo$69bo54bo4bo57bo2bo$70bo52bo6bo$125bo2bo59b2o$126b2o
$33bo2bo$34b2o3$73b2o46b2o70b2o$73b2o46b2o70b2o5$31b2o$31b2o$129b2o54b
2o$129b2o54b2o!

Here is the same pattern with an additional trick for synching up the timing.

Code: Select all

x = 271, y = 134, rule = critters
#C [[ RLE input o$bo$bo$o! ]]
#C [[ PASTET EVERY 32 ]]
#C [[ PASTE input 29 79 ]]
31$135b2o54b2o$135b2o54b2o7$127b2o65b2o3b2o$127b2o64bo2bo2b2o5$193bo2b
o2$194b2o2$191bo6bo$192bo4bo11$43b2o$43bobo$44bo3bo$46b2o9$194b2o$193b
o2bo$79b2o$79b2o3$29bo15bo9bo21bo9b2o104bo2bo$30bo15bo9bo21bo8bo$30bo
15bo9bo21bo8bo106b2o$29bo15bo9bo21bo9b2o$119bo10bo4bo$120bo8bo6bo$75b
o$76bo55b2o$87bo14bo16bo6bo24bo14bo16bo14bo$88bo11bo19bo4bo5bo2bo17bo
11bo19bo11bo$88bo11bo19bo4bo26bo11bo19bo11bo$87bo14bo16bo6bo24bo14bo16b
o14bo3$79b2o46b2o2bo2bo64b2o$79b2o46b2o3b2o65b2o$39bo2bo$40b2o3$37b2o
$37b2o$135b2o54b2o$135b2o54b2o3$115bo18bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3b
o3bo3bo3bo3bo3bo3bo3bo$116bo16bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3b
o3bo3bo3bo3bo$215bo14bo16bo14bo$216bo11bo19bo11bo$216bo11bo19bo11bo$215b
o14bo16bo14bo$133bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3b
o$134bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo3bo$120bo$119b
o!

Update (9/29/19):
We can use a similar method to stagger the uniform period signal with a relay that doesn't require the signal to be present. However, I was unable to compress the initial stream below period-64. I have some other ideas and I think it may be possible for a period-32 stream.

Code: Select all

x = 143, y = 55, rule = critters
#C [[ RLE input o$bo$bo$o! ]]
#C [[ PASTET EVERY 64 ]]
#C [[ PASTE input 0 28 ]]
$72bo4$89bo$90bo3$73bo2bo$74b2o10$86b2o2$85bo2bo3$72bo4bo45bo$71bo6bo
45bo3$bo138bo$2bo$2bo$bo138bo3$71bo12bo4bo$72bo10bo6bo5$89b2o$89b2o$121b
2o$121b2o7$124bo$123bo!

In Conway's Life, it is possible to build sparky oscillators, but in Critters, there is no such thing as a spark (which vanishes and is therefore irreversible). Movable reflectors make it possible to do some of the same things.

Work in progress: What if we use a recirculating loop instead of shuttles. I think I can get the period down to 48 with appropriate timing:

Code: Select all

x = 52, y = 66, rule = critters
15$21b2o4b2o$21b2o4b2o3$9bo8b2o20bo$17bo2bo2$9bo30bo3$17bo2bo6bo6bo$28b
o4bo$18b2o8$16bo4bo$15bo6bo11$12bo24bo3$12bo24bo3$21b2o4b2o$21b2o4b2o
!

A different approach brings it down to 48.

Code: Select all

x = 101, y = 71, rule = critters
#C [[ RLE input o$bo$bo$o! ]]
#C [[ PASTET EVERY 48 ]]
#C [[ PASTE input 8 38 ]]
21$79b2o$79b2o4$82b2o2$81bo2bo3$77bo$78bo3$72bo2bo$71bo4bo3$9bo$10bo$
10bo$9bo3$78bo2bo$77bo4bo3$76bo$75bo6$70b2o2$69bo2bo$73b2o$73b2o!

Update (10/1/19):
As a somewhat trivial observation, it is possible to stabilize the period-32 phase shifters into period-128 glider relays. It allows for gaps before the input stream arrives, but it does need to arrive at the correct step mod-128. I.e., only every fourth glider can be used to start it.

Code: Select all

x = 302, y = 137, rule = critters
#C [[ RLE input o$bo$bo$o! ]]
#C [[ PASTET EVERY 32 ]]
#C [[ PASTE input 1 83 ]]
35$221b2o54b2o$221b2o54b2o2$218b2o2$217bo2bo3$213b2o70b2o$213b2o70b2o
$217bo2bo$218b2o7$277bo6bo$278bo4bo11$135b2o$135b2o3$123bo$124bo9$165b
2o$165b2o$131bo2bo$132b2o$bo$2bo172bo$2bo172bo$bo$205bo10bo4bo$206bo8b
o6bo$125bo2bo32bo$162bo$126b2o4$280b2o$279bo2bo$165b2o46b2o70b2o$165b
2o46b2o70b2o$136bo115bo4bo$135bo114bo7bo$250bo7bo20bo2bo$252bo4bo$123b
2o155b2o$123b2o$221b2o54b2o$221b2o54b2o!

Update (10/7/19): Above with improved 90° reflectors.

Code: Select all

x = 291, y = 104, rule = critters
#C [[ RLE input o$bo$bo$o! ]]
#C [[ PASTET EVERY 32 ]]
#C [[ PASTE input 4 61 ]]
x = 319, y = 94, rule = critters
15$245bo10bo4bo46bo$244bo10bo7bo45bo$243bo11bo7bo46bo$256bo4bo11$305b
o6bo$306bo4bo13$167b2o$167b2o3$155bo$156bo7$197bo$198bo$163bo2bo2$164b
2o2$5bo202bo$6bo$6bo150bo2bo$5bo152b2o48bo$231bo10bo4bo$232bo8bo6bo3$
200bo2$202bo$199bo5$168bo91bo4bo26bo4bo$167bo75bo14bo7bo23bo7bo11bo$244b
o13bo7bo23bo7bo10bo$245bo14bo4bo26bo4bo10bo$155b2o$155b2o!

[Redstoneboi]

I don't really have the resources to be able to mess with Margolus rules a lot yet, but I do have a question/suggestion:
How would a child get its food?

Now, my idea is that the parent's last construction step would be to reroute all of its future food into the child somehow, like an umbilical cord.
This means that, depending on how the parent does said step, the child's food could be different from a steady period-n stream of gliders.

Right now there's a converter before the actual signal multiplexer (or as you call it, a bit-loop-to-stream copier) that doesn't serve any significance other than change the food that's being fed.
Modifying that converter may or may not be useless in the end.
If the stream were to be changed into a more usable food type, it'd probably be easier to make a rerouting system for the child.

My suggestion is, we should focus on getting de/construction done, then circuitry, and finally the actual mechanisms we'll use to cope with the limitations of the rule.

Once we have de/construction mechanisms, we should find out how to do the rerouting.
This lets us know what kind of food "digestion system" the machine really needs, if it needs one in the first place.
The food rerouter doesn't necessarily have to be constructed, it could just be blocked by some sort of reflector until a meta/destruction signal comes.

[pcallahan]

My suggestion is, we should focus on getting de/construction done, then circuitry, and finally the actual mechanisms we'll use to cope with the limitations of the rule.

I would describe my focus as being on the parts I can actually do. It is hard to come up with syntheses, though I believe it's possible. You may need to use a lot of gliders to get something simple, and because it's reversible, you need to deal with the fact that all these reactions will release gliders, so you need a clear path to infinity for those. Right now, I don't have the tooling to carry out systematic searches like I would do in Life.

The reason for starting out with stream conversion is that it's not worth pursuing much else if you can't convert a "food source" that isn't rigged specially for your pattern.

I have done a little on circuitry. Originally I wanted to build a binary counter, which is certainly doable if it is fed with a clock tick stream. But I got sidetracked with the embedded Turing machine I posted here: https://conwaylife.com/forums/viewtopic ... =25#p85211

(I haven't had any more time for the past few weeks. It'd be cool to see somebody else take this up.)

Added 11/30/19 (I may bump the thread if I have more results). The 5-cell period-8 oscillator shown in the box does the phase staggering, replacing the clumsy relay construction.

Code: Select all

x = 171, y = 77, rule = critters
#C [[ RLE input o$bo$bo$o! ]]
#C [[ PASTET EVERY 32 ]]
#C [[ PASTE input 5 53 ]]
# [[ POLYLINE 49 51 55 51 55 55 49 55 49 51 9 ]]
5$93bo15bo8bo41bo$96bo14bo5bo39bo$111bo5bo$94bo14bo8bo40bo11$156bo4bo
$155bo6bo33$5bo15bo15bo12b2obo$6bo15bo15bo12b2o$6bo15bo15bo43bo8bo6bo
$5bo15bo15bo43bo10bo4bo2$50b2o$72bo10bo$49bo2bo17bo13bo$49bo2bo17bo13b
o$72bo10bo$43bo6b2o$44bo$49bo2bo2$94bo8bo8bo22bo8bo14bo$104bo5bo25bo5b
o$96bo7bo5bo25bo5bo14bo$93bo9bo8bo22bo8bo15bo!