Invariance of Function Complexity under Primitive Recursive Functions

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

  author =       "John R. Woodward",
  title =        "Invariance of Function Complexity under Primitive
                 Recursive Functions",
  booktitle =    "The 5th annual UK Workshop on Computational
  year =         "2005",
  editor =       "Boris Mirkin and George Magoulas",
  pages =        "281--288",
  address =      "London",
  month =        "5-7 " # sep,
  email =        "",
  keywords =     "genetic algorithms, genetic programming, ADF",
  URL =          "",
  size =         "8 pages",
  abstract =     "Genetic Programming (GP) \cite{banzhaf:1997:book}
                 often uses a tree form of a graph to represent
                 solutions in a search space. An extension to this
                 representation, Automatically Defined Functions (ADFs)
                 \cite{banzhaf:1997:book} is to allow the ability to
                 express modules. In \cite{woodward:Modularity} we
                 proved that the complexity of a function is independent
                 of the primitive set (function set and terminal set) if
                 the representation has the ability to express modules.
                 This is essentially due to the fact that if a
                 representation can express modules, then it can
                 effectively define its own primitives at a constant
                 cost. This is analogous to the to the result that the
                 complexity of a bit string is independent of the
                 Universal Turing Machine (UTM) (within an additive
                 constant) \cite{ming93introduction}. The constant
                 depending on the UTM but not on the function.

                 The representations typically used in GP are not
                 capable of expressing recursion, however a few
                 researchers have introduced recursion into the
                 representation. These representations are then capable
                 of expressing the primitive recursive functions (PRFs)
                 which are a subclass of the partial recursive function
                 (which correspond to the computable functions). We
                 prove that given two representations which express the
                 PRFs, the complexity of a function with respect to
                 either of these representations is invariant within an
                 additive constant. This is in the same vein as the
                 proof of the invariants of Kolmogorov complexity
                 \cite{ming93introduction} and the proof in
                 \cite{woodward:Modularity}. We comment on the important
                 of the class of PRFs for learning.",
  notes =        "UKCI 2005",

Genetic Programming entries for John R Woodward