[FOM] 204:Finite Extrapolation

[Harvey Friedman]

On 1/19/04 12:25 PM, "Jacques Carette" <carette at mcmaster.ca> wrote:

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

I should have mentioned this Encyclopedia. But the main point of the posting
concerns 

*a detailed NONASYMPTOTIC language theoretic investigation.*

I asked among the most obvious basic questions towards a language theoretic
investigation yielding hard data.

Since I never saw this explicitly proposed, and since I think that with a
lot of hard work - in fact of a style that I have never seen - I made this
posting.
> 
>> 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.

That stuff is asymptotic, with no attempt to get any hard data. The whole
point of my posting is to actually get hard data, overcoming a principle
objection that is commonly made to Kolmogorov Complexity and the like.

I believe that I have pinpointed appropriate language theoretic contexts
where it will be highly nontrivial but feasible to start obtaining hard data
of an interesting kind. It is altogether too easy to spill over into
entirely humanly intractable questions here. But I think I have avoided
this, and come to a good place.

I remember working very briefly on the asymptotic Kolmogorov Complexity,
obtaining such asymptotic results as:

"it is unlikely that for two randomly given finite sequences of a given
large length, one can decide in ZFC which is more complex (or a tie)"

suitably formulated. Such things are probably well known.

> 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.
> 
I addressed the issue of stability in my posting, and conjectured that there
is a lot of stability - more than enough to justify an intensive
investigation of simple specific sequences.

Kolmogorov Complexity "succeeds" as you say, simply by becoming asymptotic,
with no hard data.

I would imagine that you would probably now agree, upon reflection, that

i) this proposal differs greatly from anything you have mentioned,
especially in terms of the techniques needed to prove anything interesting;

ii) it addresses a standard complaint about Kolmogorov complexity with a
specific rather promising proposal;

iii) you do not know how to answer any of the specific questions raised in
my posting, even though they are the most obvious first questions to ask.

On 1/19/04 1:33 PM, "Matthew Frank" <mfrank at math.uchicago.edu> wrote:

> There's an issue here with recursive definitions of sequences.  The
> standard treatment of sequences in the suggested language is so awkward
> that intuitively simple initial sequences lead to odd definitions.

...

> So the question about sequences would become more interesting by adding
> some capacity for recursive definitions to the suggested language.

I am fully aware of this issue. I didn't go that route YET because there is
no question that this will make the investigation incomparably more
difficult to suitably get off of the ground. The more powerful the language,
the harder it is to get a handle on what can be said in that language, even
with very few symbols. Adding recursion is obviously a good idea AFTER the
subject is gotten off the ground.

Harvey Friedman