Replicators

[bprentice]

Basically, it is the last step before an actual replicator pattern is built!
Highlife-like replicators, here we come!

I read this on the Geminoid Challenge discussion, which lead me to wonder what is considered a replicator by members of this forum.

Here are two Square Cell patterns:

Code: Select all

#Rule = Bit Counts
#States = 8
#NS 1,1,1,1,1,1,1,1,1
#NS 1,1,1,1,1,1,1,1,1
#NS 1,1,1,1,1,1,1,1,1
#NS 0,0,0,0,0,0,0,0,0
#RT 0,0,0,0,6,0,0,0,1,0,5,7,0,0,0,0,0,0,0,0,0,0,0,3,3,0,1,3,0,0,0,0,0,0,0,0,0
#Rows = 2
#Columns = 3
#L 3F$3F

Code: Select all

#Rule = Bit Counts
#States = 16
#NS 0,1,0,1,1,1,0,1,0
#NS 1,0,1,0,1,0,1,0,1
#NS 0,1,0,1,0,1,0,1,0
#NS 1,0,1,0,0,0,1,0,1
#RT 0,15,0,0,0,0,6,0,12,0,0,14,0,0,0,1,0,0,13,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
#Rows = 3
#Columns = 1
#L O$O$O

The first is a rare pure replicator somewhat like the extraordinary one just constructed by Dave Greene while the second one is representative of the far more common variety.

Brian Prentice

[bprentice]

simsim314,

With reference to your post here:

viewtopic.php?f=11&t=1293&start=125#p12375

Please comment on the two little patterns above. If you have a Java enabled browser you can run them on this applet:

http://bprentice.webenet.net/Square%20C ... pplet.html

They are patterns R001.sqc and R002.sqc in directory 'User Patterns'. Load them using the file open dialog, this will result in the pattern being centered and selected. To run them first clear the selection by clicking the pattern with the control key depressed. Then step (spacebar) or run (enter).

Brian Prentice

[dvgrn]

Basically, it is the last step before an actual replicator pattern is built!
Highlife-like replicators, here we come!

I read this on the Geminoid Challenge discussion, which lead me to wonder what is considered a replicator by members of this forum.

Can't speak for everyone, but one popular definition goes something like this:

Suppose a pattern P is placed in an empty universe and allowed to run. If you can always find a time Tn at which there are at least n exact copies of P in the universe, for any positive integer n, then pattern P is a replicator.

This definition allows HighLife-style replicators (one-dimensional) and B1357/S1357-style replicators (two-dimensional); those both have a sawtooth population graph, crashing back to a fixed small population at increasing intervals. Linear replicators with monotonically increasing population also count.

So do quadratic-growth replicators, of course -- in fact, those get lots of extra bonus points. Another nice-to-have feature would be if you could find a time after which the population never again drops below N copies, for any N. XOR-based replicators like the HighLife one can't meet that criterion, but they're still obviously replicators.

Under a strict reading of the above definition, by the way, it's not clear that my linear Life self-constructor counts as a replicator. There's a 277-tick phase shift between parent and child copies -- so are the copies really exact?

Luckily anyone who makes such a silly bureaucratic objection can be handed a diagonal row of 856,420 progressively phase-shifted copies of the self-constructor. That ridiculous object is a replicator in the strict sense: after 856,420 replication cycles there will be two exact in-phase copies of the original object, after 1.6 million cycles there will be three copies, etc., etc.

I won't bother adding the messy extra footnotes to the definition to disallow trivial replicators (like a single ON cell in B123/S012345678) or degenerate replicators (like a single OFF cell in most rules, that can instantly replicate itself throughout the universe... but not really!)

I think simsim314's point about "extendability" is a very good one -- a really good versatile replicator should be able to carry along extra information without changing the basic design. A standard HighLife replicator is always going to be 12 cells and period 12, whereas a linear Life replicator variant that includes a pattern of blocks spelling out "JOHN H. CONWAY" will look exactly the same as the original version -- it will just have a slightly longer data tape.

