Self-replication

A few weeks ago, arguably the greatest fan of cp4space invited me to his birthday party at the Eagle. As I mentioned in my speech, this was where Watson and Crick unveiled their proposed double-helix structure of DNA.

Interestingly, the basic idea of encoding a tape of instructions sufficient for a machine to replicate itself actually pre-dated Watson and Crick’s discovery. John von Neumann designed a mathematical model where a machine reads a tape of instructions to manipulate a ‘construction arm’, which then draws another copy of the original machine.

The first implementations were very inefficient, with tapes of over 100000 bits long. After many successive alterations, William R. Buckley and I were able to massively optimise the machine and reduce its genome length eventually down to a mere 8920 ternary digits; the start of the tape is shown on the right of the image above. The parent constructor (left) literally draws an identical copy of itself and copies its instructions.

This is a very abstract model of self-replication, but it demonstrates the complexities involved. Tim Hutton sought to make more realistic models, which better represent the processes occurring in biological life. The end result was something akin to a two-dimensional bacterium:

Its genome is divided into several genes, each of which contains a base sequence describing an enzyme to produce. These enzymes regulate the chemical reactions required for the cell to replicate itself, such as copying its DNA, invaginating and splitting into two copies of the original cell. Unfortunately, the rate of reactions is very slow, so Tim estimates a replication time of two years when running on a modern CPU.

Tim made this idea (artificial chemistry) into a public challenge, a series of puzzles ranging from propagating a signal along a wire to causing an entire cell to self-replicate. Together, we managed to implement Turing machines in this environment, proving that it is possible for these artificial life-forms to potentially be able to make decisions. One of our experiments involved a Turing machine copying a binary sequence (e.g. 100110 –> 100110100110) and splitting it down the middle to emulate binary fission. After a while, there are many copies of this information floating around:

These initially replicate exponentially, but soon the amount of space limits the growth to quadratic (even on an infinite Euclidean plane). In three dimensions, there is more space so we can reach cubic growth. Remarkably, on a hyperbolic surface, there is enough space for true exponential growth to actually be achieved.

Speaking of hyperbolic planes, I’ve dusted off my hyperbolic tiling generator to create the Diwali-themed banner for cp4space. It was suggested that I make an app for producing tilings of miscellaneous spaces with arbitrary images of your choice. Can I gauge the approximate level of interest in such a program before I attempt to give it a decent user interface?

This entry was posted in Uncategorized. Bookmark the permalink.

