# Invariance of Function Complexity under Primitive Recursive Functions

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

@InProceedings{woodward:2005:UKCIb,
author =       "John R. Woodward",
title =        "Invariance of Function Complexity under Primitive
Recursive Functions",
booktitle =    "The 5th annual UK Workshop on Computational
Intelligence",
year =         "2005",
editor =       "Boris Mirkin and George Magoulas",
pages =        "281--288",
month =        "5-7 " # sep,
email =        "jrw@cs.bham.ac.uk",
keywords =     "genetic algorithms, genetic programming, ADF",
URL =          "http://www.dcs.bbk.ac.uk/ukci05/ukci05proceedings.pdf",
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
\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 http://www.dcs.bbk.ac.uk/ukci05/",
}

Genetic Programming entries for John R Woodward

Citations