Invariants of Function Complexity under Primitive Recursive Functions

Citation

Woodward J (2005) Invariants of Function Complexity under Primitive Recursive Functions. In: Mirkin B & Magoulas G (eds.) UKCI 2005: Proceedings of the 2005 UK Workshop on Computational Intelligence. UKCI 2005: The 5th annual UK Workshop on Computational Intelligence, London, 05.09.2005-07.09.2005. London: Birkbeck University of London, pp. 281-288. http://www.dcs.bbk.ac.uk/ukci/ukci05proceedings.pdf

Abstract
Genetic Programming (GP) often uses a tree form of graph to represent solutions in a search space. An extension to this representation, Automatically Defined Functions (ADFs) is to allow the ability to express modules. In a previous paper 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 result that the complexity of a bit string is independent of the Universal Turing Machine (UTM) (within an additive constant). 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 corresponds 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 and the proof in a previous paper. We comment on the importance of the class of PRFs for learning.