21 Responses to Self-replication

  1. Anonymous says:

    Actually, Watson and Crick did not propose self-replication. “Their” structure merely suggested a plausible model for possible DNA replication. Self-replication (procreation) is a considerably earlier biological discovery, which, I dare say, precedes the study of mathematics in its entirety…

    More to the point: the self-replicating machine/patterns you describe feel intuitively different from more trivial self-replicating patterns such as arising in the Game of Life, or Langton’s Loops. But I can’t quite put a point on it: what is their “special” quality? Are they universal constructors? Surely not the biological simulation?

    Great Blog!

    • apgoucher says:

      I didn’t claim that they discovered self-replication, but rather discovered the structure of DNA (it was already known by this point that it was responsible for bacterial transformation, thanks to the Avery-MacLeod-McCarty experiment). Yes, I am inclined to agree that the discovery of self-replication was prehistoric indeed!

      The machines Buckley and I created in von Neumann’s cellular automaton are indeed universal constructors. They are non-trivial precisely because they actively orchestrate their own self-replication, rather than being passively copied.

      • Anonymous says:

        You write that “interestingly, [the tape-encoded self-replication idea] pre-dated [Watson/Crick].” Why “interestingly”? At least to my unburdened mind, this seems to suggest that the tape replication idea in biology somehow followed from Watson/Crick, which is not the case. It may also be worth to point out (to the wider CP4space readership, if not to you personally) that the chemical structure of DNA (bond topology), which is sufficient to determine what is commonly considered genetic information, was known well before W/C. W/C proposed a correct three-dimensional conformation for DNA, based on diffraction experiments performed by Rosalind Franklin and Raymond Gosling.

  2. Pingback: a self-replicating pattern in a cellular automaton, designed by John von Neumann - NSO News

  3. Pingback: Von Neumann universal constructor - Wikipedia

  4. Lucas de la Paz says:

    Can you post the phi9.rle, I’m not going to copy it from the picture by hand.

    • apgoucher says:

      Certainly:

      x = 9040, y = 60, rule = Nobili32
      47.IpAL$43.3IpAJLIL$42.I.2IpAIpALIpA3IL$40.2IJR2pAL2K2IpA2I2L$40.J2IpA
      2IpA4IpAI3L$36.4I2JpAJpAL6I3LIL$36.J4I.IpAI.L5pA2LI2L$36.2J3pARpAJpAR
      LpA3I3pA3L$36.2JpA2I3pAI2pAIpAIpALI4pA$36.2JpAJ3pAJ3pAIpAIpAI5L$36.2J
      pAJpA2IpA3IpA2IpAJ5L$34.2I9J2IpAL3pA4L2IL$33.I.2I.IpAI.IpAI.IpAIpAI5pA
      I2L$33.JR2pARpAJpARpAJpARpA5I2LI2pALIL$31.2I3pAI3pAI3pAI7pALILILILIL$
      31.JIpA2J3pAJ3pAJ3pAIL3pA2IpAIpAIpAIpA10IpA13IpAIpA3IL21IL$31.3pAIpA
      3IpA3IpAIpAIpAIpAIpAJpALpALpALpA5ILpAJpA2IpA13IpAIpA2IL9IJ2IL2IL2ILpA
      I2pA$31.13JIpAIpAIpAI3pALpALpA6IL2IpAIpAIpA13IpALpAIL11I3pAJ2pAJ2pAI
      2pAL$31.6J2IpA3IpAJ7IJ3pA7I2LJpAJpAJpALpAILIL2pAIL2ILI2pAI2pAIL2IL2IL
      ILpAIpA2IpA2IpA4IL$31.15J8pAT8pALIpAIpAIpAIpAI5pAIJI3pAJIpAI3pAI3pAJ
      2pAJIpAI12pA$30.I10J2IpAIJ3pA3IpA2IL7pAILJpAJpAJpALpALIJIJ3pAIpA10IpA
      2IpA13IpA3IpAIpAIpA3I$29.IJI10JpAJ2pAJ2KJ2IpATSIpA6ILIpAIpAIpA2LpAL5pA
      2IL7pA2ILI2pAL2pALILIpAI3pALIL2pALI5pA2QR$27.2I.IpAI.IpAI.IpAI.IpAI.pA
      I3JIpAIpAIpA3IL2IpATJpAJKJIpAIpAIpAIpAI3pAIpAIpAIpAI3pAJIJ2IJIJIJ2pAI
      pAJIJ2IJIpAL5pA$12.4IL10I2pARpAJpARpAJpARpAJpARpAJpAR3pA3JLTSpA2ILpAI
      pA2LI3pA2JKI2L6IpA9IpA11IpA2IpA12IpAJ$9.3IJRQ.12pAI3pAI3pAI3pAI3pAI8pA
      .pAIpAIpALpAJLILJ2pAJpAJ3pA6IpA4IpAIpAI3pAIpALIpAIpALI2pAI3pAIpAIpAIpA
      I2pAI2pAJ$9.J3I2pAKL9I2J3pAJ3pAJ3pAJ3pAJ5pA3JLTSpALpALIpAJILIpA2IpAIpA
      LI2pA5IpA4IpAIpAL2IJ2pAI4pAIJ2pAJ2IJ2pAIpAJ2pAIJ2pAJ$9.2JRpAI2pAL4pAI
      JILpAIJ2pAIJ2pAIJ2pAIJ2pAIJ9pA.pAIpAIpA2IpAIpALJK2JK2pALIpAJ2ILIpA2IL
      IpALpA7IpA6IJ5IJIpA7IJ$9.3pA2KLJL4pAJI2pALJpAJpAJpAJpAJpAJpAJpAJpAJpA
      J2pAIL3JLTSpALpALpAIJpA2LpA2J2KJ2pAIpAI2pALJpAK5pAILILIL2IpA7IJ5IJ$7.
      IL3JpAJLJL4pA2J4pAI3pAI3pAI3pAI3pAI9pA.pAIpAIpAIpAIpAIpALJpAI2pAJ5I2pA
      IpAJpAIJLKpAIJIJIJIpA8IJ$6.I2pA2J2pAJLJILpA2I2pAJpALJpAJpAJpAJpAJpAJpA
      JpAJpAJpAJ2pAJL3JLTSpALpAILKpALpA2LJQRJpAJ22IJ$6.J2pAILJpAJLJK2IpAIpA
      I2pAIpAIpAIpAIpAIpAIpAIpAIpAIpAI9pA.pAIpALIpA2ILpA2LJpAK2pAJ$6.pA2JIpA
      JI2pALJ2pAJKLpAL2pAJ3pAJ3pAJ3pAJ3pAJIpALpAJL3JLTSpALIpAILpALpA2LpAJpA
      JI12pA3IpA6IpAIpAIpAL4pA2IpAIpAL$6.3pA2JpAJ2pAKJ5pAK2pAIpAIpAIpAIpAIpA
      IpAIpAIpAI3pAK7pA.pAIpAL2IpAIpAI2L2pAIpARJ2pAQIpAIpAIpAIpAJ2IpAL2IL6I
      2pA2ILIpAIpALpAIpAL6pAIL$6.I2JpAJKIJLpAJ3pAJ2IpAJKpAKpAKpAKpAKpAKpAKpA
      KpAKpAJLILJL3JLTSpALpAJpALpALpALILJpAJIJpAJ2pAJpALIpAIpALJKLIJpAIpAIpA
      IpALI2pALpA2J2pAIpAI2pA2IpAIpAIpAL$6.JI2pAI3pALpAJ3pAJ2K3IpAIpAIpAIpA
      IpAIpAIpAIpAIJ10pA.pAIpAI.IpAL2IpAIpAJI2J2pAJpAIJIpAJ3IpAIpA3IpA6IpA
      3IpA2IpA2IL11IpAIpAT$6.4JKpAJ3pAJ6pA4K17pALJLJL3JLTSpALpARS2L2pALpALpA
      JpAIJpAJpAJIJL2pAL2KpAJ2K2pALpA5KILpAL2pAJ2KIJ8pAJpAKLKT$6.2JpAKpAIpA
      JL2pAKpAKpAKpA3K11pAL5KL9pA.pAIpA2IpALpA2IpA3IpAIpAILpAK2JKLpAIpA5IpA
      9I2pAIpA4IpA9IpAIpAIpAIL$6.J2KpAJ4pAIpAIpAIpAIpAILJ11pAL3ILJIpAJIJI3J
      IKLpALpALKL3pAL3pAJpAJ2pA3JIJ2ILI3pAIpA2JKL2KpA3K2pAKIpALIpAJIpAIpAI
      2pAK2pALKpA2LK$5.4IpAJ3pAL9pALJK9pALKJI2LJKpA5KJpA3KLpAKpAKpA3KpAKpAK
      pAKpAKTI3JK2pAILIpAJpA2IpAJL2pAJ2KpAJKJ2pAIJ2I5pAIpAJLKpA2KpAK$5.J3IpA
      2IpAIpA2IL3pAIpAIpALJ10K5pA2I5pAJKJ4KLpALpALpAJpAL3pAJpA2JIpAKpAKpA3K
      pAKpA4KpA2K3pAK4pAJ4KLK3pALpAKpA2KpAL2pAQT$5.2J2IpA2IpAIL2pAL2pAI2pA
      2L13I2JL2pARIL4pAJ6K11pAJpA2J2KpAJpAJ3KIL12pAJpAL2ILILJpAKJpALKL5pA4I
      L$4.IpA2JIpA2IpAIpAI2L2pAJpAJ16IpA3IpA14LJpALpAJpA2IpAIpAIpA2Q.IpA4IpA
      IpA12IpAJLJ6pAJpAKpAK2pA3IL4.pALpAL2pA2.pALpALpA.2pA3L.pALpAL2pA4.2L
      4pA3L.pA3L2pA3.4L2pALpALpALpA.2pA4.pALpAL2pA3.L.LpA.pALpAL2pA4.pALpA.
      pALpAL2pA3.2pALpA.pALpALpALpA.pALpALpALpAL2pA3.L.LpA.2pA4.pALpALpALpA
      .2pA2.2LpALpALpALpA.pALpALpALpALpALpA.pALpALpALpA.pALpAL2pA3.LpALpA.pA
      LpALpALpALpALpA.pALpA.pALpALpALpA.pALpALpALpAL2pA3.LpALpA.2pA3.L.LpAL
      pALpA.pALpA.pALpALpALpALpALpA.pALpALpALpA.2pA3.L.LpALpALpA.2pA4.pALpA
      LpA.L.2pA2L3pA3.L.LpALpA2.2pA3.L.pA.pA.2pA2L3pA2.2L.LpALpA2.pA.pA.pAL
      .2pA.L.pAL.pA.2pA3L.2pA2L3pA2.4LpALpA.pA2.pA.pAL.pA.pA.L.LpA.2LpAL.L
      3.pA.2pA2L3pA2.LpA.LpALpA.pA.pA2.pAL.pA.pA.pA.pAL.pA.pAL.pA.pA2.pA2L
      3pA2.LpA2LpALpA2.2pA.pA.pA.2pA3.LpA2.2pA.L2.L5.pA.pA.pA.2pA2L3pA2.pA.
      pALpALpA.pA2.2pA.pA.5LpA.pA3L.pAL.2pA3L.pA.pA.pA.pA2.pA2L3pA2.pA.pALpA
      LpA.pA.pA.3L.pA.pA.pALpA.pAL.2L2.LpAL.4L4.pA2L3pA2.pA.pALpA5L.2pA.L.pA
      L.pA2L.pA3L.pA.pAL4.pA2L3pA2.pA.pALpALpA.pA.pA.pA.pA2.pAL.pAL.pA3L2.
      3L2.L4.pA2L3pA2.pA.pALpALpA.pA.pA.pA.pA3.L.pA.pAL.pA.pA.pAL.pA.pAL2.L
      4.pA2L3pA2.pA3LpALpA2.pA.2pA.pA.pA.pA.3LpA.L.pA.3pA3.2pA4.pA.2pA2L3pA
      2.2pA.LpALpA.pA2.pA5L.pAL.pAL.2pA3L.pAL.2pA3L.pAL.2pA3L.pA.2pA3L.2pA
      2L3pA2.3pALpALpA2.2pA.2L.2pA.pA2.pA.pA.pA.pA.pALpAL.2L2.LpAL.2L2.LpAL
      .3LpAL.L2.pA2L3pA.L3.LpALpA2.2pA2.2pA2.2pA2.2pA.7L.pA3L.pA3L.pA3L.pA.
      2pA2L3pAL3.2LpALpA.2pA2.pA.pA2.2pA2.pA.pA.pAL.pAL2pA2.2L3.pAL2pA2.L4.
      pAL.pAL.pAL.pAL.pA.pA3LpA2.pA3L2.3L2.3L4.L.pA2.pA2L3pAL3.2LpA3L.pALpA
      2.pA.2pA2.pA.2pA2.pA.pA2.2pA3.2pA2.2pA2.pA.pAL.pAL2pA2.2L3.pAL.pA.pAL
      2.LpA2.pA.pA.pA.pA.pALpA.LpA.LpA.L2.L.pAL.pAL.pAL.pAL.pA.pA.pAL.pA.pA
      .pAL.pA3LpA2L3pAL3.2LpALpA.2L.pA2L2.2L2.3L2pA2.L.L2.2pA2.pALpA.L2pA2.
      2L3.pAL.pAL.pAL.pA.2pA.2pA3.LpA2.pALpA.LpA.3L.pAL.pAL.pAL.3pA2.2L4.pA
      2L3pAL3.2LpALpA2.pA.pA.pA.pAL.pA.pAL.pA.pAL.pALpA2.2pA2.pA.2pA2.pA.2pA
      2.pA2L.pA2L.2pA2.pA.2pA2.pA2LpA2.2pA2.pALpA.L2.L2.L2.pA.pA.2pA3.pA3.pA
      3L2.2pA3.pA3.pA2.L.pA.pA.pAL.pA.3pA3.LpA3.pA2L3pAL3.2LpAL2pA2.L.pA.L.
      pAL.pA2.2L2.3L.pA3L.pAL.pA2.3L.pA3.pA5L.pAL.pAL.pAL.pAL.2pA.8LpAL2.8L
      2pA2.2LpA3.pA2L3pAL.L2.LpAL.pA.pA.pAL.pAL.pAL.pA.pA.pAL2pA2.2L3.pAL.pA
      .pAL2pA2.L4.pAL.pA3L3.pA3.2pA.LpA.L2.L2.L2.pA2.pA7LpA2.pA.pAL.pA.pA.pA
      3L3.pAL.pA.3pA2.L6.2pA2L3pAL.L.2LpALpAL.LpA2L.pA2L.5L.2pA.2LpA2.2pA.
      3L.pAL.2pA2.2pA.2LpA.2L.2pA2.pA.pA7LpA2.pA.pA5LpA.LpA.pA.L.pAL.pAL.2pA
      .2pA3.LpA2.pAL.2pAL.2pAL2.L.pA.pA3.L.L2.2L2.L2pA2.L6.pA3.2pA2L3pAL.L
      2.LpA6LpA.L.pA3.pA.pA3.pA2.L.pA2L3.pA3.pA3.pA.pA3.pA2.3L.pAL.pAL.pAL.
      pA3L.pAL.pAL.pAL.pAL.pA3.L2.L2.pAL2.L.pA.2pA2.pA.pA.pAL.pAL.pAL.pA7.pA
      LpA3L.pAL.2pA3L.pAL.2pA3L.pAL.2pA3L.pAL.2pA3L.pA.2pA2L3pAL.L.pALpAL2.
      L2pA2.L.pA2.pAL.pA.pAL2pA2.L.L2.pAL2pA3.2pA2.pAL2pA3.LpA2.2pA.pA2.pA.
      L4.3L.2pA.pA.L.pALpA2.pA.pALpAL.2pAL2.pA7.3LpAL.2L2.LpAL.2L2.LpAL.2L
      2.LpAL.2L2.LpAL.3L2pA2.L4.2pA2.pA.pA.pA.2pA2L3pAL.3pALpAL2.2L.pA2L.pA
      L.pAL.pAL.pA3L.pA2L.2pA.L.pAL.2pA.L.pA3L.pAL.pAL.pA.pA.pA.pAL2pA3.LpA
      2.pA3L2.L2.2L2.pA2.2pA3.LpA.L.pAL.pALpA11L.pA3L.pA3L.pA3L.pA3L.3pA2.L
      .pA.LpA3LpA2L.pAL.L3.pA.pA.2pA2L3pA2L2.2LpAL2.2L3.pA2L2.L.pA2L3.pA.pA
      2.2L3.pA4L.pA2L3.pA.2pA.L.pAL.pA.pA.pA.pAL.pA.pA.pA.pA.pA2L.2pA.L.pAL
      .pA.pAL.2pA2.pA2.L.2pA.LpA.LpAL.2pAL2.pA7.5L2.3L2.3L2.3L2.3L4.2pA3.2pA
      2.2pA2.3L.pA.pA.pA2.pA2L3pA2L2.2LpAL2.2pA3.pA3.pAL.pA3.pA.pA.pA.pA.pA
      2.2pA3.LpA2.pAL2pA3.pA3.pALpA.L.2pA2.pA.pAL.2pA2.pA.pA2.L.2pA.2L.L5.L
      2.pA.L.pAL.pA.pAL.pAL.pALpA12L3.pA2L3.pA2L3.pA2L3.pA2L3.pALpA2.pA3.pA
      4LpA.2L.pALpAL.L4.pA2L3pAL.pA.2LpAL3.pA.pA.pA.pA.pA2.2pA3.pA3.pAL.pA.
      2pA2.2pA2.2pA2.pA5L.2L2.pA.2L.pAL.pA2L3.L.L4.LpA.pA.L3.pALpA.LpA.LpAL
      .2pAL2.pA7.pA2.pA2L2.L2.L2.L2.L2.L2.L2.L2.L2.L2.pA.2L.pA2.4LpA3.pA2.L
      .4LpA2L3pAL.2LpALpAL2.2pA3.pAL2.pAL.pA3.pA3.pA3.pAL.LpA4.pAL2.L.pA2L.
      pA.pA.pA.pA.pA2.2L.pAL2.pA.L.pAL.pAL.pAL.pAL.pALpA12L.pA3L.pA3L.pA3L.
      pA3L.pA4L4.4LpA3.pA3.L6.pA2.2pA2L3pAL2.pA.LpAL2.2pA2.pAL3.pA2.L2.pAL.
      LpA2L3.pA.pA.LpA.L.LpA2.pALpA.LpAL.2pAL2.pA7.pA3.2L2.L2.L2.L2.L2.L2.L
      2.L2.L2.L2.pA.L2.2L.pA.pALpA2.pA2.pA3.2L4.2L.2pA2L3pA.pAL.pALpAL2.2L.
      2L2.pA.pA.LpA2.pA.pAL.2pA.L.pALpA12L.pAL.pAL.pAL.pAL.pAL.pAL.pAL.pAL.
      pAL.pA2L.pAL.pAL.pA.pA.L2.pA3.L2.pA2.pA2L2.pA2L3pAL.pAL.LpALpA.L.pAL.
      pA.pA4LpA.L.pAL.pAL2pA3.LpA2.pAL.pA.pA.3pA2.L.pA.L.pA2.L2.LpA.pA.LpA.
      LpA2.pAL.2pA.LpAL.2pAL2.pA7.pA3.LpA.L.pA2.3L2.3L2.3L2.3L2.2LpA.LpA2.L
      2.2L2.pA.2L.pA2.L.pA4.LpA2L3pA2L.3LpALpA2.pA6LpA.L.pALpA.L.pAL.2pA2.pA
      .pA2L2pA3.LpA2.2pA2.pA.2pA.L.pA.pA2.L.pAL.pAL.pAL.2pA2L.2L2.pAL.2L.pA
      2LpA.pA2.pAL.pAL.pA.2pA.L.pALpA10L.4L.pAL.pAL.pAL.pAL.pAL.pAL.pAL.pAL
      .pA2L.6L3.3L2.L4.3LpA2L3pA2L.3LpALpA.L.pAL.pAL.pA.pA2L.pAL.pA2L4.LpA.
      2L.2pA.L.pAL.pAL.pAL3.2pA2.L2.pA.L.pAL.2pA.L2.2L2.L3.pA2.L2.pA2.2pA.L
      pA.LpA.L2.LpA.LpAL.2pAL2.pA7.pA3.pA2.2pA3.L.2L.2L.2L.2L.2L.2L.2L.2L.L
      2.L.pA.pA2.3L2.LpA4.pA.L2.L5.2pA2L3pA2L.pA2LpALpAL2.L.pAL2pA2.L.L2.2pA
      2.pA.pAL.pA.pAL.pA.pA.pAL2pA3.LpA2.pAL.pA.pA.pAL.pAL.pA.pA.pA2.L.pA3.
      pAL2.2L5.pA2.L.pAL.pA.2pA.L.2pA3L.pAL.pALpA3L2pA2.L3.L3.pAL.pAL.pAL.pA
      L.pAL.pAL.pAL.pAL.pA.pA.pA.L.L2.3L2.LpA.3L.pA2L.pA2.pA2L3pA2L.pA2LpAL
      pAL3.LpA2.2L2.8L3.pA.L.L2.2LpA.LpA2.pA.L.L.L.L.2LpA.2L.L.L2.L.L.LpA.
      2LpA4.pA2.L2.L3.pAL2.LpA.LpA.2LpA.pA.pAL.2pAL.2LpA.LpAL.2pAL2.pA7.pA
      3.pA3.pA.2pA2.LpAL.L.L.L.L.7L2.3L2.L.L8.pA2L3pA2L.pA2LpALpA2.pAL.pAL.
      pAL2pA3.2pA2.pAL.pA.pA.pA.pAL.pA2L2pA3.2pA2.pAL.pA.pA.pA.pA.pAL.pALpA
      2.L5.2LpA2.pAL.pAL.pA.pA.pAL.pA.pALpA.L.pA.pAL.pALpA12LpA2.L.L.L.L.LpA
      .2pA2.L.L.L.L.L.2L.2L.2L.3LpA3.L.pAL.2L4.pA2L3pA2L.pA2LpAL.LpA.pA.L.L
      pA.2L.3L.pAL.pAL.pA2.L.2pA.L.pA.3L.L.L.2L.L.LpA2.L4.L.pA3L.2pA2.pA.pA
      3.pA6.2L2.L2.3LpA.3LpA2.LpA.LpA.LpA2.L.pA7.pA3.pA2.L.pA2.pA2.pA.pA.2pA
      .2pA2.L.L.L2.pA2.pAL.pAL.pAL.pAL.pA4L2.L.L.L2.pA2L3pA2L.pA.LpAL.2L.L.
      2L.LpA3.L.pA5L.pA.pA3.pA2L3.L2.L.L.L2.2LpA3.L.pA.pAL2.L.2pA2.pA2L.L7.
      2pAL3.2L.2L.2L.2L.L.L.2L.2L.2LpA2.L.L.2L3.L.L.L.L.2L.L2.pA.pA2.pA3.LpA
      .9L.L2.pA.9LpA.3L2.L.pA.pA.pA.2pA2L3pA2L.pA2LpALpAL2.pA2L.2LpA.L.L.2L
      .2LpA.3L.LpA2.L.L.L.L2.4L.4L.L.2L.L.L.L.2L.2L.L.L.2L.2L.2L.pA4.L2.3LpA
      .L2.LpA.LpA.LpA2.L.L.L.L3.L2.5L.pA.pA5L2pA2.L4.L2.pA.L.pAL.pA3LpA2.pA
      .pAL.pAL.pA.pAL.pA.pA.pA2.pA2L3pA2L.pA2LpALpA2.pA.pA.pA.pA5LpA2.LpA.L
      3.2L2.pA2.2pA2.pA.2pA.L2.2pA2.L.pA.LpA2.pA.L.L.L2.L2.L.L.L4.L2.2pA2.L
      .L.L2pA3.LpA2.L2.4LpA2.2pAL.3LpA5.2pA2.2L3.2pA.pA.2L.pA2LpA.2LpA2.pAL
      .pA.pAL.pA.pA4.pA2L3pA2L2.pALpALpA2.pA.pA.pA2L.2L.2L2.6L2.pA3.L2pA2.L
      .pA2.pAL.pAL.pA.pA.pA.pAL.2pA3LpA2L.pA2L.L.pAL.pAL.pA.pAL2.LpA.L2.2pA
      2.3L.pA.L.pA.pA.pAL2pA2.LpA3.pA2.L2.2LpA.pA2.pAL.pAL.pA.pAL.pA4.L.2pA
      2L3pA2L.2pALpAL.L.L.L.L.2L.LpA4.pAL.pAL.pAL.pAL.pA.pA3.pAL3.3pA2.2L2.
      LpA2.pA3.L.L.L.LpA4.pA3L2.L2.3L3.pAL.pAL.3pA2.2L2.LpA.pA4.pAL.pAL.pA.
      2pA3L2pA2.2L3.pAL.pAL.pA.pA.2pA.LpA2.pAL.pA.pA3L.pA4.pA2L3pA2L.2pALpA
      L2.2pA3.LpA2.pA.L.L.2L.2L.2L.2L2pA2.2L3.2L2pA3.LpA2.2L.2L.L.L.LpA2.LpA
      .L4.2L.2L.2L.2LpA3.LpA.pA.L.pA5LpA.L.pAL.pAL.2pA.4LpA.L2pA2.2LpAL.2L
      2.L.pA.pA.pAL.pAL.pA3.pA.pA4.4LpA2L3pA2L.2pALpALpAL.L2pA3.4L3.8LpA.L.
      pA8LpA2.pA3L.2pA2.pA.pALpA2.pAL2.2LpA.L.pAL.2L2.L2.L2.3L2.pA3.LpA.pA
      4.pA2.6L.pAL.pAL.pA5L.2L.4L.pAL.pAL.pAL.pAL.pAL.pAL.pAL.pA.pA.pA.pALpA
      3.L.pA3L8.pA2L3pA2L.L.LpAL2pA2.L3.L.3L.pAL.pA2LpA.L.pA2L.pAL.pA2.LpA.
      L.pA.LpA.L2.LpA2.2pA.3L3.pA.pAL.pAL.pA.pA5LpA.pA.L2.2LpA2.pA.pA.2pA2.
      2L.2L.2L.2L.2L.2L.2L.2L.2L.2L.2L.2L.2L.2L.2LpA.LpA2.pA.pA.pA3L5.pA9.pA
      .pA.2pA2L3pA2L.pA.LpAL4.2pA2.2L3.pAL.pA.pAL2pA2.L.L2.pA2.pA2.pA.3LpA.
      2L.2LpA2.L.L.L2.L2.3L2.pA3.LpA.pA.2L2.LpA.pA2.pA.pA.pA2.2LpAL2.3LpAL
      2.3LpAL2.3LpAL2.2L2pA3.2pAL3.L.L2.pA.LpA.L.L.L.2L.2L.L6.L.pA.pA.pAL.
      2pA2L3pA2L.pA2LpAL4.2LpA2.3pA3.2pA2.L2.L2pA3.LpA2.LpA.2pA3.LpA2.L3.LpA
      3.L.2pA.LpA.L3.2L.3LpA3.L2.7L.3L.2pA.pA2.L.L.L2.2LpA4L.pA.2pA4L.pA.2pA
      4L.pA.2pA4L.pA.2pA4LpA4LpA4LpA4L.pA.pA.pAL.pA.pAL3.L.2LpA3.2L2.L2.L.L
      .pA4.pA2L3pA2L.pA2LpAL2.L.pA.pA.pA2.L2pA3.2pA2.pAL2pA3.LpA2.pAL.pAL2pA
      3.LpA2.2pA2.2L2.pA.2L.3LpA.LpA3.pA3.3L2.pA3.pA2.2pA.pA2.pA4.pA2.2LpA.
      3LpA.3LpA.3LpA.3LpA.3LpA.2LpA.3LpA.4LpA.3L5.pA3L.pA.pA2.L2.L.pA3LpA2L
      3pA2L.pA2LpAL4.2L2.L2.pA.L.pAL.pAL.pAL.pA2L.pA2L.pAL.pA4.2L.pAL.pAL.pA
      2.L.2pA.LpA.3LpA.L.2LpA3.L2.L2.pA3.L.pA.4L2.pA.L2.LpA.LpA2.2pA.LpA2.
      2pA.LpA2.2pA.LpA2.2pA.LpA2.2pA.L.L.L.LpA2.2pA2.pA.pAL.pAL.L.L3.L.L3.
      2LpAL.L5.pA.pALpAL.L6.pA2L3pA2L.pA2LpAL4.L2.L.pAL.pA2.2pA3.LpA2.pA3.pA
      .pAL3.pA.2L.L3.pA3.pA4L.L.2L2.pA.2L.LpA.LpA.2L2.pA3.6LpA4.2pA.L2.LpA.
      2LpA.pA.2L.pA3L.pA3L.pA3L.pA3L.pA2LpA2.pALpA2.L.L.L.LpA.L.L3.L.2L.3L
      2.L2.3L2.4LpA2L3pA2L.pA2LpAL4.4L2pA2.2LpA2.L3.2LpA3.pA2.pAL.pAL.pAL.pA
      L.pA.pALpA.LpA.LpA.6L2.L2.pA.L.LpA3.2L2.LpA.3L.pAL.2LpAL2.L.2LpAL2.L.
      2LpAL2.L.2LpAL2.L.2LpAL2.LpA3.LpA3.pA2.pA.pAL.2L.2LpA.5L.L2.L.L.LpA9.
      pA2L3pA2L.pA2LpAL4.2pA2.LpA2.LpA2.pA3LpA2.L2.pA2.2L.2L.L2.pA.L.pA.pA.
      pAL.3LpA2.pA.pA2.pA3.3L3.2LpA3LpA.LpAL2.L2.pA2.pA2L.LpA.L2.pAL2.pAL2.
      L2.pAL2.pAL2.L2.pAL2.pAL2.L2.pAL2.pAL2.L2.pAL2.pAL2.LpA4.pA.7L3.2pA2.
      2L.2LpA3.4L.2L8.pA2L3pA2L.pA2LpAL4.L.pALpA.L.pALpA.L.2pA2.pA.2pA2.pA.
      2pA3.3L.L.L.2L2.5L.2L.LpA.pA2.pALpA2.2L.2L2.pA3.L2.L2.LpA.pAL.3L.pA.pA
      L.2pA.L.pA.pAL.pALpA3LpA3L.pALpA3LpA3L.pALpA3LpA3L.pALpA3LpA3L.pALpA
      3LpA3L.pAL.pAL.pAL.pA5L2.L.L2.LpA2.4L2pA3.pAL3.pA2L3pA2L.pA2LpAL4.pA.
      L.pA3L.pA.LpA.L.2pA.L.pAL2.2L.2pA2.pA.pA.pA.pA.pA9LpA2.L.L.2L2.pAL3.
      2L.L.2L.2L.2LpA.pA.pA2.2pA.2L4.LpAL2.2LpA.2L2.L2.L2.L2.L2.L2.L2.L2.L
      2.L2.LpA2.pAL.2L2pA3.LpA2.2L.L.3L.L3.2L.2L.pA3.pA6.pA2L3pA2L.pA2LpAL
      4.2pA3.LpA2.pAL.pA.pA.pA.pAL.pA.pAL.pA.pA.pA2.pA.2pA2.LpAL2.LpA.LpA2.
      pA2.L.L.2L.L2.L2.pA2.2L.2LpA.2L.pAL.pA2L.L.L.2L.2L.2L.2L.2L.2L.2L.2L.
      2L.3L.pA.L.L.L2.9L.3L.L4.2L3.2L6.pA2L3pA2L.pA2LpAL3.pA.pA.pA.pAL.L.L
      2.4L.L.L.2L.LpA.L2.pA.2pA2.LpA3.LpA2.L.2L5.L2.5L2.pA.pAL2.pA2L.LpA.pA
      .LpA2.L.pAL.pA.pA.pA.pA.pAL.pAL.pAL.pAL.pAL.pAL.pAL.pAL.pAL.pAL.pAL2.
      2pA2.2L3.pA.L.2L.2L.L.L4.2L4.pA2L3pA2L.L.LpAL3.pAL2pA3.2pA2.pAL.pAL.pA
      L.pA2.2pA2.L.L.L.L.LpA.LpA.2L.L.L4.8LpA5LpA2.LpA2.L.L.2L.L.L.L.L.2L.
      2L.2L.2L.2L.2L.2L.2L.2L.2L2pA2.2LpA2.L2.3L2pA3.LpA2.L2.L4.pA2L3pA2L.L
      .LpA2L.pA2.L.pAL.pAL.pAL.pA3L.pA3L2.2pA2.L.pA.L.2pA2.3pA3.LpA2.L2.4LpA
      L.2pAL5.L.L.L.2L.2L.L.L.2L.L.L.L.L.2L.2L.2L.2L.2L.2L.2L.2L.2L.2L2pA2.
      3pA2.L4.pA2L3pA2L2.pALpAL3.pA.pA7L3.pA.pA5LpAL.LpA2L.pAL.LpA2L.pAL.LpA
      2L.pAL.LpA2L.pAL.LpA2L.pAL.LpA2L3.2L2pA2.L.L2.pAL.pAL2pA3.LpA2.pA.L.L
      .L.2L.L.L.L.L.2L.2L.2L.2L.2L.2L.2L.2L.2L.2L2pA.L5.L2.2pA4.pA2L3pA.pA.
      3LpAL2.pALpAL2.pALpAL2.pALpAL.3pA.pA.L.3L2pA4.pA2L2pA3L2pA4.2L2pA$4.
      2JI3pA2IpAILpAL3IpAIpA13I.2IpAIpAIJ2L13pAIpAIpAIJ3pAJpAJ3pAIJL4KJIL
      13pAIJpAIJ2IpAIpAIpAIpAIJLKpA5K$4.4pA2J2IJIpAIpA3IpAJpA15RpAL4pALIpAI
      pAIpAL5pAIpA2LpAJLpAKpAKpAK2pA2JpALKL3KpAKpA6KpA13KpAKpAKpAKpA3K6IJ$
      4.4J3pAIpAJLpA4IpAIpAIpAIpAIpAIpAIpAI3pAKpAK5pAIpAIpAI6pAJIJ2LpAJLJ3pA
      JpAJpAJpAKpAIpAL2pAJpAILpA2ILI3pAIL8pAIpAL8pAJ5QR$.3I4JI2J3pA3ILpALpA
      KpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKL3IL2pAJpA2L5pA2IpAIpA2IJ
      3pALILpAJpALKIpALpAJIpAI2pAIpAL2pAIpAI2pAK10pA$IpA3IpA3JKpAKpA3KpALpA
      LJ2K9T2pAT3pAT3pAT3pAT2pAJ3I2LpAJ2pA2LpAJLJ3pAJpAJ3KLpAK2pAL2pAKILJ
      11IpA2IpA13I2J$2JIKpAJpAJ2pAJLpA2KJpA2IpA3IpA.pA.pA.pA.2IpA.2IpA.2IpA
      .2IpA.2pAJ3K2LI2pAK7pAJpAJL2pAKpAKJpALpALIpAJLKJ6KL6KpAJ9KIL2pA2J$3pA
      IpAJpAJ2I3pAI2J3pAL4pAL3pAL2pAL3pAL3pAL3pAL3pAL3pALpAKL2JI2LILJLJ3pAJ
      LJLpAL2pAK2pALJpAKL6IpAIpA6IpA9IpAJ3IpAJ$3JRpA2I2JRpAKJ2KJ2KpAIpA2ILI
      L3KpALILpALILpALILpALILpALILpALpAJpALJ3pAKIpAJLJpAJpAJLpAKpAL3pALpALI
      pAJIpAIpAI2pA2JIpAI2pAI2pAIpAIpAIpAIpALJpAJ2pA2J$4pAJ3pAJpAJ2pAKpA2KJ
      KpAL4KLpAIL2pAI3pAI3pAI3pAI3pAI2pA2L2pALpAJpALIJL6pAJLJ2pALpALK2pALJpA
      2K4pAIJIJKpAKIJpA2IJ6IJIpAIpAJpA2J$4JL2KpAJK5pALpAKpAKpA2ILJLpAJLpATpA
      KpATpAKpATpAKpATpAKpATpAKpAI3pALpAJ2pAJLKpALJpAJ6pALpALpALpA2IpAIpAIpA
      IpAILJLpAKJ15K4pA2J$4JpAK4pAJLpAKpAKLIJ6pAKIJLpA2TJpA2TJpA2TJpA2TJpA
      2TJpALK2pAILJpATpAL.pAKJ3pAJLJ2IL2pAKpA3IpALJKpAKpAKLJKL3pAIL16pA2J$
      8J3pAKLpAJKpAJ5pAIpAIpAIpAI2.pAI2.pAI2.pAI2.pAI2.pAIpA2IpALIpA2I2pARL
      pAJpAJpAJLJpAKpAKLpAI2LKpAK5pAJpA3K3pAJL2IL2ILIpALpAIpALpAIpA2J$3JIJI
      pAKpAKJK2pA2KpA6KpAKpAILpAJpAJpAJpAJpAJpAJpAJpAJpAJpAJ2pAL2pATpA2J2pA
      LI3LpAKpAKpA2KpAKTJpA3KL9pA5ILI2pAJpAIpALIpALKI3pAIpAL2J$3JpAKJ2pA2JK
      2pAK9pAJ3KI2pAKpAKpAKpAKpAKpAKpAKpAKpAKpA3K2pAIpAI2pALpAKpAKLJpAJKpA
      2KpAJILpAL17KLJ3IpA2IpA4IpA6I2J$2J2pA2J2KpAKpA2K13IJpAIpAIpAIpAIpAIpA
      IpAIpAIpAIpAIpA5IpAIKLpA2LpAQTLJ5pAJK2JpA2KL16KLJpALKpA3K4pAJ2KpA4IJ$
      2JpAJ6K3pAJ15KpAKpAKpAKpAKpAKpAKpAKpAKpAKpA5KpA3KLKL2pA.8pA2J2K2pALpA
      L2K11pAJIpAIpAIpA9IpAIJ$2J27KpAKpAKpAKpAKpAKpAKpAKpAKpAKpA5KpA3KpAKpA
      4KJTS4pAJ6KILI12pAJ3pAI3pAIpAIpAIpAIpAJIpA$J28KpAKpAKpAKpAKpAKpAKpAKpA
      KpAKpA5KpA4KM5IpAIpA11I2pAJQRQRQRQRQRQR5pA2IJ7pA2IJ!

      • Lucas de la Paz says:

        Thank you, I also have a question. What are the extra state 25 cells for, and could you reduce the length of the tape by eliminating the extra cells?

        • apgoucher says:

          The extra cells are there because the tape encoding supports run-length compression, so adding these cells reduces the length of the tape. (It’s not just the state-25 confluent cells, if I recall correctly; there are some OTS (states 9..12) cells that are added for this same purpose.)

  5. Lucas de la Paz says:

    I realized that the replicator is very similar to the codon replicators William Buckley made.

    • apgoucher says:

      Yes, that’s correct: WRB and I worked on phi9 collaboratively, and the overall architecture is inspired by his earlier codon4 and codon5 machines. Phi9 illustrates that increasing the complexity of the decoding circuitry allows an overall decrease in tape length (i.e. the increased compression ratio outweighs the larger pattern being encoded).

  6. Lucas de la Paz says:

    Thats good to know. On the Von Neumann universal constructor wiki, it says that the tape code length is 3+ bits. How Exactly does that work? Also, what are the extra cells for?

    • apgoucher says:

      Lucas,

      The instructions are variable-length and prefix-free, where common instructions are shorter than more esoteric instructions (reminiscent of Huffman coding). I’ve lost the original e-mail discussion that contained the table of instruction opcodes, but looking at the tape I’ve been able to completely reconstruct it.

      In particular, instructions are represented by either 1, 2, 4, or 10 ternary digits as below (where ternary digits {0,1,2} are represented on the tape by cells of states {0,12,25}, respectively):

      00 == ‘construct upward OTS cell (state 10) and move left’;
      01 == ‘construct leftward OTS cell (state 11) and move left’;
      02 == ‘construct rightward OTS cell (state 9) and move left’;
      1 == ‘construct confluent cell (state 25) and move left’;
      20 == ‘construct downward OTS cell (state 12) and move left’;
      2100 == ‘construct downward STS cell (state 20) and move left’;
      2101 == ‘construct upward STS cell (state 18) and move left’;
      2102 == ‘construct leftward STS cell (state 19) and move left’;
      2110 == ‘construct rightward STS cell (state 17) and move left’;
      2111 == ‘move left’;
      2112 == ‘move down’;
      2120 == ‘move up’;
      2121 == ‘move right’;
      2122 == ‘advance state machine (e.g. switching between tape-copying and construction)’;
      22xxxxxyyy == ‘execute operation in a loop, where xxxxx encodes (number of repeats – 1) in ternary, and yyy encodes the operation’.

      That’s why there are lots of unused state-25 cells in random locations; they only require 1 ternary digit (1) to encode, whereas an empty space would require 4 ternary digits (2111) to encode.

      The 10-digit complex instructions are mostly used for moving the arm by long distances after a ‘carriage return’; for example, if you want to move right by 110 cells, it’s simpler to write 2211001121 (10 digits) than to repeat 110 copies of 2121 (440 digits).

      This is hugely different from the codon5/codon4/codon3 machines, which have constant-length instructions of (respectively) 5, 4, and 3 bits.

      Looking at the Wikipedia page, the entry for phi9 in the table needs to be amended from ‘3+ bits’ to ‘1, 2, 4 or 10 ternary digits’. Good catch!

  7. Lucas de la Paz says:

    Thanks for your support and effort towards my curiosity. I highly appreciate it.

  8. Lucas de la Paz says:

    I didn’t know that the repeat function costs?! To improve the replicator, You could’ve used a re-readable memory cell with a clear memory function so that the repeat has very limited costs. I like the idea of repeating a function for a limited amount and I think it will make future holistic replicators faster.

    • Lucas de la Paz says:

      The re-readable memory cell is already incorporated, sorry for the misconception. The redesign I’m thinking of has the re-readable memory cell in the constructor head, kind of like this prototype:

      x = 24, y = 12, rule = Nobili32
      4.QIK2.P$3.I2pA3KpA$2.IJQ.IL.2IL$.IJQIK.pA3.L$MJI2pA4KpA2K$.IJQ.IL2.2I
      L$MJQIK.pA4.L$.I2pA5KpA2K$MJQ.IL3.IL$.QIK.pA4.pA$M2pA8K$.Q.21I!

      all I need is a reset input for the latches

    • apgoucher says:

      Isn’t that what the 22xxxxxyyy instruction effectively does? It repeats an operation between 1 and 243 times.

      Specifically, look at the following section of the replicator (located at the base of the replicator, about 1/4 of the way from the left):

      x = 25, y = 18, rule = Nobili32
      13I.2IpAIpAIJ2L2pA$15RpAL4pALIpAI$IpAIpAIpAIpAIpAI3pAKpAK5pAIpAI$KpAK
      pAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAK$9T2pAT3pAT3pAT3pATpA$pA.pA.pA.pA.2I
      pA.2IpA.2IpA.2IpA.pA$pAL3pAL2pAL3pAL3pAL3pAL3pAL$LIL3KpALILpALILpALIL
      pALILpALI$2KLpAIL2pAI3pAI3pAI3pAI3pAI$LJLpAJLpATpAKpATpAKpATpAKpATpAK
      pATpA$2pAKIJLpA2TJpA2TJpA2TJpA2TJpA2T$IpAIpAIpAI2.pAI2.pAI2.pAI2.pAI$
      pAKpAILpAJpAJpAJpAJpAJpAJpAJpAJpAJpAJ$J3KI2pAKpAKpAKpAKpAKpAKpAKpAKpA
      KpA$3IJpAIpAIpAIpAIpAIpAIpAIpAIpAIpAIpA$6KpAKpAKpAKpAKpAKpAKpAKpAKpAK
      pA$6KpAKpAKpAKpAKpAKpAKpAKpAKpAKpA$6KpAKpAKpAKpAKpAKpAKpAKpAKpAKpA!

      There are three active components here (involving STS cells), namely a unary counter (top), a ternary shift register (middle), and a ternary counter (bottom). When a ternary digit is read from the tape, it is shifted into the shift register and the unary counter (defaults to 2) is decremented. When this unary counter hits 0, the instruction exits through the bottom of the shift register and the circuitry resets (setting the unary counter to 2, ready for the next 2-digit codon).

      As such, the circuitry ‘expects’ 2-digit codons, but there are some quirks in the hardware to deal with other cases:

      1. if the codon is of the form 1x, then it sends a ‘construct confluent cell and retract’ instruction to the construction arm, pushes the digit x back into the shift register (so the ‘x’ forms the first digit of the next codon) and sets the unary counter to 1. This is why a ‘1’ behaves like a one-digit instruction.
      2. if the codon is 21, then it pushes 1 onto the shift register and sets the unary counter to 2. This way, it will receive an extra two symbols (xx) from the tape and send a 3-digit instruction 1xx to the construction arm.

      3. if the codon is 22, then it sets the unary counter to 8. This means that eight ternary digits will be read from the tape into the shift register. When they exit through the bottom of the shift register, the first 5 digits (which are on the right hand side) pass down to set the ternary counter; the other 3 digits (which are on the left hand side) form the instruction. This instruction travels around in a loop, sending a copy of itself to the construction arm repeatedly, until the ternary counter counts down to 0.

      It becomes more efficient to use the special ‘repeat’ instruction 22xxxxxyyy if you want to:

      (a) construct a sequence of at least 11 confluent cells;
      (b) construct a sequence of at least 6 identical OTS cells;
      (c) construct a sequence of at least 3 identical STS cells;
      (d) move the construction arm at least 3 units in a particular direction.

      If you want to repeat fewer times than that, you may as well just use the ‘unrolled’ form: for instance, to construct a row of 8 confluent cells you can just write 11111111.

      Hopefully this is clear?

  9. Lucas de la Paz says:

    Completely clear now. I’m just thinking of a complete redesign to the ternary replicator.

  10. William R. Bucklcy says:

    Gentlemen, this discussion is excellent.

  11. Andrew Bayly says:

    I have done some work on creating a self-replicator. One of my main goals is to reduce both the size of the machine and its complexity. So far I have achieved 8×27 as the size of the replicator. More information here:

    https://andrewbayly.github.io/2023/10/14/a-tiny-universal-constructor.html

    Comments welcome!

Leave a Reply