In the popular science book Gödel, Escher, Bach, D. Hofstadter designed
a formal system called ``typogenetics'' (from typographical genetics), which simulates certain cellular processes.
The formalism was designed to give some intuition for the nature of the cellular processes involving DNA.
The system defines a mechanism for translating DNA strands into ``typographical enzymes'' analogous to the ribosome's function in actual cells.
The DNA strand can therefore be viewed as a ``source code'', and the enzyme it's translated into as the equivalent ``machine code''. An enzyme gets another DNA strand as its input and may then copy, cut, or otherwise modify it.
After the system's definition, Hofstadter poses a puzzle to the reader: find a typogenetical self-replicator (a strand that replicates itself).
This would involve an enzyme receiving its own ``source code'' as input and producing at least two copies of this very code after a finite number of iterations of this ``program self-cannibalism''.
In this thesis, we give a more rigorous definition of typogenetics and self-replicators than the one given in Gödel, Escher, Bach. In addition, we design and implement an algorithm for searching the space of DNA strands for self-replicators and present its results.
|
