Evolution as a computational engine (Q4218921)

The following problem is shown to be undecidable: given a set \(K\) of lethal genes, a starting genome \(x\) and a desired target 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. It is further shown that a restricted evolutionary system forms 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 configurations in \(M\)'s computations. For the entire collection see [Zbl 0891.00021].