Inproceedings,
Invariance of Function Complexity under Primitive Recursive Functions
The 5th annual UK Workshop on Computational Intelligence, page 281--288. London, (5-7 September 2005)
Abstract
Genetic Programming (GP) 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)
banzhaf:1997:book is to allow the ability to
express modules. In 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) 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
ming93introduction and the proof in
woodward:Modularity. We comment on the important
of the class of PRFs for learning.
