Universality for Turing Machines, Inductive Turing Machines and Evolutionary Algorithms

• Autorzy: Burgin M. , Eberbach E.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

evolutionary algorithms; universality; modeling; Turing machine; evolutionary Turing machine; inductive computation; super-recursive algorithms

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 91, nr 1
• Strony: 53--77
• Opis fizyczny: bibliogr. 20 poz., tab.

Twórcy

autor

Burgin M.

autor

Eberbach E.

• Dept. of Mathematics, University of California, 405 Hilgard Avenue, Los Angeles, CA 90095, USA,

Bibliografia

• [1] Aho, A.V., Hopcroft, J.E., and Ulman, J.D., The Design and Analysis of Computer Algorithms, Reading, Mass., Addison-Wesley P.C., 1976.
• [2] Blum, L., Cucker, F., Shub, M., and Smale, S., Complexity of Real Computation, Springer, New York, 1998.
• [3] Burgin,M., Multiple computations and Kolmogorov complexity for such processes, Notices of the Academy of Sciences of the USSR, 1983, v. 27, No. 2 (v. 269, No.4), 793-797 (translated from Russian).
• [4] Burgin,M., Universal limit Turing machines, Notices of the Russian Academy of Sciences, 1992, v.325, No. 4, 654-658 (translated from Russian).
• [5] Burgin, M., Reflexive Calculi and Logic of Expert Systems, in Creative processes modeling by means of knowledge bases, Sofia, 1992, 139-160.
• [6] Burgin,M., Reflexive TuringMachines and Calculi, Vychislitelnyye Sistemy (Logical Methods in Computer Science), 1993, No. 148, pp. 94-116, 175-176 (in Russian).
• [7] Burgin M., Nonlinear Phenomena in Spaces of Algorithms, International Journal of Computer Mathematics, 2003, v. 80, No. 12, 1449-1476.
• [8] Burgin,M., Superrecursive Algorithms, Springer, New York, 2005.
• [9] Burgin, M., Measuring Power of Algorithms, Programs, and Automata, in "Artificial Intelligence and Computer Science", Nova Science Publishers, New York, 2005, 1-61.
• [10] Burgin, M., Eberbach, E., Cooperative Combinatorial Optimization: Evolutionary Computation Case Study, BioSystems, 2008, v. 91, no. 1, 34-50.
• [11] Burks, A.W., Wright, J.B., Theory of Logical Nets, Proceedings IRE, 1953, v.41, no.10, 1357-1365.
• [12] Deutsch, D., Quantum theory, the Church-Turing principle, and the universal quantum Turing machine, Proc. Roy. Soc., Ser. A, 1985, v. 400, 97-117.
• [13] Eberbach, E., Toward a theory of evolutionary computation, BioSystems, 2005, v.82, no.1, 1-19.
• [14] Fogel, D.B., Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, IEEE Press, 1995.
• [15] Fogel D.B., An Introduction to Evolutionary Computation, Tutorial, 2001 Congress on Evolutionary Computation CEC'2001, Seoul, Korea, 2001.
• [16] Hopcroft J.E., Motwani R., Ullman J.D., Introduction to Automata Theory, Languages, and Computation, 2nd edition, Addison-Wesley, 2001.
• [17] Koza J., "Genetic Programming: On the Programming of Computers by Means of Natural Selection", "Genetic Programming II: Automatic Discovery of Reusable Programs", "Genetic Programming III: Darvinian Invention and Problem Solving", The MIT Press, 1992, 1994, and 1999.
• [18] Michalewicz Z., Genetic Algorithms + Data Structures = Evolution Programs, third edition, Springer-Verlag, 1996.
• [19] Michalewicz Z., Fogel D.B., How to Solve It: Modern Heuristics, 2nd ed., Springer-Verlag, 2004.
• [20] Vardi, M.Y., Wolper, P., Reasoning about Infinite Computations, Information and Computation, 1994, v.115, No.1, 1-37.