ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Serizawa - Linear Self Replicator.

For discussion of other cellular automata.

Serizawa - Linear Self Replicator.

Postby simsim314 » March 23rd, 2014, 6:54 pm

Serizawa rule is perfect for self replicators and universal constructors, but until now there was no known specific examples of such. Here is a working Universal Constructor based self replicator (Geminoid) in Serizawa.

It's P13,362,290 with (2444, 3219) step.

The Geminoid is attached. You can also run the script directly (you need to setup Serizawa rule in golly first and run the script, it takes about 5-10 min):

import golly as g

class Glider:
   def __init__(self, x, y, dx, dy, state, gen):
      self.x = x
      self.y = y
      self.gen = gen
      self.state = state
      self.dx = dx
      self.dy = dy
      
   def Place(self):
      if self.dx == 0:
         gld = g.parse(".B$A.A!", -1, 0, 1, 0, 0, self.dy)
      else:
         gld = g.parse("A$.B$A!", -self.dx, -1, self.dx, 0, 0, 1)
         
      gld = g.evolve(gld, self.state)
      g.putcells(gld, self.x, self.y)

class Stopper:
   def __init__(self, gld, dist):
      self.x = gld.x + dist * gld.dx
      self.y = gld.y - dist * gld.dy
      
   def Place(self):
      b = g.parse("A!", 0, 0, 1, 0, 0, 1)
      g.putcells(b, self.x, self.y)
      self.Register(data)
      
   def Register(self, data):
      data.append([self.x, self.y, 0])
      
class TripleSplitter:
   def __init__(self, gld, dist):
      self.dist = dist
      self.gld = gld
      
      self.x = gld.x + dist * gld.dx
      self.y = gld.y - dist * gld.dy
      
      self.fgld = Glider(self.x + 3 * gld.dx, self.y - 3 * gld.dy, gld.dx, gld.dy, 0, 5 + gld.gen + dist * 2 + gld.state)
      self.rgld = Glider(self.x + 4 * gld.dy - gld.dx, self.y + gld.dy + 4 * gld.dx, gld.dy, -gld.dx, 0, 5 + gld.gen + dist * 2 + gld.state)
      self.lgld = Glider(self.x - 4 * gld.dy - gld.dx, self.y + gld.dy - 4 * gld.dx, -gld.dy, gld.dx, 0, 5 + gld.gen + dist * 2 + gld.state)
      
   def Place(self):
      b = g.parse("A.A2$A.A!", 0, 0, self.gld.dy, 0, 0, self.gld.dx)
      g.putcells(b, self.x - self.gld.dy, self.y - self.gld.dx)
      self.Register(data)
      
   def Register(self, data):
      if self.gld.dx == 0:
         data.append([self.x + 1, self.y, 1])
      else:
         data.append([self.x, self.y - 1, 2])
         
class Splitter:
   def __init__(self, gld, dist, isRight):
      
      self.split = TripleSplitter(gld, dist)

      if isRight:
         self.refstop = Stopper(self.split.lgld, 1)
         self.refgld = self.split.rgld
      else:
         self.refstop = Stopper(self.split.rgld, 1)
         self.refgld = self.split.lgld
   def Place(self):
   
      self.split.Place()
      self.refstop.Place()
      
      
   def Register(self, data):
      self.split.Register(data)
      self.refstop.Register(data)

class Mirror(Splitter):
   def __init__(self, gld, dist, isRight):
   
      Splitter.__init__(self, gld, dist, isRight)
      self.fstop = Stopper(self.split.fgld, 1)
   
   def Place(self):
      
      Splitter.Place(self)
      self.fstop.Place()
      
      
   def Register(self, data):
      Splitter.Register(self, data)
      self.fstop.Register(data)

def PlaceNegative():
   total = 10
   dist = 29
   deltaX = 400
   
   for i in xrange(0, total):
      gld = Glider(posx + i * dist, posy, 0, -1, 0, 0)
      #gld.Place()
      split = Mirror(gld, 10 + i * dist, False)
      split.Place()
   
      mir = Splitter(split.refgld, defaultDx + 2 * dist * (total - i), False)
      mir.Place()
      
      mir = Mirror(mir.split.fgld, 30 * 10, False)
      mir.Place()
      
      
def PlaceRef(dist, fact, toplace):         
   total = 10
   delta = [200, 200, 190, 190, 180]
   #ds = [[1,0,1,0,0,1,0,1,0,0], [1,0,1,0,0,1,0,1,0,0], [1,0,0,1,0,1,0,0,1,0],[1,0,1,0,0,1,0,1,0,0], [1,0,1,0,0,1,0,1,0,0], [1,0,0,1,0,1,0,0,1,0]]
   #ir = 11
   #d = 36
   ir = 1
   d = 52
   deltaX = 400
   
   ds = [[1,0,0,1,0,1,0,0,1,0],[1,0,1,0,0,1,0,1,0,0], [1,0,1,0,0,1,0,1,0,0], [1,0,0,1,0,1,0,0,1,0], [1,0,0,1,0,1,0,0,1,0],[1,0,1,0,0,1,0,1,0,0], [1,0,1,0,0,1,0,1,0,0], [1,0,0,1,0,1,0,0,1,0]]
   #placement = [[0,0,-1,-1,-1,-1,-1,-1,-1,-1], [0,4,-1,-1,-1,-1,-1,-1,-1,-1], [0,2,72,71,-1,-1,-1,-1,-1,-1], [0,0,-1,-1,-1,-1,-1,-1,-1,-1], [-1,-1,10,0,-1,-1,-1,-1,-1,-1], [37 ,41,7,0,51,-1,-1,-1,-1,-1]]
   #placement = [[-1,-1,-1,-1,-1,0,0,-1,-1,-1], [-1,-1,-1,-1,-1,0,4,-1,-1,-1,-1,-1,-1,-1,-1], [-1,-1,-1,-1,-1,0,2,52 + 2 * (dist - 19),51 + 2 * (dist - 19),-1,-1,-1,-1,-1,-1], [-1,-1,-1,-1,-1,0,0,-1,-1,-1,-1,-1,-1,-1,-1], [-1,-1,-1,-1,-1,-1,-1,10,0,-1,-1,-1,-1,-1,-1], [-1,-1,-1,-1,-1,17 + 2 * (dist - 19),21 + 2 * (dist - 19),7,0,31 + 2 * (dist - 19),-1,-1,-1,-1,-1]]
   placement = []
   placement.extend([[-1,-1,-1,-1,-1,0,2,72,71,-1], [-1,-1,-1,-1,-1,0,0,-1,-1,-1], [-1,-1,-1,-1,-1,-1,-1,10,0,-1], [-1,-1,-1,-1,-1,37 ,41,7,0,-1]])
   placement.extend([[0,2,72,71,-1,-1,-1,-1,-1,-1], [0,0,-1,-1,-1,-1,-1,-1,-1,-1], [-1,-1,10,0,-1,-1,-1,-1,-1,-1], [37 ,41,7,0,-1,-1,-1,-1,-1,-1]])
   #ds = [[1,0,1,0,0,0,0,0,0,0], [1,0,1,0,0,0,0,0,0,0]]
   #placement = [[0,4,0,0,0,0,0,0,0,0], [0,0,0,0,0,0,0,0,0,0]]
   
   #for i in xrange(0, 2):    
   #   placement.extend(placement)
   #   ds.extend(ds)
      
   for i in xrange(0, total):
   
      gld = Glider(posx + i * dist, posy, 0, 1, 0, 0)
      split = Splitter(gld, 10 + i * dist, True)
      mir = Mirror(split.refgld, defaultDx + 2 * dist * (total - i), True)
         
      if toplace:

         split.Place()
         mir.Place()

      if i >= total / 2:
         mir = Mirror(split.split.fgld, dist * total / 2, True)
         mir.Place()
         mir = Mirror(mir.refgld,10 + 60 * (10 - i), True)
         mir.Place()
         delMir = 10
         mir = Mirror(mir.refgld, delMir, False)
         mir.Place()
         mir = Mirror(mir.refgld, delMir, False)
         mir.Place()
         mir = Mirror(mir.refgld, delMir, True)
         mir.Place()
         mir = Mirror(mir.refgld, 10, True)
         mir.Place()
         mir = Mirror(mir.refgld, delMir, False)
         mir.Place()
         mir = Mirror(mir.refgld, delMir, False)
         mir.Place()
         mir = Mirror(mir.refgld, delMir, True)
         mir.Place()
         
      for j in xrange(0, len(placement)):
         if placement[j][i] >= 0:
            #gld = Glider(posx + i * dist, posy + dist * j + i * fact + placement[j][i], 0, 1, ds[j][i], 0)
            gld = Glider(posx + i * dist, posy + total * dist * j + placement[j][i], 0, 1, ds[j][i], 0)
            #gld.Place()
      if i <= 4:
         gld = Glider(posx + i * dist, posy - delta[i], 0, 1, 0, 0)
      else:
         gld = Glider(posx + deltaX + 201, -157 + posy - i * dist, 1, 0, 0, 0)
         
      if i%5 == 0 or i%5 == 1:
         if i <= 4:
            gl = Glider(posx + i * dist, 50 + posy - delta[i], 0, 1, 0, 0)
         else:
            gl = Glider(posx + deltaX + 131, -157 + posy - i * dist, 1, 0, 0, 0)
         
         mir = Mirror(gl, 10, i > 4)
         mir.Place()
         mir = Mirror(mir.refgld, 6, i <= 4)
         mir.Place()
         mir = Mirror(mir.refgld, 10, i <= 4)
         mir.Place()
         mir = Mirror(mir.refgld, 6, i > 4)
         mir.Place()
      
      if i%5 == 4:
         if i <= 4:
            gl = Glider(posx + i * dist,  posy - delta[i], 0, 1, 0, 0)
         else:
            gl = Glider(posx + 471, -157 + posy - i * dist, 1, 0, 0, 0)

         mir = Mirror(gl, 0, i > 4)
         mir.Place()
         mir = Mirror(mir.refgld, 5, i <= 4)
         mir.Place()
         
      if i%5 ==0 or i%5 == 2:
         mir = Mirror(gld, 19, i <= 4)
         mir.Place()
      
         sp = Splitter(gld, 0, i > 4)
         sp.Place()
         mir = Mirror(sp.refgld, 6, i <= 4)
         mir.Place()
         mir = Mirror(mir.refgld, 6, i <= 4)
         mir.Place()
      if i%5 == 1 or i%5 == 3:
         mir = Mirror(gld, 19, i > 4)
         mir.Place()
      
   ddX = 0
   ddY = 0
   
   if toplace:
      ddX = 1031
      ddY = 774
      
   b = g.parse("A!")
   g.putcells(b, 11 + posx + (dist - 17) / 2, -ddY-250 + posy)
   data.append([11 + posx + (dist - 17) / 2, -ddY-250 + posy, 0])
   

   data.append([ddX + defaultDx + deltaX - 682 + posx + (dist - 17) / 2, -319 + posy, 0])
   g.putcells(b, ddX + defaultDx + deltaX - 682 + posx + (dist - 17) / 2, -319 + posy)
   
