- 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",
-
DOI = "
10.1109/ICSMC.2003.1244444",
- 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}.
Also known as \cite{1244444}",
