[FOM] Kolmogorov Feasibility??

[V.Sazonov@csc.liv.ac.uk]

Quoting Stephen G Simpson <simpson at math.psu.edu> Wed, 12 Jul 2006:

> Modulo these reservations, can we say that s is "Kolmogorov feasible"
> if its Kolmogorov complexity is "feasible", e.g., less than 2^{1000}?
> Is this what is being proposed?

It seems you wanted to say "much less than 2^{1000}". But what does it 
formally mean? If n is much less than 2^{1000}, is n+1 still much less 
than 2^{1000}? Thus, before any considerations on Kolmogorov's 
complexity, the primary question is whether it is formally consistent 
to postulate the existence of a (semi)set F of feasible numbers 
satisfying the axioms:

0 in F, forall n (n in F => n+1 in F), but 2^1000 not in F.

Therefore, in which sense Kolmogorov's complexity is the right way for 
approaching to feasibility? First, F (and some other related concepts 
such as feasible computability, etc.) should be consistently formalised.

On the other hand, having such F, we could consider binary strings of 
feasible length and their complexity. But this is sufficiently subtle 
thing requiring reconsidering even the concept of computability before 
trying to apply anything like Kolmogorov complexity. (See also my 
previous posting.) Also, as to feasible computability (essentially, the 
computability in our real, feasible, world), I doubt very much that any 
unique analogue of Church Thesis would ever hold here. This is because 
feasible numbers are not closed under multiplication what should 
exclude the existence of anything like the universal Turing machine - 
the real base for CT. However note that in the case of Bounded 
Arithmetic where only a weaker axiom

exists n 2^n = infinity

is consistent and the closure under multiplication holds, a universal 
Turing machine can be shown (with a due care) to exist.

>
> Of course, ultra-finitists such as Sazonov may want to reject this
> definition, because they do not admit numbers such as 2^{1000000000}
> as mathematically meaningful, even though they are "Kolmogorov
> feasible" in the above sense.

I admit absolutely any mathematical intuition as soon as it is (or 
could be) formalised including natural numbers, infinite sets, and also 
ultra-finitism. In this sense I am formalist. I am not an 
ultra-finitist in any (quasi)religious sense. What I reject is 
Platonism just because it is an unacceptable in science mysticism.


Vladimir Sazonov



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