class CommandPlacer():
   def __init__(self):
      self.loc = 0
      self.dist = 29
      self.cellLoc = [0, 0]
      self.lastCmd = -1
      self.lastDir = -1
      
   def Push(self, dir):
      
      if not(self.lastCmd == 0 and self.lastDir == dir):
         self.loc += 150

      ds = [[1,0],[1,0]]
      pl = [[0,0], [0,4]]
      spacing = [40, 40]
      self.Place(ds, pl, spacing, dir)
      
      self.cellLoc[dir] += 2
      
      self.lastCmd = 0
      self.lastDir = dir
      
   def PullSequence(self, dir, shoot):
      self.loc += 150
      
      pl = [[0,2,72,71,-1], [0,0,-1,-1,-1], [-1,-1,10,0,-1], [37 ,41,7,0,51 * shoot]]
      ds = [[1,0,0,1,0],[1,0,1,0,0], [1,0,1,0,0], [1,0,0,1,0]]
      spacing = [60, 80, 58, 40]
      self.Place(ds, pl, spacing, dir)
      self.cellLoc[dir] -= 31
      
   def Pull(self, dir):
      self.PullSequence(dir, 1)
      self.lastCmd = 1
      self.lastDir = dir
      self.loc += 150
   def Shoot(self, dir):
      self.PullSequence(dir, -1)
      self.lastCmd = 2
      self.lastDir = dir
      self.loc += 150
      
   def CreateBlock(self):
      self.loc += 150
      
      #pltemp = [[0,2,72,71,-1], [0,0,-1,-1,-1], [-1,-1,10,0,-1], [37 ,41,7,0,-1]]
      
      ds = [[1,0,0,1,0, 1,0,0,1,0],[1,0,1,0,0, 1,0,0,1,0], [1,0,0,1,0, 1,0,0,1,0],[1,0,1,0,0, 1,0,0,1,0],[1,0,1,0,0, 1,0,1,0,0], [1,0,0,1,0, 1,0,0,1,0],[1,0,1,0,0, 1,0,0,1,0], [1,0,0,1,0, 0,1,1,0,0]]
      pl = [[0,2,72,71,-1,-1,-1,-1,-1,-1], [0,0,-1,-1,-1,-1,-1,-1,-1,-1], [-1,-1,-1,-1,-1,0,2,72,71,-1], [-1,-1,-1,-1,-1,0,0,-1,-1,-1]]
      pl.extend([[-1,-1,10,0,-1,-1,-1,-1,-1,-1], [37 ,41,7,0,-1,-1,-1,-1,-1,-1], [-1,-1,-1,-1,-1,-1,-1,10,1,-1], [-1,-1,-1,-1,-1,37,42,8,0,-1]])
      spacing = [150, 150, 150, 150, 58, 39, 58, 90]
      
      self.Place(ds, pl, spacing, 0)
      
      self.cellLoc[0] -= 31
      self.cellLoc[1] -= 31
      
      self.lastCmd = 3
      self.lastDir = -1
      self.loc += 150
      
   def Place(self, ds, pl, spacing, dir):
      for j in xrange(0, len(pl)):
         for i in xrange(0, len(pl[0])):
            if pl[j][i] >= 0:
               gld = Glider(posx + (i + dir * 5) * self.dist, posx + pl[j][i] + self.loc, 0, 1, ds[j][i], 0)
               gld.Place()

         self.loc += spacing[j]
   
   def Place2Block(self, dir):
      self.CreateBlock()
      self.Pull(1 - dir)

      for j in xrange(0, 14):
         self.Push(dir)
      for j in xrange(0, 32):
         self.Push(1 - dir)
         
      self.CreateBlock()

      self.Pull(1 - dir)
      for j in xrange(0, 30):
         self.Push(1 - dir)
         
      self.Shoot(1 - dir)
   
   def Goto(self, x, y):
      
      while (self.cellLoc[0] > x or self.cellLoc[0]%2 != x%2):
         self.Pull(0)
      
      while (self.cellLoc[1] > y or self.cellLoc[1]%2 != y%2):
         self.Pull(1)
         
      for j in xrange(0, (y - self.cellLoc[1]) / 2):
         self.Push(1)
      
      for j in xrange(0, (x - self.cellLoc[0]) / 2):
         self.Push(0)

   def Set0(self, x0, x1):
      for j in xrange(0, x0):
         self.Push(0)
      
      for j in xrange(0, x1):
         self.Push(1)
      
      self.cellLoc = [0, 0]
      
   def PlaceData(self, data):
      
      maxXY = -100000
      minXY = 100000
      
      for d in data:
         if maxXY < d[0] - d[1]:
            maxXY = d[0] - d[1]
            
         if minXY > d[0] - d[1]:
            minXY = d[0] - d[1]
      
      dXY = []

      for i in xrange(minXY, maxXY + 1):
         l = []
         
         for d in data:
            if i == d[0] - d[1]:
               l.append(d)
         
         dXY.append(l)
      
      for i in reversed(dXY):
         for d in i:
            self.Goto(-d[1], d[0])
            
            if d[2] == 0:
               self.CreateBlock()
            if d[2] == 1:
               self.Place2Block(1)
            if d[2] == 2:
               self.Place2Block(0)



defaultDx = 900
data = []
posx = (593 + 29) - 1116
posy = 5600 - 6374
PlaceNegative()
posx += (896 + 29) + 600

PlaceRef(29, 0, False)
posx = 0
posy = 0
PlaceRef(29, 0, True)



cmd = CommandPlacer()
cmd.Set0(1113, 410)
cmd.PlaceData(data)
cmd.Pull(0)
cmd.Pull(1)

#cmd = CommandPlacer()
#cmd.Goto(1200, 1200)
#cmd.Place2Block(1)
#posx += 1000


