# What is the field studying the search and generation of computer programs?

This Github repo hosts a very cool project where the creator is able to, give an integer sequence, predict the most likely next values by searching the smallest/simplest programs that output that integer sequence. I was trying to approach the same idea using lambda-calculus instead of a stack-based language, but I was stuck on the enumeration of valid programs on LC's grammar.

Anyway, what is the field studying that kind of idea and how can I grasp the current state-of-art?

• as YF points out, Kolmogorov complexity is close, but its not typically used in an empirical approach as in the above case, because there are a lot of undecidability issues. there are other more empirical areas of CS where programs analyze or build other programs eg genetic programming, "program synthesis" etc... this is sometimes connected to EE where there is a link between program logic and circuits... also, busy beaver problem is related, and there are also connections to cellular automata.
– vzn
Jan 10, 2014 at 4:39

What you are describing is a Kolmogorov complexity approach. The Kolmogorov complexity of an integer sequence (or a string) is the size of the minimal program computing it (in some fixed Turing-complete language). Here we're looking for the minimal program which generates $n+1$ numbers, the first $n$ of which are the given sequence.
Another (non-computable) approach is the universal probability distribution in which a given integer sequence of complexity $x$ is given a probability in proportion to $2^{-x}$. By conditioning on the first $n$ numbers produced, we can construct a probability distribution on the next number. By restricting the set of programs, we can make this distribution computable (though perhaps not efficiently).