Slightly Beyond Turing's Computability for Studying Genetic Programming

摘要

Inspired by genetic programming (GP), we study iterative algorithms for non-computable tasks and compare them to na?ve models. This framework justifies many practical standard tricks from GP and also provides complexity lower-bounds which justify the computational cost of GP thanks to the use of Kolmogorov's complexity in bounded time.