posx = 1716 + (593 + 29) - 1116
posy = 1500 + 5600 - 6374 + int(cmd.loc/2 + 2000)
PlaceNegative()
posx += (896 + 29) + 600
PlaceRef(29, 0, False)
posx = 1716
posy = 1500 + int(cmd.loc/2 + 2000)
PlaceRef(29, 0, True)
'''

posx = 1716 + (593 + 29) - 1116
posy = 1500 + 5600 - 6374 + 3500000
PlaceNegative()
posx += (896 + 29) + 600
PlaceRef(29, 0, False)
posx = 1716
posy = 1500 + 3500000
PlaceRef(29, 0, True)
'''
Attachments
SerizawaGeminoid.7z
(21.86 KiB) Downloaded 182 times
Last edited by simsim314 on March 27th, 2014, 6:04 am, edited 1 time in total.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Working Geminoid (Self replicator)

Postby dvgrn » March 26th, 2014, 5:27 pm

Very nice work! Finally, a Geminoid device with orthogonal signals, so that its bounding box is a reasonably good approximation of its size... It's nice to see Geminoid principles applied to a completely different rule.

The pattern as it stands is not quite a Geminoid spaceship. It's also not quite a self-replicator, at least according to my annoyingly technical definition of the term. The original Gemini spaceship had a separate "destructor arm" that shot down old copies of the replicator units after they went dormant. Disabling or removing that Gemini destructor arm (which is quite easy to do) produces a "self-constructing puffer" exactly analogous to this Serizawa Geminoid pattern -- but not a self-replicator, in my view, because there's only ever one copy of the glider streams that encode the construction data.

Now, my opinion about what counts as a self-replicator is just an opinion, of course -- people have definitely built patterns along these same lines in various rules, where the data stream is never replicated and the object just leaves behind empty shells of circuitry behind itself... and sometimes they called these patterns "replicators".

But it doesn't seem like a very satisfactory kind of replication, somehow. -- Come to think of it, I said something similar about current Conway's Life Geminoid replicators, so I'm not playing favorites too much, at least. But the interesting question is: how easy is it to put together variations of this design that everyone would agree is a true self-replicator?

It might be worth thinking about making a true Geminoid spaceship, for starters. Is it possible to clean up one of these Serizawa logic circuits (i.e., patterns made out of single stable state-1 dots) using single gliders from just one construction arm? I haven't played around with this rule very much, but there aren't many different ways to collide a glider with a dot. It looks to me as if one glider at a time will let you move a dot, or convert a dot into two gliders, or absorb a glider -- but to delete a dot you need two synchronized gliders.

The glider+dot->2 gliders reaction brings up the possibility of a "destruction seed" -- pre-built constellation of dots off to the side of a circuit, that could be triggered cleanly to produce a synchronized salvo to shoot down the circuit once it has gone dormant. Paul Chapman and I spent some time working on a Conway's Life version of this destruction method, for the diagonal "Demonoid" spaceship -- but there's no complete working model of a Demonoid yet. Has any investigation been done along those lines in the Serizawa rule?
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator

Postby simsim314 » March 27th, 2014, 6:00 am

About Self replication there is definitely a confusion of a kind.

I would consider it self replicator the same way Gaoucher's self replicator (in Nobili's rule) is replicator. I think the original Von Neumann replicator is linear replicator as well. Also in Codd's rule all the replicators are of this kind.

Also the original design of Conway's replicator in life, is linear replicator that makes only one copy of itself.

So I think my replicator has the proper "basic" self replicator property, i.e. it replicates itself using universal constructor.

That said, I do agree that a point of having a replicator is the ability of multiple copies i.e. quadratic growth.

So I suggest a change of terminology:

A linear self replicator, and a quadratic self replicator.

A linear self replicators unlike puffers or spaceships include universal constructors in them. That means that they can add any construable addition inside them. I mean you can add a glider gun to Gemini, and this glider gun would travel with it (or write your name). This property is unique for self replicators only, you can't add glider gun to some spaceship and expect it to travel alongside it.

A quadratic self replicator is like linear self replicator, but also exhibits quadratic growth i.e. makes more than one copy of itself.

Many of known self replicators are linear self replicators. Also many of quadratic growth self replicator are not universal replicators, that means that they have a considerable limitation of what can travel alongside them.

Also a Geminiod probably should be defined as Linear Self Replicator that destroys it's parent. Thus being both a space ship and linear self replicator.

===========================================

Now having this linear self replicator in Serizawa, what remains is making it Geminoid as well as making Demonoid.

In Serizawa there is no point of adding destruction arm, due to the fact that one glider doesn't deletes a block but deletes a block and splits into two gliders. Which as you mentioned require destruction seeds. This seeds circuitry can be triggered by single glider that comes from existing arm.

Well I think it's the next challenge for the Serizawa rule - to make a Geminoid.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator

Postby dvgrn » March 27th, 2014, 1:51 pm

simsim314 wrote:I would consider it self replicator the same way Goucher's self replicator (in Nobili's rule) is replicator. I think the original Von Neumann replicator is linear replicator as well. Also in Codd's rule all the replicators are of this kind.

Also the original design of Conway's replicator in life, is linear replicator that makes only one copy of itself.

So I think my replicator has the proper "basic" self replicator property, i.e. it replicates itself using universal constructor.

Absolutely. My (minor) objection to calling this Serizawa self-constructor a "replicator" applies equally to all those Nobili and Codd self-constructing patterns.

simsim314 wrote:That said, I do agree that a point of having a replicator is the ability of multiple copies i.e. quadratic growth.

So I suggest a change of terminology:

A linear self replicator, and a quadratic self replicator.

That's a certainly a good and clear distinction, and I've been using basically the same terms to describe the initial Conway's Life replicator design (linear) and the next-stage diamond-shaped design (which will be quadratic-growth).

simsim314 wrote:Also a Geminoid probably should be defined as Linear Self Replicator that destroys it's parent. Thus being both a space ship and linear self replicator.

Well, there I'm not so sure. I'm probably going to keep the terminology I've been using since the Gemini came out. The Gemini is not a linear self-replicator because there are never even two copies of the glider data streams, let alone an unbounded number -- there's just one copy that moves slowly and throws off some stable stuff along the way for support. If the Gemini doesn't really replicate itself, then it's not really a "self-replicating spaceship".

To me it makes more sense to call the Gemini a "self-constructing spaceship", and if you disable the destructor arm it becomes a "self-constructing puffer". That gets the "universal constructor" reference in there, but stops short of claiming self-replicator status. Seems as if we should save "self-replicator" and "replicator" for things that there are reliably more and more of over time. [That requirement also makes me not entirely happy with HighLife-type and other 1D and 2D parity-rule replicators, where the average population does increase but inevitably crashes back to a fixed value every now and then. Those are clearly replicators -- just not my favorite kind, I guess.]

simsim314 wrote:Now having this linear self replicator in Serizawa, what remains is making it Geminoid as well as making Demonoid.

I should probably not try to push "Demonoid" as an official type of Geminoid; it will end up being vague and confusing. "Demonoid" was originally just a typo for "diagonal Geminoid", but now the idea of self-destructing circuitry is kind of associated with it too -- just because a diagonally moving spaceship can't easily reach its parent with diagonal construction arms, so a different destruct mechanism was needed for efficiency reasons.

But a Serizawa Demonoid would actually have to move orthogonally, so I suppose it should be called an Orthoganoid instead... Pre-seeded self-destructing circuitry -- or self-modifying circuitry in general -- can have all kinds of interesting uses, not just in glide-symmetric spaceships. So we need some more general terminology there. The Gemini spaceship is incrementally self-erasing; the Demonoid or other seeded circuits would be single-step self-erasers.

How easy is it to build a Serizawa "meteor shower" seed that can cleanly annihilate a given piece of circuitry when it's triggered by a single glider, by shooting a large synchronized salvo at it from far off to one side? Does it seem to be easier to integrate the "seeds of destruction" into the circuit itself? If so, how much larger does the circuit have to be to accommodate the extra seeds?

Maybe the easiest universal toolkit for Serizawa would be to find ways to build "freeze-dried slow salvo" seeds. Hit a "seed" arrangement with one glider and get a chain reaction that produces any sufficiently widely spaced salvo of gliders that you want (all on parallel lanes). It looks as if two carefully synchronized salvos coming in at 90 degrees could fairly efficiently clean up any chunk of Serizawa circuitry -- so it would just be a matter of figuring out enough glider turning and splitting variations to be able to get all the relative timings right.
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » March 27th, 2014, 2:57 pm

I was thinking along those lines, and on my opinion it's simply more elegant to add extra self destruct circuitry.

Here is all it takes for the self destruct circuitry.