One important distinction here seems to be between "natural" or "simple" replicators like the HighLife's, as opposed to "self-constructing" replicators like von Neumann's, Langton's, Tempesti's, and so on. Both types are certainly replicators, and both types are interesting, but in different ways. EDIT: I believe towerator's comment was about the self-constructing type of replicator (of course, since there isn't any known natural replicator in B3/S23). If a self-destruct option is added to a linear self-constructing replicator, it's fairly easy to make it behave like a really huge and inefficient HighLife replicator, at least in terms of the sawtooth population count.

[dvgrn]

Here are two Square Cell patterns...

From their small size, I'm guessing that these two "Bit Counts" patterns must be different forms of natural replicators. But I haven't managed to get SquareCell to open them yet.

After downloading Square Cell Applet.zip, I tried creating "replicator1.txt" and "replicator2.txt" with the text of the patterns you quoted, and opening those files with SquareCellApplet.jar. The correct patterns appear, and the rule appears to change -- but when I run one of the patterns, no cells change. What am I missing here?

[I briefly tried changing security settings to allow SquareCell to run in a browser window, but ran out of patience when adding a trusted site didn't work, in a couple of different browsers. I'd rather leave the security settings in Chrome the way they are, so that I don't forget to change them back...!]

[bprentice]

Dave,

The small replicator examples can also be run on the Java program 'Square Cell'. Do the following:

Copy the two example patterns to an editor and save them to your Desktop as files R001.sqc and R002.sqc.

Download 'Square Cell.zip' from here:

http://bprentice.webenet.net/Square%20Cell/

Unzip 'Square Cell.zip' on your Desktop. This will give you a directory called 'Square Cell'.

Open this directory and double click on SquareCell.jar.

Adjust the size of the window.

Adjust the size of the cells using the + and - keys on the number pad on your keyboard.

Load R001.sqc using the file open dialog, this will result in the pattern being centered and selected.

Clear the selection by clicking the pattern with the control key depressed.

Run or step the automata with the 'spacebar' or 'enter' keys.

Each of the control buttons have associated hints telling what they do.

Clear the automata.

Load and run R002.sqc

There is a brief note ('Java Square Cell.html') that tells how to use 'Square Cell' here:

http://bprentice.webenet.net/Square%20Cell%20Patterns/

The patterns can also be run by simply downloading SquareCellApplet.jar and double clicking on it.

I've just done all of this on my iMac which runs OS X 10.6.8 and Java 1.6.0_65. Everything worked as expected.

Brian Prentice

[dvgrn]

The small replicator examples can also be run on the Java program 'Square Cell'. Do the following...

Aha! Turned out I had done everything right except for the Ctrl-click-on-the-pattern step. SquareCell seems like the kind of program where you can figure everything out by experimenting with the user interface -- nice tooltips and everything -- but I didn't come across any hints that would tell me that Ctrl+click was a good thing to try. (Felt silly after I read the instructions, though -- you've explained the same thing before, somewhere else).

The problem was that I couldn't tell that the pattern was floating over the universe, waiting to be dropped in -- so when I ran the empty universe, I thought I was running the pattern, and when nothing happened I thought the rule must be wrong somehow. I wonder how many people have tried SquareCell and been similarly frustrated? As I recall, this is actually the second or third time I've downloaded the jar file; it was just the first time I was annoyed enough to ask stupid questions on the forums.

I suspect SquareCell already works the way you want it to, so the only suggestion I can make would be to shift the current Open File behavior to a new toolbar button -- "Insert Pattern From File", maybe. My expected behavior for Open File is that the pattern will appear in a new universe, ready to run. And that's exactly what it looks like it's doing, to a first-time user, so it's very mysterious to have the opened pattern default to floating rather than evolving.

Maybe the other odd thing is that there's no toolbar button or simple mouse operation that can unstick the selection and get things working. A "Drop Selection" button might give people a hint about what's going on...?

[bprentice]

