How many Good Programs are there? How Long are they?
Morgan Kaufmann, William B. Langdon · 2002
We model the distribution of functions implemented by non-recursive programs, similar to linear genetic programming (GP). Most functions are constants, the remainder are mostly parsimonious. The eect of ad-hoc rules on GP are described and new heuristics are proposed. Bounds on how long programs need to be before the distribution of their functionality is close to its limiting distribution are provided in general and for average computers. Results for average computers and a model like genetic programming are experimentally tested.