Invariance of function complexity under primitive recursive functions

Citation

Woodward J (2006) Invariance of function complexity under primitive recursive functions. In: Collet P, Tomassini M, Ebner M, Gustafson S & Ekart A (eds.) Genetic Programming: 9th European Conference, EuroGP 2006, Budapest, Hungary, April 10-12, 2006. Proceedings. Lecture Notes in Computer Science, 3905. 9th European Conference, EuroGP 2006, Budapest, Hungary, 10.04.2006-12.04.2006. Berlin Heidelberg: Springer, pp. 310-319. http://link.springer.com/chapter/10.1007/11729976_28#; https://doi.org/10.1007/11729976_28

Abstract
Genetic Programming (GP) [1] often uses a tree form of a graph to represent solutions. An extension to this representation, Automatically Defined Functions (ADFs) [1] is to allow the ability to express modules. In [2] 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 reminiscent of the result that the complexity of a bit string is independent of the choice of Universal Turing Machine (UTM) (within an additive constant) [3], 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 their representations. These representations are then capable of expressing a wider classes of functions, for example the primitive recursive functions (PRFs). We prove that given two representations which express the PRFs (and only 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 [3] and the proof in [2].