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?

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

3 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s