Turing-complete data structure for genetic programming
Taro Yabuki, Hitoshi Iba · 2004
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.