Turing completeness in the language of genetic programming with indexed memory
Astro Teller · 2002
Genetic programming is a method for evolving functions that find approximate or exact solutions to problems. There are many problems that traditional genetic programming (GP) cannot solve, due to the theoretical limitations of its paradigm. A Turing machine (TM) is a theoretical abstraction that expresses the extent of the computational power of algorithms. Any system that is Turing complete is sufficiently powerful to recognize all possible algorithms. GP is not Turing complete. This paper proves that when GP is combined with the technique of indexed memory, the resulting system is Turing complete. This means that, in theory, GP with indexed memory can be used to evolve any algorithm.>