# [FOM] Feasibility

Vladimir Sazonov V.Sazonov at csc.liv.ac.uk
Fri Dec 24 14:13:04 EST 2004

Dear Gernot,

Quoting Gernot Salzer <salzer at logic.at>:
> This is all very well (and not really debatable) as long as we agree
> that we are just exploring interesting theories and structures.
> The problem starts when we get philosophical and pretend to describe
> the universe, and mix "reality" (whatever this may be) with models
> that were designed to reflect only certain properties of it or none
> at all.

No pretension to describe the universe! Just an attempt to
realize what is the relation of natural numbers to our real
world by considering the concept of feasible numbers.

>
> If questions about unary notation being natural means that they come
> easily to ones mind, ok.

I am sending you my reply to Matt Insall with appropriate comments.

If it means that they are a good description
> of the universe, we start to move on thin ice.
> Concerning the original question about where infinity starts I don't
> (yet?) see the relevance of this type of finitism for modelling (aspects
> of) the universe. Something like Kolmogorov complexity seems to be more
> appropriate to define the size of numbers than their unary length.
> But I'd be happy to learn about interesting consequences of this
> unary view.

Does Kolmogorov complexity define the size of numbers?
By the way, it is actually not about numbers, but rather
about binary strings. Their size (length) can be long,
but the complexity high, and vice versa.

Once, I considered a "unary" version of Kolmogorov complexity.
Instead of additively optimal encoding of binary strings
by binary strings, U:{0,1}* -> {0,1}*, we can define
polynomially optimal (which could be made even injective)
encoding \xi:{1}* -> {0,1}* of binary strings by unary strings.
Then (the length of) unary strings would serve as the measure
of complexity of binary strings. This technique (with unary
strings as codes) was also used to get some independence
result on complexity of SAT.

If to return back to the idea of feasibility, it is
potentially related with complexity of binary strings.
But, first of all it is about the length of (binary or
unary) strings, whether it is feasible or not.

I repeat, the first problem is whether it is possible
to formalize this concept at all. Actually, I have a
version of such a formalization (see
http://www.csc.liv.ac.uk/~sazonov/papers/lcc.ps).

Of course, it is extremely important question for myself
whether feasibility is really interesting mathematical
concept, and, in principle, I have some arguments for that.
I have already no doubts that it is potentially a
mathematical concept. It only should be further developed.
The problem is that further informal discussion  like this
without touchig on the necessary formal aspects will be
seemingly not so fruitful.

I only mention that the main motivation of considering
feasibility concept is the same as for complexity theory.
In both cases we care about resources used by computations.
Complexity theory just counts and compares such resources.
Alternative, but related approach would consist in
reconsidering the very concept of natural number.

Merry Christmas and Happy New Year,