Evolution of lambda-expressions through Genetic Programming

Dorothea Heiss-Czedik and Walter Fontana

We illustrate a minimal version of Genetic Programming operating with -calculus by evolving the predecessor function. The expression obtained works differently than the original version of Kleene. In those runs that were successful hundreds of different expressions realizing the predecessor function were found, indicating a large degree of neutrality. We suggest that the study of the ``-calculus landscape'' holds promise for a more rigorous and systematic understanding of the power and limitations of Genetic Programming as they derive from the language that maps syntactical constructs into functional behaviors.