@InProceedings{Bac:Clo:CSL97,
  author =       "Rolf Backofen and Peter Clote",
  title =        "Evolution as a Computational Engine",
  year =         1997,
  booktitle =    "Proc. of Annual Conference of the European Association for
                  Computer Science Logic (CSL'97)",
  editor =       "Mogens Nielsen and Wolfgang Thomas",
  volume =       1414,
  series =       "Lecture Notes in Computer Science",
  pages =        "35--55",
  address =      "Berlin",
  publisher =    "Springer--Verlag"
, abstract = {Given a finite set $K$ of
<i> lethal genes</i>, a starting genome $x$ and a desired <I> target </I>
genome $y$, is there a sequence of base insertions, deletions, and
substitutions, which from $x$ produces the desired genome $y$,
and such that no intermediate genome contains
a lethal gene. The main result of this paper is that, appropriately
formulated, this problem is undecidable, even when the underlying
alphabet has only 2 symbols (e.g. two of the bases A,C,G,T).
We prove that asexual evolutionary systems form a universal
computation engine, in the sense that for any
reversible
Turing machine $M$ and input $x$, there is a finite set $K$ of lethal genes,
which can guide the computation, so that all intermediate genomes
are prefixes of (encodings of) configurations in the computation of $M$.
Since reversible Turing machines retain the history of
their entire computation, and are essentially encoded by evolutionary systems,
this
suggests a encoding
mechanism by which
<I> phylogeny recapitulates ontogeny. </I>
   }
}