Modeling Evolution by Evolutionary Machines: A New Perspective on Computational Theory and Practice

Abstract

The main goal of this paper is the further development of the foundations of evolutionary computations, connecting
classical ideas in the theory of algorithms and the contemporary state of art in evolutionary computations.
To achieve this goal, we develop a general approach to evolutionary processes in the computational context, building
mathematical models of computational systems, called evolutionary machines or automata. We introduce two
classes of evolutionary automata: basic evolutionary automata and general evolutionary automata. Relations between
computing power of these classes are explored. Additionally, several other classes of evolutionary machines are investigated,
such as bounded, periodic and recursively generated evolutionary machines. Dierent properties of these
evolutionary machines are obtained.