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)