-
Recent Posts
Subscribe to Complex Projective 4-Space
Join 2,090 other subscribersArchives
- March 2025
- July 2024
- January 2024
- July 2023
- March 2023
- February 2023
- January 2023
- October 2022
- September 2022
- July 2022
- June 2022
- May 2022
- January 2022
- December 2021
- September 2021
- July 2021
- June 2021
- May 2021
- February 2021
- January 2021
- December 2020
- November 2020
- October 2020
- September 2020
- August 2020
- July 2020
- June 2020
- May 2020
- June 2019
- May 2019
- March 2019
- November 2018
- September 2018
- July 2018
- June 2018
- May 2018
- April 2018
- March 2018
- February 2018
- November 2017
- October 2017
- November 2016
- May 2016
- March 2016
- February 2016
- December 2015
- September 2015
- March 2015
- February 2015
- January 2015
- December 2014
- November 2014
- October 2014
- September 2014
- August 2014
- July 2014
- June 2014
- May 2014
- April 2014
- March 2014
- February 2014
- January 2014
- December 2013
- November 2013
- October 2013
- September 2013
- August 2013
- July 2013
- June 2013
- May 2013
- April 2013
- March 2013
- February 2013
- January 2013
- December 2012
- November 2012
- October 2012
- September 2012
- August 2012
Recent Comments
- Andrew Bayly on Fully self-directed replication
- martin on Cipher 69: A void
- 如何证明SSCG(3)>TREE(3) — part 1 – 大老李聊数学 on Graph minors
- NooneAtAll on Graph minors
- NooneAtAll on Graph minors
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?
Like this:
Like Loading...
This entry was posted in Uncategorized. Bookmark the permalink.
21 Responses to Self-replication
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!
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.
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.
Pingback: a self-replicating pattern in a cellular automaton, designed by John von Neumann - NSO News
Pingback: Von Neumann universal constructor - Wikipedia
Can you post the phi9.rle, I’m not going to copy it from the picture by hand.
Certainly:
x = 9040, y = 60, rule = Nobili32
47.IpAL43ドル.3IpAJLIL42ドル.I.2IpAIpALIpA3IL40ドル.2IJR2pAL2K2IpA2I2L40ドル.J2IpA
2IpA4IpAI3L36ドル.4I2JpAJpAL6I3LIL36ドル.J4I.IpAI.L5pA2LI2L36ドル.2J3pARpAJpAR
LpA3I3pA3L36ドル.2JpA2I3pAI2pAIpAIpALI4pA36ドル.2JpAJ3pAJ3pAIpAIpAI5L36ドル.2J
pAJpA2IpA3IpA2IpAJ5L34ドル.2I9J2IpAL3pA4L2IL33ドル.I.2I.IpAI.IpAI.IpAIpAI5pA
I2L33ドル.JR2pARpAJpARpAJpARpA5I2LI2pALIL31ドル.2I3pAI3pAI3pAI7pALILILILIL$
31.JIpA2J3pAJ3pAJ3pAIL3pA2IpAIpAIpAIpA10IpA13IpAIpA3IL21IL31ドル.3pAIpA
3IpA3IpAIpAIpAIpAIpAJpALpALpALpA5ILpAJpA2IpA13IpAIpA2IL9IJ2IL2IL2ILpA
I2pA31ドル.13JIpAIpAIpAI3pALpALpA6IL2IpAIpAIpA13IpALpAIL11I3pAJ2pAJ2pAI
2pAL31ドル.6J2IpA3IpAJ7IJ3pA7I2LJpAJpAJpALpAILIL2pAIL2ILI2pAI2pAIL2IL2IL
ILpAIpA2IpA2IpA4IL31ドル.15J8pAT8pALIpAIpAIpAIpAI5pAIJI3pAJIpAI3pAI3pAJ
2pAJIpAI12pA30ドル.I10J2IpAIJ3pA3IpA2IL7pAILJpAJpAJpALpALIJIJ3pAIpA10IpA
2IpA13IpA3IpAIpAIpA3I29ドル.IJI10JpAJ2pAJ2KJ2IpATSIpA6ILIpAIpAIpA2LpAL5pA
2IL7pA2ILI2pAL2pALILIpAI3pALIL2pALI5pA2QR27ドル.2I.IpAI.IpAI.IpAI.IpAI.pA
I3JIpAIpAIpA3IL2IpATJpAJKJIpAIpAIpAIpAI3pAIpAIpAIpAI3pAJIJ2IJIJIJ2pAI
pAJIJ2IJIpAL5pA12ドル.4IL10I2pARpAJpARpAJpARpAJpARpAJpAR3pA3JLTSpA2ILpAI
pA2LI3pA2JKI2L6IpA9IpA11IpA2IpA12IpAJ9ドル.3IJRQ.12pAI3pAI3pAI3pAI3pAI8pA
.pAIpAIpALpAJLILJ2pAJpAJ3pA6IpA4IpAIpAI3pAIpALIpAIpALI2pAI3pAIpAIpAIpA
I2pAI2pAJ9ドル.J3I2pAKL9I2J3pAJ3pAJ3pAJ3pAJ5pA3JLTSpALpALIpAJILIpA2IpAIpA
LI2pA5IpA4IpAIpAL2IJ2pAI4pAIJ2pAJ2IJ2pAIpAJ2pAIJ2pAJ9ドル.2JRpAI2pAL4pAI
JILpAIJ2pAIJ2pAIJ2pAIJ2pAIJ9pA.pAIpAIpA2IpAIpALJK2JK2pALIpAJ2ILIpA2IL
IpALpA7IpA6IJ5IJIpA7IJ9ドル.3pA2KLJL4pAJI2pALJpAJpAJpAJpAJpAJpAJpAJpAJpA
J2pAIL3JLTSpALpALpAIJpA2LpA2J2KJ2pAIpAI2pALJpAK5pAILILIL2IpA7IJ5IJ7ドル.
IL3JpAJLJL4pA2J4pAI3pAI3pAI3pAI3pAI9pA.pAIpAIpAIpAIpAIpALJpAI2pAJ5I2pA
IpAJpAIJLKpAIJIJIJIpA8IJ6ドル.I2pA2J2pAJLJILpA2I2pAJpALJpAJpAJpAJpAJpAJpA
JpAJpAJpAJ2pAJL3JLTSpALpAILKpALpA2LJQRJpAJ22IJ6ドル.J2pAILJpAJLJK2IpAIpA
I2pAIpAIpAIpAIpAIpAIpAIpAIpAIpAI9pA.pAIpALIpA2ILpA2LJpAK2pAJ6ドル.pA2JIpA
JI2pALJ2pAJKLpAL2pAJ3pAJ3pAJ3pAJ3pAJIpALpAJL3JLTSpALIpAILpALpA2LpAJpA
JI12pA3IpA6IpAIpAIpAL4pA2IpAIpAL6ドル.3pA2JpAJ2pAKJ5pAK2pAIpAIpAIpAIpAIpA
IpAIpAIpAI3pAK7pA.pAIpAL2IpAIpAI2L2pAIpARJ2pAQIpAIpAIpAIpAJ2IpAL2IL6I
2pA2ILIpAIpALpAIpAL6pAIL6ドル.I2JpAJKIJLpAJ3pAJ2IpAJKpAKpAKpAKpAKpAKpAKpA
KpAKpAJLILJL3JLTSpALpAJpALpALpALILJpAJIJpAJ2pAJpALIpAIpALJKLIJpAIpAIpA
IpALI2pALpA2J2pAIpAI2pA2IpAIpAIpAL6ドル.JI2pAI3pALpAJ3pAJ2K3IpAIpAIpAIpA
IpAIpAIpAIpAIJ10pA.pAIpAI.IpAL2IpAIpAJI2J2pAJpAIJIpAJ3IpAIpA3IpA6IpA
3IpA2IpA2IL11IpAIpAT6ドル.4JKpAJ3pAJ6pA4K17pALJLJL3JLTSpALpARS2L2pALpALpA
JpAIJpAJpAJIJL2pAL2KpAJ2K2pALpA5KILpAL2pAJ2KIJ8pAJpAKLKT6ドル.2JpAKpAIpA
JL2pAKpAKpAKpA3K11pAL5KL9pA.pAIpA2IpALpA2IpA3IpAIpAILpAK2JKLpAIpA5IpA
9I2pAIpA4IpA9IpAIpAIpAIL6ドル.J2KpAJ4pAIpAIpAIpAIpAILJ11pAL3ILJIpAJIJI3J
IKLpALpALKL3pAL3pAJpAJ2pA3JIJ2ILI3pAIpA2JKL2KpA3K2pAKIpALIpAJIpAIpAI
2pAK2pALKpA2LK5ドル.4IpAJ3pAL9pALJK9pALKJI2LJKpA5KJpA3KLpAKpAKpA3KpAKpAK
pAKpAKTI3JK2pAILIpAJpA2IpAJL2pAJ2KpAJKJ2pAIJ2I5pAIpAJLKpA2KpAK5ドル.J3IpA
2IpAIpA2IL3pAIpAIpALJ10K5pA2I5pAJKJ4KLpALpALpAJpAL3pAJpA2JIpAKpAKpA3K
pAKpA4KpA2K3pAK4pAJ4KLK3pALpAKpA2KpAL2pAQT5ドル.2J2IpA2IpAIL2pAL2pAI2pA
2L13I2JL2pARIL4pAJ6K11pAJpA2J2KpAJpAJ3KIL12pAJpAL2ILILJpAKJpALKL5pA4I
L4ドル.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.2L2pA4ドル.
2JI3pA2IpAILpAL3IpAIpA13I.2IpAIpAIJ2L13pAIpAIpAIJ3pAJpAJ3pAIJL4KJIL
13pAIJpAIJ2IpAIpAIpAIpAIJLKpA5K4ドル.4pA2J2IJIpAIpA3IpAJpA15RpAL4pALIpAI
pAIpAL5pAIpA2LpAJLpAKpAKpAK2pA2JpALKL3KpAKpA6KpA13KpAKpAKpAKpA3K6IJ$
4.4J3pAIpAJLpA4IpAIpAIpAIpAIpAIpAIpAI3pAKpAK5pAIpAIpAI6pAJIJ2LpAJLJ3pA
JpAJpAJpAKpAIpAL2pAJpAILpA2ILI3pAIL8pAIpAL8pAJ5QR$.3I4JI2J3pA3ILpALpA
KpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAKL3IL2pAJpA2L5pA2IpAIpA2IJ
3pALILpAJpALKIpALpAJIpAI2pAIpAL2pAIpAI2pAK10pA$IpA3IpA3JKpAKpA3KpALpA
LJ2K9T2pAT3pAT3pAT3pAT2pAJ3I2LpAJ2pA2LpAJLJ3pAJpAJ3KLpAK2pAL2pAKILJ
11IpA2IpA13I2J2ドルJIKpAJpAJ2pAJLpA2KJpA2IpA3IpA.pA.pA.pA.2IpA.2IpA.2IpA
.2IpA.2pAJ3K2LI2pAK7pAJpAJL2pAKpAKJpALpALIpAJLKJ6KL6KpAJ9KIL2pA2J3ドルpA
IpAJpAJ2I3pAI2J3pAL4pAL3pAL2pAL3pAL3pAL3pAL3pAL3pALpAKL2JI2LILJLJ3pAJ
LJLpAL2pAK2pALJpAKL6IpAIpA6IpA9IpAJ3IpAJ3ドルJRpA2I2JRpAKJ2KJ2KpAIpA2ILI
L3KpALILpALILpALILpALILpALILpALpAJpALJ3pAKIpAJLJpAJpAJLpAKpAL3pALpALI
pAJIpAIpAI2pA2JIpAI2pAI2pAIpAIpAIpAIpALJpAJ2pA2J4ドルpAJ3pAJpAJ2pAKpA2KJ
KpAL4KLpAIL2pAI3pAI3pAI3pAI3pAI2pA2L2pALpAJpALIJL6pAJLJ2pALpALK2pALJpA
2K4pAIJIJKpAKIJpA2IJ6IJIpAIpAJpA2J4ドルJL2KpAJK5pALpAKpAKpA2ILJLpAJLpATpA
KpATpAKpATpAKpATpAKpATpAKpAI3pALpAJ2pAJLKpALJpAJ6pALpALpALpA2IpAIpAIpA
IpAILJLpAKJ15K4pA2J4ドルJpAK4pAJLpAKpAKLIJ6pAKIJLpA2TJpA2TJpA2TJpA2TJpA
2TJpALK2pAILJpATpAL.pAKJ3pAJLJ2IL2pAKpA3IpALJKpAKpAKLJKL3pAIL16pA2J$
8J3pAKLpAJKpAJ5pAIpAIpAIpAI2.pAI2.pAI2.pAI2.pAI2.pAIpA2IpALIpA2I2pARL
pAJpAJpAJLJpAKpAKLpAI2LKpAK5pAJpA3K3pAJL2IL2ILIpALpAIpALpAIpA2J3ドルJIJI
pAKpAKJK2pA2KpA6KpAKpAILpAJpAJpAJpAJpAJpAJpAJpAJpAJpAJ2pAL2pATpA2J2pA
LI3LpAKpAKpA2KpAKTJpA3KL9pA5ILI2pAJpAIpALIpALKI3pAIpAL2J3ドルJpAKJ2pA2JK
2pAK9pAJ3KI2pAKpAKpAKpAKpAKpAKpAKpAKpAKpA3K2pAIpAI2pALpAKpAKLJpAJKpA
2KpAJILpAL17KLJ3IpA2IpA4IpA6I2J2ドルJ2pA2J2KpAKpA2K13IJpAIpAIpAIpAIpAIpA
IpAIpAIpAIpAIpA5IpAIKLpA2LpAQTLJ5pAJK2JpA2KL16KLJpALKpA3K4pAJ2KpA4IJ$
2JpAJ6K3pAJ15KpAKpAKpAKpAKpAKpAKpAKpAKpAKpA5KpA3KLKL2pA.8pA2J2K2pALpA
L2K11pAJIpAIpAIpA9IpAIJ2ドルJ27KpAKpAKpAKpAKpAKpAKpAKpAKpAKpA5KpA3KpAKpA
4KJTS4pAJ6KILI12pAJ3pAI3pAIpAIpAIpAIpAJIpA$J28KpAKpAKpAKpAKpAKpAKpAKpA
KpAKpA5KpA4KM5IpAIpA11I2pAJQRQRQRQRQRQR5pA2IJ7pA2IJ!
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?
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.)
I realized that the replicator is very similar to the codon replicators William Buckley made.
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).
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?
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!
The first replicator doesn’t need those extra cells because it wasn’t constructed by another replicator
Thanks for your support and effort towards my curiosity. I highly appreciate it.
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.
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.P3ドル.I2pA3KpA2ドル.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
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.2IpAIpAIJ2L2pA15ドルRpAL4pALIpAI$IpAIpAIpAIpAIpAI3pAKpAK5pAIpAI$KpAK
pAKpAKpAKpAKpAKpAKpAKpAKpAKpAKpAK9ドルT2pAT3pAT3pAT3pATpA$pA.pA.pA.pA.2I
pA.2IpA.2IpA.2IpA.pA$pAL3pAL2pAL3pAL3pAL3pAL3pAL$LIL3KpALILpALILpALIL
pALILpALI2ドルKLpAIL2pAI3pAI3pAI3pAI3pAI$LJLpAJLpATpAKpATpAKpATpAKpATpAK
pATpA2ドルpAKIJLpA2TJpA2TJpA2TJpA2TJpA2T$IpAIpAIpAI2.pAI2.pAI2.pAI2.pAI$
pAKpAILpAJpAJpAJpAJpAJpAJpAJpAJpAJpAJ$J3KI2pAKpAKpAKpAKpAKpAKpAKpAKpA
KpA3ドルIJpAIpAIpAIpAIpAIpAIpAIpAIpAIpAIpA6ドルKpAKpAKpAKpAKpAKpAKpAKpAKpAK
pA6ドルKpAKpAKpAKpAKpAKpAKpAKpAKpAKpA6ドルKpAKpAKpAKpAKpAKpAKpAKpAKpAKpA!
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:
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.
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?
Completely clear now. I’m just thinking of a complete redesign to the ternary replicator.
Gentlemen, this discussion is excellent.
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!