x = 459, y = 274, rule = Serizawa
39$361.A.A2.A.A$362.B4.B7$431.A.A$362.A.A67.B$363.B8$426.A.A2.A.A$
427.B4.B22$425.A3.A4$361.A3.A54.A9.A$421.B12.A$369.A50.A9.A2$364.A.A
66.A$360.A44.A8$365.B$364.A.A6$174.A4$429.A4$75.A3.A2$50.A$76.A$54.A
22.A$53.A$50.A20.A$205.A3.A39.A3.A$59.A$73.A$56.A118.A32.A43.A9.A98.A
.A$174.A32.A43.A110.B$197.A37.A$180.A32.A43.A$262.A2$178.A32.A43.A2$
360.A.A3.A.A$361.B5.B6$175.B32.B43.B$174.A.A30.A.A41.A.A9$58.A2$77.A$
60.A15.A$99.A$54.A27.A$55.A2$80.A3$359.A$363.A.A2$57.A310.A2$78.A281.
A3.A$59.A17.A$100.A$53.A29.A$54.A2$81.A6$56.A352.A.A$410.B$79.A$58.A
19.A$101.A$52.A31.A$53.A2$82.A4$411.A.A$412.B$55.A2$80.A$57.A21.A$
102.A$51.A33.A245.A.A2.A.A$52.A279.B4.B2$83.A325.A.A$410.B5$54.A2$81.
A$56.A23.A$103.A300.A.A$50.A35.A318.B$51.A2$84.A9$81.B$80.A.A5$53.A2$
60.A$55.A$403.A3.A$49.A$50.A9.A2$408.A$47.A3.A$408.A5$339.A2$334.A.A$
330.A!


I think adding another destruction arm will take at least +50%. Adding the destruction seeds path, will probably make it +100%. But on my opinion it's worth it, because it's the point of those "self constructors" in the first place, you can add to them "stuff" and they will run. All the extra self destruct circuitry will not require a new "design", or rewrite my script that construct the stream. It will only require "extra" stuff to place "on top" of the existing circuitry.

I think this proofs the point of "universality" as clear as it gets - you place extra stuff, you run the same script - and wualla, you have self constructing spaceship instead of puffer.

I didn't like the destruction arm in Gemini, and I will probably make it with seeds.

I also thought that Demonoid meant Diamonoid - Diamoned shaped self replicator. In my opninion the destruction mechanism is a small detail of the self construction ship, because this detail is pretty minor, and in my opinion this destruction arm is kind of "mistake" or shortcut, to the much more elegant and "correct" way of self destruction.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 12th, 2014, 2:50 am

Here is a small update on construction arm recipe. Now It's possible to have universal constructor with only four streams instead of previous ten (two per arm instead of previous five).

x = 8, y = 130, rule = Serizawa
3.A3$2.B$.A.A10$6.B$5.A.A8$.B$A.A3$3.B$2.A.A3$.B$A.A3$3.B$2.A.A4$.B$A
.A3$3.B$2.A.A3$.B$A.A3$3.B$2.A.A6$2.B$.A.A12$6.B$5.A.A6$.B$A.A3$3.B$
2.A.A3$.B$A.A3$3.B$2.A.A4$.B$A.A3$3.B$2.A.A3$.B$A.A3$3.B$2.A.A6$2.B$.
A.A12$6.B$5.A.A!
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby dvgrn » April 12th, 2014, 5:57 pm

simsim314 wrote:Here is a small update on construction arm recipe. Now It's possible to have universal constructor with only four streams instead of previous ten (two per arm instead of previous five).

That should certainly take care of bringing the length down under 10K cells -- and pretty easily under 5K, I would think, with a little more optimization. There are fewer components, so they can be packed more tightly together, so the big initial elbow pushes won't take nearly as long.

With only four streams, will it be possible to activate both construction arms simultaneously (and save a lot more length) -- or are there still unavoidable signal-crossing conflicts? Are delay components still needed on both construction arms, or does it become possible to change the timing of the signals in the actual streams, and get the same effect?

Is there any hope of encoding a two-arm construction recipe into a single stream, to get rid of the signal crossing problems and maybe reduce the number of reflectors?
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 13th, 2014, 2:28 am

dvgrn wrote:Are delay components still needed on both construction arms, or does it become possible to change the timing of the signals in the actual streams, and get the same effect?


It's a good question. The delay mechanism is not so bad on my opinion, it has a price of course, and in this case can also be optimized as well, but it allows to handle timing, and adjust it for small changes in design instead of redesigning half of the components. Perhaps placing a delay mechanism in the reflection mechanism, will solve the crossing problem better, and will allow a wider range of not crossing input.

dvgrn wrote:Is there any hope of encoding a two-arm construction recipe into a single stream


Well the only thing needed for this is a state machine. 4G->G converter. My main concern with this one, that it will be simply ineffective. Adding extra components + making the construction four time slower (two times slower than current, but four time slower than optimal). In Life you have very light weighted components that allow this, I'm not so sure in Serizawa it's possible so easily. But I'll try this idea, I think this direction definitely worth investigation, and single stream of data can be much more "dense" so it will compensate a bit on the inefficiency, hopefully the state machine will not require a too big delay.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 13th, 2014, 3:50 am

