Evolving Lambda-Calculus Functions Using Genetic Programming

Genetic Programming (GP) has shown great effectiveness in fields such as Artificial Life by evolving fittest artificial beings in an imaginary biological environment. This study takes GP to a different level, where the environment consists of math problems, whereas individuals in the environment are potential problem solvers, and fitness is measured by the correctness of their answers. This study investigates the history of evolutionary solvers that are versatile and consistent in solving a specific range of problems. Such solvers give insights to the emergence of intelligence. First, the concepts, rules, and applications of GP and Lambda-calculus are studied separately. Then motivations for choosing Lambda-calculus instead of other mathematical systems are explained. Techniques and special modifications are needed to combine Lambda-calculus with GP and also to avoid some potential pitfalls of GP. A final model is presented and tested with several simple mathematical problems. For each problem, after the GP procedure produces the fittest individuals (or fails to do so), the brief history of evolution is analyzed and the structures of the fittest problem solvers are studied