<p>Most of the patterns in my collection at <a href="http://www.ics.uci.edu/~eppstein/ca/replicators/" rel="noreferrer">http://www.ics.uci.edu/~eppstein/ca/replicators/</a> were found with a somewhat different heuristic search process, that was intended to find puffers but also turns out to work for replicators:</p>

<ul>
<li><p>Pick a small random seed pattern</p></li>
<li><p>Simulate a moderate number of steps of a modified version of the cellular automaton rule, starting with that seed. The modification is: if you find a small enough set of live cells, separated by far enough from the rest of the pattern, delete them.</p></li>
<li><p>If the simulation finds two states that have the same pattern of cells (but possibly shifted with respect to each other), check it against a collection of known repetitions and shifts and, if it seems new, report it. See <a href="https://en.wikipedia.org/wiki/Cycle_detection" rel="noreferrer">https://en.wikipedia.org/wiki/Cycle_detection</a> for efficient methods of finding repeated patterns that don't involve testing all against all.</p></li>
</ul>

<p>Many replicators eventually reach a state with just two copies of the replicator far from each other, after which the modification to the rule deletes one of them and you get a repetition.</p>

CC BY-SA 3.0
2015-08-03T00:34:10.830Z
2015-08-03T00:34:10.830Z
David Eppstein
<p>My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or Evoloop, are designed by painstaking, lengthy, meticulous design/engineering, which often involves composing units designed by previous mathematicians/hobbyists into more advanced and better behaved self-replicators. In other words, I believe that the current process of designing a self-replicator is following:</p>

<ol>
<li>Take a self-replicator somebody designed before.</li>
<li>Get an idea of improving it, based on some theoretical research that somebody did, a gut feeling, an idea that's been floated around, a dream you had last night etc. The idea should improve the self-replicator with respect to some property that is commonly recognised to be worth improving (lower period, less fragility, sexual reproduction, etc.).</li>
<li>Try to make it work by working through multiple versions of the design, continuously refining the idea, and doing <em>a ton</em> of micro-optimisation. If you succeed go to step 1, and try to improve your new replicator. If you fail, go to step 2 and pick a different idea.</li>
</ol>

<p>This method obviously works very well, as shown by the progress in the field, and is not very different from how <a href="https://terrytao.wordpress.com/career-advice/dont-prematurely-obsess-on-a-single-big-problem-or-big-theory/" rel="nofollow">in general progress in mathematics works</a>. However, I've been thinking lately of a <em>different approach</em> to the problem, and I couldn't find any prior art trying this approach.</p>

<p>The process, let's call it "Self-Replicator Data-Mining" would be following:</p>

<ol>
<li>Take the largest grid you can quickly evolve on your hardware. Size would most likely be limited by the amount of RAM you can devote to a GPU shader, which assuming to be 12 GB, gives a grid of about 100,000^2 squares.</li>
<li>Pick a "rich" set of rules, like <a href="https://en.wikipedia.org/wiki/Brian%27s_Brain" rel="nofollow">Brian's Brain</a>, to get <strong>a lot</strong> of chaos (you'll have to work on a torus).</li>
<li>Run it for about 8 months, periodically saving the state to a hard drive for backups. A back-of-envolope calculation <a href="https://www.wolframalpha.com/input/?i=8+months+*+%28%28672+GB%2Fsecond%29%2F%2812+GB%29%29+" rel="nofollow">shows</a> that this would give you about billion steps of a simulation.</li>
<li>In meantime, design an algorithm which can <em>recognise</em> a self-replicator by looking at the grid after the nth iteration. The algorithm might be very slow, because it only needs to work once. It does sound like the biggest challenge -- and probably would involve some machine learning/ pattern recognition. In principle a parent can replicate to a slightly mutated child, which would make data mining of self-replicators even more difficult.</li>
<li>Publish your newly discoverd self-replicator(s) if you manage to find any. Or go to step 2 and pick a different set of rules, or wait for a graphics card with 120 GB of RAM, or run your simulation for 8 years, or abandon the method entirely in favour of something more fruitful.</li>
</ol>

