Dana Angluin, James Aspnes, and Raonne Barbosa Vargas. Mutation systems. International Journal of Computer Mathematics 90(6):1132–1149, June 2013. (LATA 2011 special issue). An earlie version appeared in Language and Automata Theory and Applications: 5th International Conference, LATA 2011, Tarragona, Spain, May 26–31, 2011, Lecture Notes in Computer Science 6638, Springer-Verlag, May 2011, pp. 92–104.
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 k ≥ 2, such systems can simulate computation by both finite state machines and 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 analyze the efficiency of the finite state machine simulation assuming random point mutations.
@article{AngluinABV2013,
author = {Dana Angluin and James Aspnes and Barbosa Vargas, Raonne},
title = {Mutation systems},
month = jun,
year = 2013,
journal = {International Journal of Computer Mathematics},
volume = 90,
number = 6,
pages = {1132--1149}
}