Splitting a glider stream in Margolus Critters
Posted: March 28th, 2019, 1:13 am
I'm starting a new thread because this is the first thing that looks like a useful result for what I have been thinking about. I'm also not saying it's new (in fact the gadget consists of a single cell, so it must have been noticed) but I'm unsure if Critters has been studied from this viewpoint. The question is what it would take to build universal constructors in Critters. It is tricky but not impossible. Reversibility is not a fatal problem as long as we have paths for escaping gliders to move "history" out of the active area, effectively simulating irreversibility much as we do in the real world, by producing waste heat.
As I said in the other thread, to get around the issue of conservation of cells:
Begin with a single fixed-period glider stream entering from infinity. No gun can exist in Critters, so this stream is there by fiat. Is this "cheating"? Well, is it cheating for a plant to require sunlight to grow? If we have physics-like rules, we will not have devices that produce energy out of nothing, so we do need some source of energy.
My question was whether this source of gliders can be split in such a way to be used in multiple patterns. It turns out that a period-8n stream can be split using a single cell that acts as a 180 degree reflector but also creates collisions resulting in 90 degree deflections.
I started with the glider in this phase (moving right) such that its upper left cell is at (1, 1) set to collide with a single cell at (1, 4) (note this will not work in viewer)
In general, let there be an infinite stream of gliders positioned at (1, 1-8nj) for j=0, 1, 2, ... This is in effect, the only kind of "gun" you will get in the Critters rule because of reversibility and cell conservation. But it is a legitimate infinite periodic pattern. I'd like to avoid having lots of these, so the goal is to split it into other glider sources at other locations.
In Critters, when two gliders collide, at least one must eventually emerge, usually two. But one thing that makes the world a little more friendly is that backward gliders can often pass through a forward stream "transparently" without interacting at all. That is how we deal with backward gliders in this splitter if they don't eventually rebound.
You can look at the RLE pattern with 25 gliders (j<25 and n=2) in viewer. I have put two additional cells set to split the 90-degree output stream of the original stream to demonstrate that it can be chained. You need n>=2 for sufficient spacing, and need to work a little to avoid having the backward gliders collide with the initial stream.
You can watch the above pattern run in this online RCA app.
So what happens in this splitter? (1) The first glider passes through the cell unchanged, but moves the cell to a reflector position. (2) The second glider is reflected back from the cell. (3) The second glider collides with the third glider, creating fixed debris A and a reflected glider B. (4) B passes through the cell phase-shifted and escapes. (5) The fourth glider collides with the fixed debris, producing a backward glider C and a forward glider D. C continues backward through the period-8n stream without interacting. D is reflected back from the cell and collides with the fifth glider, producing E and F heading up and down relative to the stream.
Here is what a stream of 5 gliders looks like in the app.
The up and down streams have the right periodicity to be split again. (The forward stream has gliders out of phase) They can be split because they originate from a collision point that is normally empty space. So the backward gliders will not hit the splitter cell. In fact, they collide with each other to produce forward and backward gliders producing a third glider. This has to be staggered to avoid the original stream (i.e. the next splitters cannot be placed symmetrically).
Finally, for a stream of 25 gliders on a single path chaining splitters as shown, we get 3 gliders out on parallel paths. These can be split further. We are "wasting" gliders of course, but there are infinitely many. A universal constructor built with such a trickle of raw material would be slow, but there is no reason in theory it could not work.
Note that the gliders that continue forward out of phase can actually be deflected 90 degrees like this (see app). So we can probably do a lot better than a reduction of 3/25 every time we split the stream. This is just a proof of concept.
ADDED: Here is a small python program for applying Critters transitions to sparse cell lists:
It can be run at this repl.it link. The pattern is preset to be 5 gliders spaced 16 cells apart approaching the reflector cell. There are no graphics (though I use a clunky Python turtle graphics approach offline). I was trying to come up with an easy way to get a cell list into Golly for viewing. Anyone know?
As I said in the other thread, to get around the issue of conservation of cells:
Begin with a single fixed-period glider stream entering from infinity. No gun can exist in Critters, so this stream is there by fiat. Is this "cheating"? Well, is it cheating for a plant to require sunlight to grow? If we have physics-like rules, we will not have devices that produce energy out of nothing, so we do need some source of energy.
My question was whether this source of gliders can be split in such a way to be used in multiple patterns. It turns out that a period-8n stream can be split using a single cell that acts as a 180 degree reflector but also creates collisions resulting in 90 degree deflections.
I started with the glider in this phase (moving right) such that its upper left cell is at (1, 1) set to collide with a single cell at (1, 4) (note this will not work in viewer)
Code: Select all
o..o
.o
.o
o
In Critters, when two gliders collide, at least one must eventually emerge, usually two. But one thing that makes the world a little more friendly is that backward gliders can often pass through a forward stream "transparently" without interacting at all. That is how we deal with backward gliders in this splitter if they don't eventually rebound.
You can look at the RLE pattern with 25 gliders (j<25 and n=2) in viewer. I have put two additional cells set to split the 90-degree output stream of the original stream to demonstrate that it can be chained. You need n>=2 for sufficient spacing, and need to work a little to avoid having the backward gliders collide with the initial stream.
Code: Select all
x = 411, y = 321, rule = critters
34$391bo127$13bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15b
o15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo2bo$14bo15bo15bo15bo15bo15bo
15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15b
o15bo$14bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15b
o15bo15bo15bo15bo15bo15bo15bo15bo15bo$13bo15bo15bo15bo15bo15bo15bo15b
o15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo15bo
143$391bo!
So what happens in this splitter? (1) The first glider passes through the cell unchanged, but moves the cell to a reflector position. (2) The second glider is reflected back from the cell. (3) The second glider collides with the third glider, creating fixed debris A and a reflected glider B. (4) B passes through the cell phase-shifted and escapes. (5) The fourth glider collides with the fixed debris, producing a backward glider C and a forward glider D. C continues backward through the period-8n stream without interacting. D is reflected back from the cell and collides with the fifth glider, producing E and F heading up and down relative to the stream.
Here is what a stream of 5 gliders looks like in the app.
The up and down streams have the right periodicity to be split again. (The forward stream has gliders out of phase) They can be split because they originate from a collision point that is normally empty space. So the backward gliders will not hit the splitter cell. In fact, they collide with each other to produce forward and backward gliders producing a third glider. This has to be staggered to avoid the original stream (i.e. the next splitters cannot be placed symmetrically).
Finally, for a stream of 25 gliders on a single path chaining splitters as shown, we get 3 gliders out on parallel paths. These can be split further. We are "wasting" gliders of course, but there are infinitely many. A universal constructor built with such a trickle of raw material would be slow, but there is no reason in theory it could not work.
Note that the gliders that continue forward out of phase can actually be deflected 90 degrees like this (see app). So we can probably do a lot better than a reduction of 3/25 every time we split the stream. This is just a proof of concept.
ADDED: Here is a small python program for applying Critters transitions to sparse cell lists:
Code: Select all
# construct margolus transition tables for critters
def make_critters_table():
table = []
for i in range(16):
window = [(i>>b) & 1 for b in range(4)]
ct = sum(x for x in window)
if ct in [0, 1, 4]:
nexti = i ^ 0xf
elif ct == 2:
nexti = i
else:
nexti = sum(window[i] << (3 - i)
for i in range(4)) ^ 0xf
table.append(nexti)
return table
TABLE = make_critters_table()
# collect individual cells into 2x2 boxes at offset
def pack_cells(cells, offset):
windows = {}
# toggle vacuum between 0 and 1
default = 0xf * offset
for i, j in cells:
di = (i + offset) % 2
dj = (j + offset) % 2
pos = (i - di, j - dj)
windows[pos] = (windows.get(pos, default) ^
(1 << (di * 2) + dj))
return windows
# apply transition rule to boxes
def apply_rule(windows, table):
for pos in windows:
windows[pos] = table[windows[pos]]
# unpack boxes
def unpack_cells(windows, offset):
for pos in windows:
# toggle vaccuum between 1 and 0
window = windows[pos] ^ ((offset ^ 1) * 0xf)
for di in range(2):
for dj in range(2):
if ((window >> (di * 2) + dj) & 1):
yield pos[0] + di, pos[1] + dj
def run(cells, offset):
windows = pack_cells(cells, offset)
apply_rule(windows, TABLE)
return list(unpack_cells(windows, offset)), offset ^ 1
def show(cells):
for cell in sorted(cells):
print('%d %d' % cell)
# construct a stream of gliders
glider = [(1, 1), (2, 2), (3, 2), (4, 1)]
cells = [(celli, cellj - 16 * j) for celli, cellj in glider
for j in range(5)]
# append a reflector cell
cells.append((1, 4))
offset = 0
print('cells at generation 0')
show(cells)
generations = 120
for step in range(generations):
cells, offset = run(cells, offset)
print('cells at generation %d' % generations)
show(cells)