<p>Has anything like this ever been tried? Is it a path worth pursuing or are there any obvious flaws?</p>

<machine-learning><ne.neural-evol><markov-chains><cellular-automata>
Data Mining of self-replicators
picrin
# Data Mining of self-replicators

(Asked by: username_0 on 2015-08-02)

My current (very limited) understanding of the creative process that leads to the design of self-replicators is that any particular self-replicator, like Universal Constructor, Langton's loop or Evoloop, are designed by painstaking, lengthy, meticulous design/engineering, which often involves composing units designed by previous mathematicians/hobbyists into more advanced and better behaved self-replicators. In other words, I believe that the current process of designing a self-replicator is following:

1. Take a self-replicator somebody designed before.
2. Get an idea of improving it, based on some theoretical research that somebody did, a gut feeling, an idea that's been floated around, a dream you had last night etc. The idea should improve the self-replicator with respect to some property that is commonly recognised to be worth improving (lower period, less fragility, sexual reproduction, etc.).
3. Try to make it work by working through multiple versions of the design, continuously refining the idea, and doing *a ton* of micro-optimisation. If you succeed go to step 1, and try to improve your new replicator. If you fail, go to step 2 and pick a different idea.

This method obviously works very well, as shown by the progress in the field, and is not very different from how [in general progress in mathematics works](https://terrytao.wordpress.com/career-advice/dont-prematurely-obsess-on-a-single-big-problem-or-big-theory/). However, I've been thinking lately of a *different approach* to the problem, and I couldn't find any prior art trying this approach.

The process, let's call it "Self-Replicator Data-Mining" would be following:

1. Take the largest grid you can quickly evolve on your hardware. Size would most likely be limited by the amount of RAM you can devote to a GPU shader, which assuming to be 12 GB, gives a grid of about 100,000^2 squares.
2. Pick a "rich" set of rules, like [Brian's Brain](https://en.wikipedia.org/wiki/Brian%27s_Brain), to get **a lot** of chaos (you'll have to work on a torus).
3. Run it for about 8 months, periodically saving the state to a hard drive for backups. A back-of-envolope calculation [shows](https://www.wolframalpha.com/input/?i=8+months+*+%28%28672+GB%2Fsecond%29%2F%2812+GB%29%29+) that this would give you about billion steps of a simulation.
4. In meantime, design an algorithm which can *recognise* a self-replicator by looking at the grid after the nth iteration. The algorithm might be very slow, because it only needs to work once. It does sound like the biggest challenge -- and probably would involve some machine learning/ pattern recognition. In principle a parent can replicate to a slightly mutated child, which would make data mining of self-replicators even more difficult.
5. Publish your newly discoverd self-replicator(s) if you manage to find any. Or go to step 2 and pick a different set of rules, or wait for a graphics card with 120 GB of RAM, or run your simulation for 8 years, or abandon the method entirely in favour of something more fruitful.

Has anything like this ever been tried? Is it a path worth pursuing or are there any obvious flaws?

**Tags:** machine-learning, ne.neural-evol, markov-chains, cellular-automata


---

## 1 answers

### Answer by username_1 on 2015-08-03. Score: 7 | Accepted answer

Most of the patterns in my collection at <http://www.ics.uci.edu/~eppstein/ca/replicators/> were found with a somewhat different heuristic search process, that was intended to find puffers but also turns out to work for replicators:

* Pick a small random seed pattern
* Simulate a moderate number of steps of a modified version of the cellular automaton rule, starting with that seed. The modification is: if you find a small enough set of live cells, separated by far enough from the rest of the pattern, delete them.
* If the simulation finds two states that have the same pattern of cells (but possibly shifted with respect to each other), check it against a collection of known repetitions and shifts and, if it seems new, report it. See <https://en.wikipedia.org/wiki/Cycle_detection> for efficient methods of finding repeated patterns that don't involve testing all against all.

Many replicators eventually reach a state with just two copies of the replicator far from each other, after which the modification to the rule deletes one of them and you get a repetition.


---

