- 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",
- address = "London",
- 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
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 http://www.dcs.bbk.ac.uk/ukci05/",