The problem was that I couldn't tell that the pattern was floating over the universe, waiting to be dropped in -- so when I ran the empty universe, I thought I was running the pattern, and when nothing happened I thought the rule must be wrong somehow. I wonder how many people have tried SquareCell and been similarly frustrated? As I recall, this is actually the second or third time I've downloaded the jar file; it was just the first time I was annoyed enough to ask stupid questions on the forums.

In addition to the hints associated with the buttons, there is this note:

http://bprentice.webenet.net/Square%20C ... 0Cell.html

which tells how to run Square Cell and in particular explains how the selector works.

We have had this conversation before, here:

viewtopic.php?f=7&t=1115&p=8175&hilit=Mike#p8153

To return to the topic of this thread, it seems that both of my example patterns fit your definition of a replicator.

Brian Prentice

[alexv]

I've just done all of this on my iMac which runs OS X 10.6.8 and Java 1.6.0_65. Everything worked as expected.

It is recent problem since java 7 upd 51
https://www.java.com/en/download/help/java_blocked.xml

[alexv]

Brian

I would say that your examples just show necessity of accurate definition. Could we use term "replicator"
for a pattern that often appears rather due to some internal property than due to replication of initial
configuration? Such patterns quite often for "fractal-type" CA. Below is an example from "WlAnt family",
(rule WlAnt-4 is in archive here: viewtopic.php?f=11&t=1293 )

Code: Select all

x = 4, y = 4, rule = WlAnt-4
2.A$2.BA$ABA$2.B!

Alexander

PS. WlAnt-4 in new Golly format

Code: Select all

@RULE WlAnt-4

@TABLE

# Reversible Ants
# origin: simpl-c3o
# rules: 10

n_states:4
neighborhood:Moore
symmetries:rotate4reflect

var E1={0,2} #Even
var E2={0,2}
var E3={0,2}
var E4={0,2}
var E5={0,2}
var E6={0,2}
var E7={0,2}
var E8={0,2}
var O1={1,3} #Odd
var O2={1,3}
var A1={0,1,2,3} #Any
var A2={0,1,2,3}
var A3={0,1,2,3}
var A4={0,1,2,3}
var A5={0,1,2,3}
var A6={0,1,2,3}
var A7={0,1,2,3}

0,E1,E2,A1,E3,E4,E5,O1,E6,1
1,E1,E2,A1,E3,E4,E5,O1,E6,3
1,E1,E2,E3,E4,E5,E6,E7,E8,2
1,A1,A2,A3,A4,A5,A6,A7,O1,2
1,A1,E1,A2,E2,O1,E3,O2,E4,2
2,E1,E2,A1,E3,E4,E5,O1,E6,0
2,E1,E2,E3,E4,E5,E6,E7,E8,1
2,A1,A2,A3,A4,A5,A6,A7,O1,1
2,A1,E1,A2,E2,O1,E3,O2,E4,1
3,E1,E2,A1,E3,E4,E5,O1,E6,2

@TREE

num_states=4
num_neighbors=8
num_nodes=22
1 0 2 1 3
1 1 3 0 2
2 0 1 0 1
2 1 0 1 0
2 1 1 1 1
2 0 0 0 0
3 2 3 2 3
3 3 3 3 3
3 4 5 4 5
3 5 5 5 5
4 6 7 6 7
4 8 9 8 9
4 9 9 9 9
5 10 11 10 11
5 12 12 12 12
6 13 14 13 14
6 14 14 14 14
7 15 16 15 16
7 16 16 16 16
8 17 18 17 18
8 18 18 18 18
9 19 20 19 20 

[alexv]

PPS to previous comment: a "simple/snakes" CA may be more appropriate as an example of "fractal-type" CA
viewtopic.php?f=11&t=1293&start=75#p11156
The rule in new Golly format

Code: Select all

@RULE Revsimple

@TREE

