[FOM] Feasibility

[Vladimir Sazonov]

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,

Vladimir



----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.