Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms

Issue title: Machines, Computations and Universality, Part I

Article type: Research Article

Authors: Burgin, Mark | Eberbach, Eugene

Affiliations: Dept. of Mathematics, University of California, Los Angeles, CA 90095, USA. [email protected] | Dept. of Engineering and Science, Rensselaer Polytechnic Institute, Hartford, CT 06120, USA. [email protected]

Note: [] Address for correspondence: Dept. of Mathematics, University of California, 405 Hilgard Avenue, Los Angeles, CA 90095, USA

Abstract: The aim of this paper is the development of foundations for evolutionary computations. To achieve this goal, a mathematical model of evolutionary automata is introduced and studied. The main classes of evolutionary automata considered in this paper are evolutionary Turing machines and evolutionary inductive Turing machines. Various subclasses and modes of evolutionary computation are defined. Problems of existence of universal objects in these classes are explored. Relations between Turing machines, inductive Turing machines, evolutionary Turing machines, and evolutionary inductive Turing machines are investigated.

Keywords: evolutionary algorithms, universality, modeling, Turing machine, evolutionary Turing machine, inductive computation, super-recursive algorithms

DOI: 10.3233/FI-2009-0033

Journal: Fundamenta Informaticae, vol. 91, no. 1, pp. 53-77, 2009