OK here is 4G->G multiplier (actually it's two 2G->G).

x = 60, y = 548, rule = Serizawa
38.A$46.A3$37.A7.A.A$34.A16.A$37.A3$5.A3$4.A.A22.A$A2$28.A.A23.A$34.A
4$4.A15.A24.A.A7.A$.A56.A$4.A15.A34.A4$5.A2$30.A9.A$15.A17.A3.A8.B12.
A$20.A.A7.A9.A4.A.A5.A.A3$21.A32.A$29.A11.A42$46.B$45.A.A46$46.B$45.A
.A46$46.B$45.A.A46$46.B$45.A.A46$46.B$45.A.A46$46.B$45.A.A46$46.B$45.
A.A46$46.B$45.A.A46$46.B$45.A.A46$46.B$45.A.A46$46.B$45.A.A!


The main downside is its slowness, as I was afraid (94 ticks between input gliders). It's "optimized" for size based on the interaction between two opposite gliders that toggle a state of a block. Probably not the "smallest possible" but it's pretty small using only 6 reflectors (12 for 4G->G), which is OK.

Now the other downside to large glider delay and single stream is that synchronization will now require more space (or more components).

But it's obvious advantage (no stream sync + only two reflectors per steam) is a good reason to carry on and check it's performance.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby dvgrn » April 13th, 2014, 7:41 am

simsim314 wrote:Now the other downside to large glider delay and single stream is that synchronization will now require more space (or more components).

But it's obvious advantage (no stream sync + only two reflectors per steam) is a good reason to carry on and check it's performance.

The other downside to a single stream attached to a 4G->G component like this, is that a signal is now required on all four streams.

No doubt there are ways of using a glider on one stream to suppress a glider on another stream, with just the right timing -- either mutually annihilating both signals, or letting one or the other continue. But that will also add to the complexity of the design, of course. And it may still be necessary to add lots of NOP operations on one arm, for when you only want to be running the other arm.

There actually may be a good case here for a "serial" design, along the lines of the unfinished diagonal self-constructing B3/S23 spaceship in the Geminoid Challenge thread. It seems as if Serizawa can support either re-usable or one-time switching circuitry. The Demonoid has only one construction arm, but the same idea could be used to reduce four streams to two in Serizawa, or even four streams to one --

Start with a single stream, let it bounce back and forth three times between successive 180-degree reflectors. There will be four 180-degree reflectors in each replicator unit, at either end of the pattern. Then, on the fourth pass, unblock four optional outputs from those reflectors to run the two construction arms. When the construction is done, block up the optional outputs again. This would allow any pattern and timing of gliders in a single stream, with no extra NOP operations to worry about.

The construction could then happen very quickly, with minimal timing-adjustment circuits -- you can just move the actual gliders in the stream to get any relative timing you want, since there are no stream-crossing problems. The overall replication time would still be four times the "optimal" speed because you have to wait until all four parallel streams have advanced to the right place. But the reduction in circuitry might help make up for that extra cost.
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 13th, 2014, 9:03 am

I'm not sure what is your concern after having 4G->G converter? each of the converters can have it's "phase". i.e. after the glider is entering an "interpretation unit" it splits into four gliders, each is input to one of four 4G -> G converters, each converter in his own phase, giving output per each of 0-1-2-3 mod 4 gliders in the stream. For each 4G->G converter the other three gliders are only "state switchers" and only one glider is actually the output.

Also going for this design, it would be almost necessary reuse the same interpreter for both streams (upper and lower), so I made a circuit for that as well. Here is the concept (not optimized for space, and not synchronized between arms - probably both of these are small details, that can be handled pretty easily):

x = 1213, y = 977, rule = Serizawa
98$498.A$533.A3$497.A.A32.A.A$493.A44.A5$489.A4$488.A.A$484.A4$532.A.
A$528.A9.A3$488.A8.A.A$484.A18.A$488.A4$489.A42.A.A$528.A9.A$550.A$
558.A3$549.A7.A.A$546.A16.A$549.A3$517.A3$516.A.A22.A$512.A20.A$683.A
8.A$540.A.A23.A$546.A2$682.A.A8.A$678.A18.A$516.A15.A24.A.A7.A125.A$
513.A56.A$516.A15.A34.A$702.A$591.A2$517.A$590.A.A91.A18.A$542.A9.A
33.A120.A$527.A17.A3.A21.A112.A18.A$532.A.A7.A9.A12.A.A3$533.A32.A41.
A74.A$541.A11.A62.A3$607.A7.A.A$604.A16.A$607.A3$575.A87.A$424.A230.A
2$574.A.A22.A$570.A83.A.A7.A$409.A15.A106.A117.A16.A$95.A333.A94.A73.
A.A23.A39.A$99.A.A307.A15.A178.A2$523.A.A7.A$518.A17.A$100.A307.A124.
A40.A15.A24.A.A7.A$571.A36.A19.A$508.A65.A15.A34.A2$647.A$677.A9.A$
507.A15.A33.A.A15.A$504.A58.A$507.A15.A76.A9.A$585.A17.A3.A21.A16.A7.
A.A21.A9.A14.A$590.A.A7.A9.A12.A.A17.A19.A42.A$646.A31.A9.A14.A$537.A
$531.A.A57.A32.A$599.A11.A$503.A173.A9.A14.A$507.A.A22.A$661.A$642.A
21.A$508.A10.A126.A.A12.A$532.A2$647.A$518.A12.A.A126.A10.A$515.A21.A
$518.A$647.A22.A.A$655.A20.A2$646.A.A$642.A$497.A35.A$494.A41.A$497.A
25.A.A7.A$557.A.A57.A38.A15.A$553.A121.A$617.A38.A15.A$498.A$532.A2$
616.A54.A2$646.A$643.A17.A$646.A7.A.A3$515.A139.A$512.A16.A117.A$515.
A7.A.A3$524.A$516.A9$458.A8.A4$457.A.A8.A$453.A18.A$468.A3$477.A$438.
A3$437.A.A19.A18.A$433.A48.A$459.A18.A4$458.A10$439.A$419.A23.A$423.A
.A13.A4$108.A307.A21.A4$107.A.A307.A141.A$103.A460.A$417.A141.A5$558.
A5$448.A9.A4$449.A9.A18.A$419.A62.A$423.A.A23.A9.A18.A3$424.A$448.A9.
A18.A164$108.B$107.A.A46$108.B$107.A.A46$108.B$107.A.A46$108.B$107.A.
A12$814.A$849.A3$813.A.A32.A.A$809.A44.A5$805.A4$804.A.A$800.A4$848.A
.A$844.A9.A3$804.A8.A.A$800.A18.A$804.A4$805.A42.A.A$844.A9.A$866.A$
874.A2$108.B$107.A.A755.A7.A.A$862.A16.A$865.A3$833.A3$832.A.A22.A$
828.A20.A$999.A8.A$856.A.A23.A$862.A2$998.A.A8.A$994.A18.A$832.A15.A
24.A.A7.A125.A$829.A56.A$832.A15.A34.A$1018.A$907.A2$833.A$906.A.A91.
A18.A$858.A9.A33.A120.A$843.A17.A3.A21.A112.A18.A$848.A.A7.A9.A12.A.A
3$849.A32.A41.A74.A$857.A11.A62.A3$923.A7.A.A$920.A16.A$923.A3$891.A
87.A$740.A230.A2$890.A.A22.A$886.A83.A.A7.A$725.A15.A106.A117.A16.A$
411.A333.A94.A73.A.A23.A39.A$415.A.A307.A15.A178.A$108.B$107.A.A729.A
.A7.A$834.A17.A$416.A307.A124.A40.A15.A24.A.A7.A$887.A36.A19.A$824.A
65.A15.A34.A2$963.A$993.A9.A$823.A15.A33.A.A15.A$820.A58.A$823.A15.A
76.A9.A$901.A17.A3.A21.A16.A7.A.A21.A9.A14.A$906.A.A7.A9.A12.A.A17.A
19.A42.A$962.A31.A9.A14.A$853.A$847.A.A57.A32.A$915.A11.A$819.A173.A
9.A14.A$823.A.A22.A$977.A$958.A21.A$824.A10.A126.A.A12.A$848.A2$963.A
$834.A12.A.A126.A10.A$831.A21.A$834.A$963.A22.A.A$971.A20.A2$962.A.A$
958.A$813.A35.A$810.A41.A$813.A25.A.A7.A$873.A.A57.A38.A15.A$869.A
121.A$933.A38.A15.A$814.A$848.A2$932.A54.A2$962.A$959.A17.A$108.B853.
A7.A.A$107.A.A2$831.A139.A$828.A16.A117.A$831.A7.A.A3$840.A$832.A9$
774.A8.A4$773.A.A8.A$769.A18.A$784.A3$793.A$754.A3$753.A.A19.A18.A$
749.A48.A$775.A18.A4$774.A10$108.B646.A$107.A.A625.A23.A$739.A.A13.A
4$424.A307.A21.A4$423.A.A307.A141.A$419.A460.A$733.A141.A5$874.A5$
764.A9.A4$765.A9.A18.A$735.A62.A$739.A.A23.A9.A18.A3$740.A$764.A9.A
18.A!


The main thing which is still left to solve - is the sequencer algorithm, which is a hold back for all Geminoids for now. I'm hoping to make some very optimized algorithm, that will run up to couple of days for the best output, and will be generic enough to cover a big range of Geminoids. I think everyone who has a final design for Geminoid, will spare few days to optimize the stream sequence.

A rough estimation is that this Geminoid will be much more efficient. My first one had 800 blocks, and spread for 2000 units. This one will have around 350 blocks, and will spread hopefully for less than 500 units, making it at least 8 times more efficient and only twice slower.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby dvgrn » April 13th, 2014, 11:56 am

simsim314 wrote:I'm not sure what is your concern after having 4G->G converter? each of the converters can have it's "phase". i.e. after the glider is entering an "interpretation unit" it splits into four gliders, each is input to one of four 4G -> G converters, each converter in his own phase, giving output per each of 0-1-2-3 mod 4 gliders in the stream. For each 4G->G converter the other three gliders are only "state switchers" and only one glider is actually the output.

That all makes sense. The case I was thinking of was this: if you have two glider streams controlling each of two construction arms, there are bound to be times when arm #1's elbow is already in position but you have to move the other one. If you're sending a glider to each stream in turn, there has to be some way to send control gliders to the arm #1 circuit without having an effect on the elbow.

Of course if you have cheap INCs and DECs you can just do INCn+DECn as a NOP operation -- but that only makes a NOP the same length as INCn+DECn. Something else might have to be done if you just want to do, say, a single INC1 on one side, and a NOP on the other...?

I can see that Serizawa DEC operations are very different from B3/S23 Geminoid DECs -- you can get any large DEC with a single operation. I should probably look into adding something similar for 9hd and 10hd constructor arms -- I can probably produce a 180-degree glider and crash another glider into it later to make a new elbow. At the moment the search utilities that look for elbow operations just throw out anything with a 180-degree glider (!).

simsim314 wrote:I'm hoping to make some very optimized algorithm, that will run up to couple of days for the best output, and will be generic enough to cover a big range of Geminoids. I think everyone who has a final design for Geminoid, will spare few days to optimize the stream sequence.

I'll be very interested to see what you come up with. I've made a few attempts at a Geminoid optimizer algorithm, but with the range of INC and DEC operations available for B3/S23 Geminoids, the time needed to find the absolute best sequence seemed to be best measured in years or decades, not days... and writing even a "pretty good" optimizer was a fairly difficult problem. For the linear replicator I ended up settling for a compiler that was just smart enough that most people probably couldn't see the stupidity immediately.
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 13th, 2014, 7:17 pm

dvgrn wrote: there are bound to be times when arm #1's elbow is already in position but you have to move the other one


Well my solution to this as you mentioned is due to the fact that DEC operation is on one hand pulls back a lot (also due to the fact that the spaces between the gliders are wide), on the other hand the two arms can be simply synchronized. So after DEC operation (with N step) to the correct amount, which is only matter of proper timing, one can achieve the same amount of pulls (INCs) afterwords. More than that the number of pulls (INC) can be made an even number as well.

For example if I need to INC one arm by 10 and DEC other arm by 12. What I do is decrease both arms, but one arm I will decrease by 32 the other DEC by 12 (+2N which are not important). After adding INC 22 (+2N) times, I will get exactly what I want (DEC by 12 and INC by 10).

Other solution is simply to exploit the fact that it's possible to collide a glider with construction arm without any consequences (the glider dies in Serizawa with direct collision) having as many "NOPs" as I need.

dvgrn wrote: I can probably produce a 180-degree glider and crash another glider into it later to make a new elbow.


Yes I think it's great idea that can be useful! I'm really inspired by the fact that Geminoids from different rules can give ideas to each other. This single stream Geminoid design come directly from Life, and this Serizawa Geminoid gives some ideas to Life Geminoids. I'm also working on some Linear Self Constructors in other rules (the GeminoidParticles is just one example), having experience with Serizawa gives a lot of "general" construction ideas.

simsim314 wrote: writing even a "pretty good" optimizer was a fairly difficult problem


Well I approach it as the usual Traveling Salesman Problem (TSP). There are many heuristic approaches to solve the problem, I will take some specific problem (like Geminoid in GeminoidParticles), and will try to optimize it, compering the different approaches (taking into account that not all "cities" are always available). Hopefully to find the approach with best result without carrying too much for performance only the result quality. Hopefully spread the best working idea into a more General Interface that can be programmed for a wide range of construction problems taking into account special construction arms, special constructions that include few operations, and different "interaction widths" of different components.

For some ideas or comparison between heuristic algorithm on TSP, and some ideas how to approach this problem there is a lot on the internet, and a lot of academic researched has been done. Starting from greedy algorithms, or semi greedy (trying only N closest options), dynamic programming, genetic algorithms, neural networks, ant colony optimization, or some other random and statistical approaches. Many of these are applicable in construction order problem for UC with minor modifications. They all have showed a pretty good results in real world problems, optimizing up to 1% from the optimal.

simsim314 wrote:smart enough that most people probably couldn't see the stupidity immediately


Haha... For encouraging, the simplest greedy algorithm, yields a result which are not twice worse than the optimal. So probably even not optimal, some "not totally stupid algorithm" will do an "OK" job.

I was thinking with what algorithm the original Geminoid was designed? Anyway I hope that the "dark ages of construction order" will soon be over, and we will have some nice heuristic to use.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby dvgrn » April 13th, 2014, 8:46 pm

simsim314 wrote:I was thinking with what algorithm the original Geminoid was designed?

Let's see... the glider-pair builder script for 9hd is available here, and it includes a list of the known elbow-move recipes at the time (there are more now.) But it doesn't look as if I ever posted any glider-pair compiler code.

I believe the compiler ended up simply minimizing the cost of each new slow-salvo glider. It did a little more at the beginning -- looked through all of the available glider-output recipes to find the one that left the elbow in the best location. After that it just checked to see which elbow start location was cheapest to get to from the current location, and moved the elbow there as efficiently as possible.

We have combined elbow-move and glider-output recipes like "m-9g-15:e40 e97 o1 e-89" (move the elbow closer by 9, glider lane is -15) and also "m-5g-15:e-10 o-7 o-173 e-16" (move elbow closer by only 5, same glider lane). So at the very least, the compiler should choose the elbow output location that is closest to the next target location -- closest in terms of glider-pair cost, that is.

I don't think I even worried about that level of optimization, let alone the more complicated cases where the compiler should really use a slightly more expensive glider-producing recipe that just happens to drop the elbow in exactly the right location for the next glider output -- add one extra glider pair and save a four-glider-pair elbow move later.

With so many different elbow-move recipes, all about the same cost, it seemed as if no matter how much I worried about this kind of optimization, I'd never improve the total recipe length by more than maybe 10%. It's probably possible to save a lot more than 10% elsewhere -- e.g., by optimizing the slow salvo that does the actual construction -- but that's another problem entirely.
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 14th, 2014, 4:43 am

dvgrn wrote: it just checked to see which elbow start location was cheapest to get to from the current location


This what's called a greedy algorithm (going for the closest first).

dvgrn wrote:With so many different elbow-move recipes, all about the same cost, it seemed as if no matter how much I worried about this kind of optimization, I'd never improve the total recipe length by more than maybe 10%.


In the special case you've described, you probably right. But I do believe that even for your problem, which is a bit different from "standard" two arm build, if you continue to improve the recipes, and have some solution starting from 2 to 8 pair-shoots with very wide range of movements, you will need some sort of optimization of the kind.

Any UC construction problem can be reduced into some smaller problems:
1. What are the next available options (not shadowing anything in between)?
2. What are the distances (construction cost) to those options?
3. What is the best next option?

The first two problems are defined by the construction designs and recipes found for a specific UC, and can be solve pretty fast. The third one is optimization problem. It's clear that if the cost to each available visit is the same or approximately the same, there is nothing to optimize. But in Serizawa Geminoid it's definitely not the case, also in GeminoidParticles it's definitely not the case, I believe that in your case it's true as well, it's just that you used pretty small amount of "local" recipes, for movements. Having a wider range of movement costs and options, will certainly increase the optimization possibilities. Also the fact that you were using a slow salvo, may have some effect on it (instead of two arm).

I was thinking to build something like that in Life, which uses two arms instead of one. This could be much faster Geminoid.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby dvgrn » April 15th, 2014, 8:00 am

simsim314 wrote:In the special case you've described, you probably right. But I do believe that even for your problem, which is a bit different from "standard" two arm build, if you continue to improve the recipes, and have some solution starting from 2 to 8 pair-shoots with very wide range of movements, you will need some sort of optimization of the kind.

Oh, I definitely agree -- it would be very nice to have an algorithm that can reliably find a glider-pair recipe that's within 1% of the optimum, instead of just within 10% or 25%. I originally planned a much slower compiler, which would combine single elbow moves into short sequences which were known to be the most efficient. Eventually you'd have a database of a few million sequences along these lines: "starting with an elbow at 0, with only ten glider pairs you can get Lane -5, Lane -23, and Lane -14 gliders in that order, and the elbow ends up at -16." Then the compiler could try all the most likely ways of stringing these minimal sequences together.

But there turned out to be more immediate problems that needed solving to get a linear replicator to work at all. So I left the glider-pair optimization problem for another year. Hopefully it will be sorted out a little better by the time the first 2D quadratic B3/S23 replicator comes along...!

simsim314 wrote:Any UC construction problem can be reduced into some smaller problems:
1. What are the next available options (not shadowing anything in between)?
2. What are the distances (construction cost) to those options?
3. What is the best next option?

Above I was talking about compiling a fixed slow-salvo construction recipe into actual construction-arm operations ("elbow ops"). As you point out here, the optimization problem is really much more complicated than that.

In B3/S23 stable circuitry, there are usually many ways to place still lifes to produce equally functional circuitry. In particular, for eaters that suppress glider outputs, there are generally several dozen plausible placements, with several dozen plausible recipes for each eater placement. Any of these hundreds of combinations might happen to be significantly cheaper to construct, either in terms of the total number of gliders in the slow salvo, or in terms of the total number of glider pairs needed to program the construction arm to generate that slow salvo.

In both cases, the expense is highly dependent on the precise current placement of the construction arm's hand or elbow. In single-arm constructions, you always want to have a little surplus junk -- the "hand" -- left over on the construction site, so that the slow salvo has something to aim at. Ideally you want the leftover junk to already happen to be be in exactly the right position to start the next object construction. Otherwise you have to waste gliders moving the junk around.

In many cases there are thousands of ways to clean up a construction and leave a little junk behind in different places. So a really good compiler would keep track of all the possibilities, and hopefully find one that matched up exactly with an input for one of the possible recipes for the next object to be constructed.

Another way to save on construction expense is to use "dirty" recipes that leave extra junk lying around. As long as it isn't in the way of the actual operation of the circuit, and as long as the circuit doesn't need to self-destruct later, there's no point in cleaning any extra junk up -- and some of it might well come in handy as alternate "hand" objects for later incremental constructions.

In one-arm Geminoid constructions so far, just for the sake of keeping things simple, the recipes have been clean, and the leftover hand object has generally been a block. Allowing other types of common ash as starting points for construction recipes would immediately cut at least 15% off of the total length of construction salvos. (If you look closely at the linear B3/S23 replicator in operation, you'll notice I did a few experiments along these lines.)

simsim314 wrote:The first two problems are defined by the construction designs and recipes found for a specific UC, and can be solve pretty fast. The third one is optimization problem. It's clear that if the cost to each available visit is the same or approximately the same, there is nothing to optimize. But in Serizawa Geminoid it's definitely not the case, also in GeminoidParticles it's definitely not the case, I believe that in your case it's true as well, it's just that you used pretty small amount of "local" recipes, for movements. Having a wider range of movement costs and options, will certainly increase the optimization possibilities.

Well, I don't know about "pretty small amount". I put together a pre-optimized list of about 100,000 ways to move a hand block, and looked up each new adjustment in that table. Generally it was possible to adjust one of those recipes to fit the current construction situation. That block-move table was combined with another lookup table with half a million recipes for small stable objects. For the linear replicator I just cherry-picked the obviously good recipes, of course, instead of letting an automated compiler find the absolute best combinations.

simsim314 wrote:I was thinking to build something like that in Life, which uses two arms instead of one. This could be much faster Geminoid.

Yes, that was high on my list of possible optimizations for the linear replicator. I wanted to build a single-arm self-constructor mostly just because it hadn't ever been done before, not because it was the most efficient way to do construction.

However, there are definitely a lot of interesting cases where a single arm can do things that are impossible for two-arm constructors (except, obviously, if you use "one-arm emulation mode"!) One example is bending the construction arm around an arbitrary number of elbows.
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 17th, 2014, 4:28 am

dvgrn wrote:In particular, for eaters that suppress glider outputs, there are generally several dozen plausible placements, with several dozen plausible recipes for each eater placement.


Hmm.. I didn't think of that. It's like depending on the route the salesmen came into the city the distance to other cities may vary. This is kinda bad news, but the good news are most of the heuristics will work for this cases as well, just a bit slower due to explosion of options.

dvgrn wrote:So a really good compiler would keep track of all the possibilities


Well as I thought the slow salvo is really a much more complex problem with nuances. For example something else that can help, is to place "few construction blocks" building in parallel, or finding a way to use the debris from dirty recipes. Anyway sometimes you need to draw the line, and limit your options. Having a few thousand cities and few thousand routs to each city, even the best of the heuristics will take much longer. Not saying it's impassible to optimize, just saying that at some point you make "assumptions" and go with them, knowing they are not "absolutely the best".

dvgrn wrote:pre-optimized list of about 100,000 ways to move a hand block...half a million recipes for small stable objects.


Wow I knew it's a big project, but didn't think it's so big. But if I'm not mistaken for the "block pairs" arm movement, you used the standard (Paul Chapman's) 3-4 pairs recipes. Not sure how much expanding the recipes for glider pairs will help, but it might.

Anyway I want to get back to Serizawa Geminoid soon. There are plenty unique challenges there as well.

I was wondering, if this "opposite gliders shoot approach" is applicable for life as well. I mean two gliders shoot at each other at 180 degrees from opposite direction, using timing to shoot a glider from any given location, in some reasonable range, and using a slow salvo recipes to move a block arm (like in Serizawa, although here it's much simpler).

Having a "slow salvo", as the "first arm" as well.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 17th, 2014, 8:43 am

Here is a small recipe for "opposite gliders shoot".

x = 49, y = 27, rule = B3/S23
5$31bo$7bo24bo$8bo21b3o5b2o$6b3o6bo21b2o$14b2o23bo$14bobo4$41b2o$18bo
21b2o$17b2o23bo$17bobo!


As I see it, there would be four 4G->G converters, two for for each glider color, and two interpreters, each per color that would get single glider input and two gliders correctly timed output for the opposite shoot reaction (similar to original Gemini interpreter). It's also simple to make "NOP" operation as seen in the recipe. The rest will be done with slow salvo (that will not only "move" block, but also will shoot output glider as the usual construction arm).
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby dvgrn » April 17th, 2014, 8:53 am

simsim314 wrote:
dvgrn wrote:In particular, for eaters that suppress glider outputs, there are generally several dozen plausible placements, with several dozen plausible recipes for each eater placement.


Hmm.. I didn't think of that. It's like depending on the route the salesmen came into the city the distance to other cities may vary.

Right -- the current object's construction cost varies significantly depending on the location of the construction arm's elbow and the location of the leftover hand block -- and also the "current object" could sometimes be placed in many different locations, each with its own recipe and its own output hand location. As you say, it definitely looks like the kind of problem where you give up on finding the "best" option, and gratefully settle for "good enough".

simsim314 wrote:if I'm not mistaken for the "block pairs" arm movement, you used the standard (Paul Chapman's) 3-4 pairs recipes. Not sure how much expanding the recipes for glider pairs will help, but it might.

I think I understand this point, if you meant "glider pairs" in the first sentence. The odds seem very good that more glider-pair recipes can be found, and that they will shorten the recipe by quite a bit. What I'm finding as I get deeper into the search tree -- 5 to 8 glider pairs, let's say -- is that there are larger groups of optimized recipes where the 90-degree glider output is on the same lane, but the elbow can move to a wide range of locations.

If I build the slow salvo mostly using these recipe groups, there's a lot more flexibility to put an elbow exactly where it's needed for the next object construction -- makes it easier to compile a glider-pair recipe incrementally, doing exhaustive searches just for one object at a time, and have it come out looking reasonably close to optimal.

simsim314 wrote:I was wondering, if this "opposite gliders shoot approach" is applicable for life as well. I mean two gliders shoot at each other at 180 degrees from opposite direction, using timing to shoot a glider from any given location, in some reasonable range, and using a slow salvo recipes to move a block arm (like in Serizawa, although here it's much simpler).

I remember Paul Chapman considered something along those lines in 2003, when we were designing the construction arm that ended up getting used in the original Gemini. It didn't make sense with the technology we had then, but it might actually be workable now.

However, you need at least three gliders to get a 90-degree output -- EDIT: I went and dug up the exact same reaction that you just posted, so no need to quote it again I guess.

Very likely there are 180-degree lanes where two slow glider pairs will produce a clean 90-degree output, but I don't think anyone has done that search yet. The big problem is glider colors -- with this method, your slow-salvo recipes for manipulating the elbow would all have to be one color, like black or white bishops on a chessboard. That's a fairly serious limitation, which would probably more than counteract any advantages of this method. EDIT: In the system you outlined, it seems fairly clear that a separate subsystem for each color of glider, plus having to synchronize two parallel gliders in each of the two subsystems, would all add up to a replicator unit that's several times larger than the current diagonal Geminoid construction arm, and also many times slower.

Systems like Serizawa with orthogonal gliders are very lucky not to have this problem. Off and on I've considered the idea of a Life construction arm that shoots LWSSes instead of gliders from its elbow. I've found a few promising reactions, so I'm pretty sure it can be done, and that universal construction is possible with slow LWSS collisions just about as efficiently as with slow glider collisions. Gemini-style LWSS pairs also look good as a construction toolkit.

But that would take a complete rewrite of slow-salvo search code, and might or might not make a smaller Geminoid or replicator overall. There's no huge database of known "LWSS constructions" equivalent to Mark Niemiec's and H. Koenig's and many others' work on glider constructions, so a project like that would really be breaking into new territory. I'm planning on designing a Geminoid spaceship at some point that uses LWSSes for cleanup, at least, to avoid the need for self-destruct circuitry or an extra destructor arm -- but that's a long way off yet.
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 17th, 2014, 9:36 am

dvgrn wrote: with this method, your slow-salvo recipes for manipulating the elbow would all have to be one color


Interesting thought, did anyone done such research? Maybe it's not so bad after all?

dvgrn wrote:would all add up to a replicator unit that's several times larger than the current diagonal Geminoid construction arm


Definitely. It's not a recipe for optimizing the Geminoid, but as a general construction idea that might be useful in some other cases. For example I was thinking of growing spiral, it might be useful in some "recursive system" that would use the same recipe recursively. It also has some elegance about it, starting from the first spiral node, the design will use slow salvo, and it also might somehow benefit the design.

I'm also thinking of "Universal Geminoid" that works along these lines, so it would be nice to see many Geminoids in many CA's based on same principles (in Life it could be the old p30 technology, that would require 60 streams, but it will use only duplicators and reflectors, and some basic interactions - no sophistication, which does not exist in other CA's).

dvgrn wrote: I've considered the idea of a Life construction arm that shoots LWSSes instead of gliders from its elbow


As a thought, it might be possible to get this kind of design closer to Serizawa design. I think it has some theoretical value as well. Kind of a more "high level CA design", that can be done in some basic system like GeminoidParticles or something along those line, and then "translated" or "compiled" into specific CA like Life or Serizawa or any other rule that has "support" for the basic components.

It might be possible to start from very "strict" requirements, and make a way through into CA's with some less advanced technologies.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator.

Postby dvgrn » April 17th, 2014, 12:51 pm

simsim314 wrote:
dvgrn wrote: with this method, your slow-salvo recipes for manipulating the elbow would all have to be one color

Interesting thought, did anyone done such research? Maybe it's not so bad after all?

To my knowledge, nobody had looked into this question until a few minutes ago... I just wrote a quick script to look through a sample of the half-million recipes I mentioned above, to see how many of them had all their gliders on one color.

Out of sample of 4380 recipes, 27 of them turned out to have monocolored gliders -- all on the same color, for some reason: either my sample, or the search that built the original database, seems to be prejudiced toward starting with the first glider on one particular side of the block. But if you reverse the recipes you get the other glider color, of course.

With a branching factor for the search tree only (say) half of one percent of the size of the standard slow-salvo search tree, it's not really clear that you'd end up with a universal construction set. You might never see some orientations of eaters, for example.

-- But, just as an educated guess, I bet you would! You'd just need maybe a hundred gliders on average to build less common objects, or to do arbitrary small block moves, instead of the current average of ten gliders or less. Only one way to find out for sure... probably oblique's slow-salvo search program could be fairly easily adapted to have a look at this tree.

simsim314 wrote:
dvgrn wrote:I've considered the idea of a Life construction arm that shoots LWSSes instead of gliders from its elbow...

As a thought, it might be possible to get this kind of design closer to Serizawa design. I think it has some theoretical value as well. Kind of a more "high level CA design", that can be done in some basic system like GeminoidParticles or something along those line, and then "translated" or "compiled" into specific CA like Life or Serizawa or any other rule that has "support" for the basic components.

It's certainly possible to build an orthogonal Geminoid in Conway's Life with existing technology. Slow-salvo-constructible glider-to-LWSS and LWSS-to-glider converters are known (or Herschel-to-LWSS, etc.) so the construction data could be stored in an orthogonal loop. And the current construction arm could easily build and trigger LWSS seeds one after another to produce an LWSS slow salvo -- just at a much higher cost.

We'd need a couple of different LWSS seeds to get all possible LWSS placements, though. *WSSes aren't stuck on a single color of diagonal, but if you only build a single type of seed you'll get a somewhat equivalent problem with the phase (since *WSSes are p4, but travel 2 cells every 4 ticks).

With a little luck, there will turn out to be ways to get both *WSS phases directly from an elbow operation -- i.e., using glider pairs, for a diagonal construction arm. That way you wouldn't have to spend a lot of time making and triggering spaceship seeds using slow salvos. I've only run into one phase so far, and haven't figured out how to make the reaction completely clean yet. But that's just because DOpSearch (the only glider-pair search utility that's been written so far) doesn't look for LWSSes -- it just blindly throws them out with all the other explosive patterns.

While we're on the subject, I should mention that theoretically it's also perfectly possible to use loafers as signals in an orthogonal loop, and even to generate a slow-salvo stream of loafers to do constructions with, instead of *WSSes. I have no idea if that last would work; it seems a little unlikely -- there might be too many explosions and not enough annihilation reactions -- but it's interesting to think about. Loafers are the closest thing Life has to Serizawa gliders: no color problems and no phasing problems... and you can fit about seven times as many of them onto the same length tape, compared to Serizawa gliders, since they travel so slowly.

Corderships are even slower, and are also slow-constructible. But you'd need a diagonal memory tape again, and I'd say there's absolutely no hope of doing one-arm constructions with them...! No point, either -- for construction they have no advantages over gliders.
dvgrn
Moderator
 
Posts: 3027
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 17th, 2014, 2:46 pm

dvgrn wrote:Out of sample of 4380 recipes, 27 of them turned out to have monocolored gliders


Since we are talking about slow salvos as a construction arm (replacing the glider pair), and not slow salvo as "build recipe" of other still life, 27 should be enough.

Actually from Serizawa I've learned that the only thing you need for construction arm is 3 OPS: pull-pull with different parity and single recipe for push (or push-push and pull which is less likely). Any integer can be constructed from this. In life we also need two colors for gliders. If from those 27 there are those 5 things (pulls of different parity, push, and black-white glider reflection), we have a way to construct everything we need. Of course not optimal, but hey this is not optimal approach in the first place.

Talking of p30 technology, it might be also useful to check out how much "input streams" are necessary as slow salvo. It's plausible that we don't need ALL the possible inputs. So maybe it would be enough to have 4-5 different "input streams" (by input stream I mean the "trace" of a glider in Life-History), for the basic operations, that would cost only 8-10 p30s (also it's possible to "cross channels", having two p30's for the two glider stream, and 4-5 p30 for different input streams etc.). Considering that p30s are pretty cheap, using two arms (or even one), it could be somewhat cheaper than what we think.

I'm not a big fan of the p30 technology, but considering that in many CAs it's the level of technology we have, it could be nice to experiment with it in life, where we can always "cheat" with some "advanced stuff" if necessary.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Re: Serizawa - Linear Self Replicator

Postby oblique » April 17th, 2014, 5:36 pm

dvgrn wrote:Well, there I'm not so sure. I'm probably going to keep the terminology I've been using since the Gemini came out. The Gemini is not a linear self-replicator because there are never even two copies of the glider data streams, let alone an unbounded number -- there's just one copy that moves slowly and throws off some stable stuff along the way for support. If the Gemini doesn't really replicate itself, then it's not really a "self-replicating spaceship".

Playing the heretic I might be tempted to say, that every spaceship is somehow "replicating" itself in some sense ;)
oblique
 
Posts: 122
Joined: July 16th, 2013, 1:30 pm

Re: Serizawa - Linear Self Replicator.

Postby oblique » April 17th, 2014, 5:47 pm

dvgrn wrote:With a branching factor for the search tree only (say) half of one percent of the size of the standard slow-salvo search tree, it's not really clear that you'd end up with a universal construction set. You might never see some orientations of eaters, for example.

-- But, just as an educated guess, I bet you would! You'd just need maybe a hundred gliders on average to build less common objects, or to do arbitrary small block moves, instead of the current average of ten gliders or less. Only one way to find out for sure... probably oblique's slow-salvo search program could be fairly easily adapted to have a look at this tree.

I'm not quite getting the search space you are describing here. Do you mean: all gliders in one recipe must have the same color? Like in skiping every other "lane"? What are the other parameters of the search?
oblique
 
Posts: 122
Joined: July 16th, 2013, 1:30 pm

Re: Serizawa - Linear Self Replicator.

Postby simsim314 » April 17th, 2014, 6:12 pm

Here is a recipe for a 3 collinear glider pairs for "slow" shoot. I also "proved" just by brute force that two collinear glider pairs always leave some debris.

x = 214, y = 188, rule = LifeHistory
17$194.B$193.A.A$193.2AB$194.A21$170.B$169.BAB$168.2A2B$169.2A13$154.
B$153.A.A$153.2AB$154.A41$105.3A$107.A$106.A18$85.3A$87.A$86.A28$55.
3A$57.A$56.A!


Here is 7 gilders recipe (although it's probably redundant):

x = 218, y = 211, rule = LifeHistory
43$194.B$193.BAB$192.2A2B$193.2A10$181.B$180.BAB$179.2A2B$180.2A24$
154.B$153.BAB$152.2A2B$153.2A42$105.3A$107.A$106.A18$85.3A$87.A$86.A
18$65.3A$67.A$66.A8$55.3A$57.A$56.A!


Let's do some thinking: assuming we'll find some compact "two-glider input" duplicator with simple interpreter (one comes to my mind is just two silvers with two semi Snarks, allowing any distance we choose).

The advantage of slow salvo is that it can shoot on several targets in the "shooting range" (which is the distance between the two interpreters), and it's not "committed" to a single block, so let's say we will use "5 blocks" to shoot upon from this salvo, it could be somehow faster than "back forth" glider pair approach, with single block, cutting time in places where some long "travel" was needed.

Also as a thought it might be possible to create some part of the new copy using direct shoots from the salvo itself, which might make it even faster than current Geminoid. Of course tweaking the Geometry is necessary, placing most of the "mass" of the new copy in the "shoot range" of the salvo.
User avatar
simsim314
 
Posts: 1455
Joined: February 10th, 2014, 1:27 pm

Next

Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 3 guests

cron