[FOM] Kolmogorov Feasibility??

[Karlis Podnieks]

Mirco Mannucci writes:
 > it recently occurred to me that, as numbers can be realized as
 > binary strings, one could come up with the following: a number is
 > feasible iff its algorithmic complexity as a string is small (with
 > respect to the number itself).
 >
 > By complexity here I mean Kolmogorov complexity, or some related
 > concept.

This proposal could be put in a more radical way.

Let us think of Turing machines as primary objects, and of natural numbers
generated by these machines - as derived objects. Some machine "generates"
number N, if it prints out N times 1 and halts.

Let us say that feasible machines generate "feasible" numbers. Then, the
number 2^2^1000000 will be "feasible" (it can be "generated" by a very small
machine). But most numbers less than 2^2^1000000 will be "unfeasible".

Thus, this approch reveals "complicated structure" of the "real" natural
number system. The idea that any natural number can be generated by
iterating the successor function, is very abstract and not very practical.

Of course, we could consider exponential expressions instead of Turing
machines - as in my posting
http://www.cs.nyu.edu/pipermail/fom/2005-December/009504.html.

Karlis Podnieks
www.ltn.lv/~podnieks
University of Latvia