Contents

• Genetic Programming stochastic search for programs
• What is known about the space of all programs
• Above threshold, proportion of functions of each type independent of length

• Experimental evidence, tree based GP
• Proof linear, e.g. machine code GP
• Proof tree
• ADFs , Indexed Memory, recursion and iteration
• So what?

Background - Genetic Programming

• Genetic Programming is a stochastic technique that produces programs, not by constructing them but by using a genetic algorithm to search the space of possible programs for one of adequate performance.

• In standard GP programs are represented by trees (cf. lisp S-expressions) rather than as lines of code. For example, the simple expression
  
  $\max \left(x^{2}, x+3y\right)$ max(x * x, x + 3 * y);
  
  would be represented as: