Evolution as a computational engine

DOI10.1007/BFB0028006MaRDI QIDQ4218921zbMATH OpenFDO

Authors Rolf Backofen, Peter Clote

Publication date 21 June 1999

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BFB0028006

zbMATH Keywords

lethal genesrestricted evolutionary systemreversible Turing machineThue systemundecidabilityuniversal computation engine

Mathematics Subject Classification ID

Thue and Post systems, etc. (03D03) Turing machines and related notions (03D10) Undecidability and degrees of sets of sentences (03D35) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Problems related to evolution (92D15)

Review text

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

Recommendations

• Computational Evolution
• scientific article; zbMATH DE number 741098
• Evolutionary computing
• Evolutionary computer simulations
• Evolutionary computation
• scientific article; zbMATH DE number 1100791
• scientific article; zbMATH DE number 1374049
• scientific article; zbMATH DE number 1100792
• scientific article; zbMATH DE number 1222692

Cited in

(14)

• Evolution as computation. DIMACS workshop, Princeton, NJ, USA, January 1999
• Evolutionary computer simulations
• Evolution and Biocomputation: computational models of evolution
• Complexity theory and genetics: The computational power of crossing over
• A mathematical model for evolutionary systems
• Evolutionary design by computers
• Mutation systems
• Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms
• DNA-like genomes for evolution in silico
• scientific article; zbMATH DE number 6949725 (Why is no real title available?)
• Programming in biomolecular computation
• Foundations of Genetic Algorithms
• Observation of Unbounded Novelty in Evolutionary Algorithms is Unknowable
• Thinking about evolution in terms of cellular computing

This page was built for publication: Evolution as a computational engine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4218921)