Mutation systems

Abstract

We propose mutation systems as a model of the evolution of a string subject to the effects of mutations and a fitness function. One fundamental question about such a system is whether knowing the rules for mutations and fitness, we can predict whether it is possible for one string to evolve into another. To explore this issue, we define a specific kind of mutation system with point mutations and a fitness function based on conserved strongly k-testable string patterns. We show that for any k greater than 1, such systems can simulate computation by both finite state machines (FSMs) and asynchronous cellular automata. The cellular automaton simulation shows that in this framework, universal computation is possible and the question of whether one string can evolve into another is undecidable. We also analyse the efficiency of the FSM simulation assuming random point mutations.

Keywords:

• mutation systems
• finite automata
• cellular automata
• k-testable languages
• point mutations
• reversible computation

Keywords:

• 03D80
• 68Q45
• 68Q80

Acknowledgements

This material is based upon work supported by the National Science Foundation under Grant Number CCF-0916389. A preliminary version of this paper appears in the proceedings of LATA 2011 2. Raonne Barbosa Vargas is now employed by Microsoft Corporation. The authors thank David Eisenstat and Sarah Eisenstat for help with aspects of this paper.