Turing Completeness in the Language of Genetic Programming with Indexed Memory

Created by W.Langdon from gp-bibliography.bib Revision:1.3872

  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
                 ( or J.GP.CS.CMU.EDU

                 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.",

Genetic Programming entries for Astro Teller