num_states=4
num_neighbors=8
num_nodes=20
1 0 2 1 3
1 1 3 0 2
2 0 1 0 1
2 1 0 1 0
2 0 0 0 0
3 2 3 2 3
3 3 4 3 4
3 4 4 4 4
4 5 6 5 6
4 6 7 6 7
4 7 7 7 7
5 8 9 8 9
5 10 10 10 10
6 11 12 11 12
6 12 12 12 12
7 13 14 13 14
7 14 14 14 14
8 15 16 15 16
8 16 16 16 16
9 17 18 17 18

@COLORS

0 255 255 255
1 255 0 0
2 127 255 0
3 0 0 255 

Class of replicators I am talking about - they are satisfying formal definition and even do not produce
extra noise, but "something wrong" with that:

Code: Select all

x = 7, y = 7, rule = Revsimple
3.A$2.ABA$.A.A.A$ABABABA$.A.A.A$2.ABA$3.A!

It replicates with period 8. Number of replicators is rather intriguing:
1,5,9,21,25,29,41,85...
I was really wrong, with choice of name "simple" for that CA 10 years ago

Alexander

PPPS. Relating discussion here
viewtopic.php?f=11&t=1400
The simple/snakes rule is reversible and computationally universal, Fredkin gate has
the same construction as for "Wireless Ants"

So, if to accept the "fractal" pattern as replicator, it is example of reversible CA both universal
and with replicator.

[simsim314]

As far as I can see the point of replicators is to some extend simulate the replication abilities of biological cells. It's also a good start to have a good theory of self replicating physical machines, those machines can make production very (extremely) cheap. This is why I think it's interesting to build self replicators in rules with preservation laws (it will require also the mining process, organization, and construction which is more similar to real world).

The point of extensibility, is more relevant for "encoding" more complex information inside the replicator, like a DNA that can hold the replication mechanism, and construction mechanism of many smaller designs.

Eventually I think the replication can get much more interesting if we could find some way to have evolution inside replicators, which require pseudo random generators inside the replicators themselves (or we can use probabilistic cellular automatons).

Obviously finding a rule with many kinds naturally occurring, evolving (at least competing), self replicators with preservation law is the "ultimate" challenge for CA design as far as replication concerned, but I don't see it happens soon. The more probable way to achieve this is with artificial chemistry, that already have naturally occurring versatile self replicators.

[bprentice]

Alexander,

As usual you have turned a somewhat mundane discussion into a thought provoking exercise. I think Dave nailed the definition with this statement:

'One important distinction here seems to be between "natural" or "simple" replicators like the HighLife's, as opposed to "self-constructing" replicators like von Neumann's, Langton's, Tempesti's, and so on.'

We should call patterns like my 'Bit Counts' examples and your Revsimple and WlAnt-4 examples REPLICATORS and those patterns that require the inventiveness of a human brain SELF CONSTRUCTING REPLICATORS. And perhaps subdivide REPLICATORS into those that leave extra debris and those that don't.

Brian

[alexv]

.. This is why I think it's interesting to build self replicators in rules with preservation laws (it will require also the mining process, organization, and construction which is more similar to real world). ...

Due to the discussion I realized importance of point mentioned not quite long time ago - in real life replicator
may not work in empty universe. Curiously, Revsimple has even two conservation laws,
the script energies-Revsimple.py below lets check that

Code: Select all

# Calculates energies for simple-snakes rule

from glife import rect
from time import time
import golly as g

r = rect( g.getselrect() )
if r.empty: 
  r = rect( g.getrect() )
  if r.empty: g.exit("No selection and the pattern is empty.")
  r.top = r.top - 1
  r.height = r.height + 2
  r.left = r.left-1
  r.width = r.width + 2

oldsecs = time()
maxstate = g.numstates() - 1
En1 = 0
En2 = 0
Ed1 = 0
Ed2 = 0
sn1 = [0, 1, 0, 1]
sn2 = [0, 0, 1, 1] 
kc = [-1,3]

