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. 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, 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 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?


1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.