Mutation systems
Dana Angluin, James Aspnes, Raonne Barbosa Vargas · International Journal of Computer Mathematics · 2012
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.