for row in xrange(r.top, r.top + r.height):
       for col in xrange(r.left, r.left + r.width):
         cell = g.getcell(col, row)
         neib = g.getcell(col-1, row)
         En1 = En1 + (1 - kc[sn1[cell]]*kc[sn2[neib]])/2
         En2 = En2 + (1 - kc[sn2[cell]]*kc[sn1[neib]])/2
         neib = g.getcell(col, row-1)
         En1 = En1 + (1 - kc[sn1[cell]]*kc[sn2[neib]])/2
         En2 = En2 + (1 - kc[sn2[cell]]*kc[sn1[neib]])/2
         neib = g.getcell(col-1, row-1)
         Ed1 = Ed1 + sn1[cell]*sn2[neib]
         Ed2 = Ed2 + sn2[cell]*sn1[neib]
         neib = g.getcell(col-1, row+1)
         Ed1 = Ed1 + sn1[cell]*sn2[neib]
         Ed2 = Ed2 + sn2[cell]*sn1[neib]
                
g.show("Energies: Es=(" + str(En1/2) + "+" + str(En2/2) + ")/4=" + str((En1+En2)/8) + 
'; Ed='+str(Ed1) + "+" + str(Ed2) + "=" + str(Ed1+Ed2))

There Es,Ed are some "side and diagonal energies" calculated in specific way from "interactions" between cells.
Despite of that example of replicator may work starting on empty field without change of the energies
(in fact, the replicator is obtained making three steps from single red cell on empty field and similar
diamond-like replicators may be obtained making 7, 15, ... 2^n-1 steps).

We should call patterns like my 'Bit Counts' examples and your Revsimple and WlAnt-4 examples REPLICATORS and those patterns that require the inventiveness of a human brain SELF CONSTRUCTING REPLICATORS.

Agree, but it is difficult to define formally and in fact, Revsimple is making quite nontrivial things usually
expected from human-made replicators.

Alexander

[alexv]

Finally I found recursive equation for number of 2D fractal replicators mentioned earlier (1,5,9,21,25,29,41,85...)

It is more complicated than for 1D method of replication such as HighLife or 'Bit counts'
http://ayvlasov.wordpress.com/2014/06/2 ... -fractals/

Alexander

[Extrementhusiast]

That revsimple replicator looks like a fractal that keeps going back and forth in the amount of complexity.

For another fractal debris-laying replicator, I designed this rule based off of one of the rules in the "Random Three-State Rules" thread:

Code: Select all

n_states:3
neighborhood:Moore
symmetries:rotate4reflect

var a = {0,1,2}
var b = {a}
var c = {a}
var d = {a}
var e = {a}
var f = {a}
var g = {a}
var h = {a}
var i = {0,2}
var j = {i}
var k = {i}
var L = {i}
var m = {i}
var n = {i}
var p = {i}
var q = {i}

0,i,j,k,L,m,n,p,1,1
0,i,j,k,L,m,n,1,q,2
0,i,j,k,L,m,1,p,1,2
1,a,b,c,d,e,f,g,h,0

A single red cell in this rule generates a fractal pattern that left me absolutely speechless. The number of red cells follows that of normal 2D single-cell replicators, but the number of yellow cells is quite different. (I'll edit that in pretty soon here.)

EDIT: The number of yellow cells follows the sequence

Code: Select all

0, 4, 16, 24, 52, 60, 92, 116, 176, 184, 216, 240, 328, 352, 448, 520, 644, 652, 684, 708, 796, 820, 916, 988, 1196, 1220, 1316, 1388, 1652, 1724, 2012, 2228, 2480, ...

Not sure what that sequence is yet.

[alexv]

The pattern is resembling "T-Square fractal"
http://en.wikipedia.org/wiki/T-Square_(fractal)

[alexv]

Finally I found recursive equation for number of 2D fractal replicators mentioned earlier (1,5,9,21,25,29,41,85...)

The more numbers in the sequence now can be found in OEIS
http://oeis.org/A244642
together with interesting graph, see the second one, log scale:
http://oeis.org/A244642/graph

Alexander

[Gamedziner]

Square space-filling tree fractal replicator for rule B1/S8 (starts with only one live cell!):

Code: Select all

x = 0, y = 0, rule = B1/S8
o!

https://en.wikipedia.org/wiki/Space-fil ... e#Examples