[FOM] 204:Finite Extrapolation

[Jacques Carette]

First, do not misunderstand me: I am fascinated by this area of mathematics,
and agree that it has been under-explored.  Looking at 'simplicity' instead
of 'complexity' has somehow been under-studied.

> 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 do not understand why you state that Kolmogorov Complexity is
'asymptotic'.  True, a lot of *applications* have been asymptotic in nature,
but the theory itself is very much 'finite', in that it deals primarily with
finite strings, finite programs, and programs terminating in finite time.

Kolmogorov Complexity has been used a lot to study randomness, and here
things are indeed rather 'asymptotic'.  Using it to study *simplicity*
instead, turns the tables around.

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

Your language is clearly recursively enumerable, and your length function is
computable, so yes, this is definitely a good place to start.  But any r.e.
language with computable length function will do.  But that is not 'really'
an interesting question, now is it?  It is clear that in your language,
interesting questions can be posed, but perhaps there could be a slightly
different language with the same power but with completely different
complexities?

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

I conjecture instead that there exists different languages than yours that
can express the same ideas but which contain classes of objects whose
complexity is not within a (universal) constant of the ones from your
language.  This is what I mean by stability.

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

This is why I have used MDL as my principal tool instead of KC itself.  And
that I had to re-interpret it in an exact setting, based on axiomatically
defined theories.  And there, you can get hard data.  See my paper for 2
examples of '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;

I do not (yet) see this.

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

Which questions are these?  If you mean the ones at the end of the posting,
then using gfun in Maple I can force it to give me conjectures for all your
sequences.  A bit of brute force could then prove these.  However, your
sequences are very short, so their information content is very very low,
possibly leading to a lot of ties.

If you mean (unstated!) interesting questions like 'There should be a
effective relation between Schanuel's Conjecture and the simplicity of a
number.  Prove this', then we are really getting somewhere.

Jacques