[FOM] 204:Finite Extrapolation

[Jacques Carette]

The pre-existing work relating to this topic is vast.

>From the 'experimental mathematics' side, a good starting point is Sloane's
Encyclopedia of Integer Sequences, and the many papers cited there.  There
is a lot of software (and theory!) that helps with such extrapolation, most
of which based on generalized Pade approximants and/or LLL.

>From the foundational side, clearly what is laid out below is just a
restatement of Minumum Description Length (MDL), as advocated by Rissanen;
this can also be viewed as being a particular specialization of Kolmogorov
Complexity (or sometimes known as algorithmic information theory).  The
textbook by Li and Vitanyi "An Introduction to Kolmogorov Complexity" is
particularly lucid.  There is considerable literature on this topic, the
foundations of which is from the 60's.

I can even add my (small) contribution to this: in the larger context of
'simplification of expressions' [rather than just sequences of integers] for
Computer Algebra Systems, the same issue of 'simple' arises.  I have
submitted a paper 'Understanding Expression Simplification' that merges MDL,
and computational and axiomatic theories of expressions to produce what I
believe is a fairly stable metric for 'complexity'.  The biggest danger in
this area is to give simplicity metrics that are not stable under
isomorphism/theory interpretations; this is where Kolmogorov Complexity
succeeds.
See http://www.cas.mcmaster.ca/~carette/publications.html for a copy of the
article.

Jacques