Turing-complete Data Structure for Genetic Programming

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

@InProceedings{yabuki03smc,
  author =       "Taro Yabuki and Hitoshi Iba",
  title =        "Turing-complete Data Structure for Genetic
                 Programming",
  booktitle =    "IEEE International Conference on Systems, Man and
                 Cybernetics",
  year =         "2003",
  volume =       "4",
  pages =        "3577--3582",
  address =      "Washington, D.C., USA",
  month =        "5-8 " # oct,
  publisher =    "IEEE Press",
  keywords =     "genetic algorithms, genetic programming, language
                 classifier, Turing-completeness",
  ISSN =         "1062-922X",
  URL =          "http://www.iba.k.u-tokyo.ac.jp/~yabuki/paper/2003-yabuki-smc.pdf",
  size =         "6 pages",
  abstract =     "In generating a program automatically, if we do not
                 know whether the problem is solvable or not in advance,
                 then the representation of the program must be
                 Turing-complete, i.e. the representation must be able
                 to express any algorithms. However, a tree structure
                 used by the standard genetic programming is not
                 Turing-complete. We propose a representation scheme,
                 which is a recurrent network consisting of trees. It
                 makes genetic programming turing-complete without
                 introducing any new non-terminals. In addition, we
                 empirically show how it succeeds in evolving language
                 classifiers.",
  notes =        "

                 Turing completeness comes from infinite length
                 integers. Lisp like: car, cdr, cons. Claims better
                 performance on Tomita languages than
                 \cite{Iba:1995:tdpGP}.",
}

Genetic Programming entries for Taro Yabuki Hitoshi Iba