- author = "Astro Teller",
- title = "Turing Completeness in the Language of Genetic Programming with Indexed Memory",
- booktitle = "Proceedings of the 1994 IEEE World Congress on Computational Intelligence",
- year = "1994",
- volume = "1",
- pages = "136--141",
- address = "Orlando, Florida, USA",
- month = "27-29 " # jun,
- publisher = "IEEE Press",
- keywords = "genetic algorithms, genetic programming",
-
URL = "
http://www.cs.cmu.edu/afs/cs/usr/astro/public/papers/Turing.ps",
-
DOI = "
doi:10.1109/ICEC.1994.350027",
- size = "6 pages",
- abstract = "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 express 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 will prove 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.",
-
notes = "Proof that Language of GP+Indexed Memory is Turing
Complete, Nb does NOT show GP+IM itself will solve
anything. You can get these papers by anonymous ftp to
any CMU machine. (e.g. GS61.SP.CS.CMU.EDU
(128.2.203.143) or J.GP.CS.CMU.EDU
(128.2.250.198))
then cd to /afs/cs/usr/astro/public/papers/
Since several come from the Mac, they won't work in GhostView, but they should print fine.",
