6
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – vzn
    Jan 10, 2014 at 4:39

2 Answers 2

3
$\begingroup$

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.

Kolmogorov complexity is not computable - that is, one cannot compute the size of a minimal program computing a given sequence. The implementation you mention computes a restricted version of Kolmogorov complexity in which the programs are very simple (and always halt).

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).

$\endgroup$
3
$\begingroup$

This is broad, studied and impinging in several different areas, and not confined to the following:

  • Program synthesis. The idea is that a formal specification of the program's input & output relationship is given and software can be used to search or derive for programs that satisfy the specification. Here are some recent research results at Microsoft.

  • Genetic programming and genetic algorithms. This is a field in machine learning where evolutionary processes are used to evolve functioning programs.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.