[FOM] Kolmogorov Feasibility??

[Stephen G Simpson]

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.

The Kolmogorov complexity of a string s is defined as the length of
the smallest program which eventually halts with output s.  Because of
concerns about the details of how "programs", "halting", and "output"
are defined, it seems to me that the Kolmogorov complexity of s is
mathematically well defined only up to plus or minus O(1).  Therefore,
in Mannucci's non-asymptotic context, what do we mean by "small"?  Or,
is this not a concern, for some reason?

In addition, one must choose between plain Kolmogorov complexity and
prefix-free Kolmogorov complexity, the latter corresponding to
self-delimiting programs, i.e., programs with an end-of-program
marker.  These two complexity notions have strikingly different
asymptotic properties.

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?

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.  Is this a fair statement of their
position?

Alternatively, Mannucci may want to define s to be "Kolmogorov
feasible" if the ratio

      Kolmogorov complexity of s / length of s

is small.  But again, what do we mean by "small" in a non-asymptotic
context?  

Asymptotically, the above ratio is known to be equal to the effective
Hausdorff dimension of s.  The concept of effective Hausdorff
dimension was introduced and studied by in recent years by Jack Lutz.

-- Steve

FOM signature:

  Stephen G. Simpson

  Professor of Mathematics, Pennsylvania State University

  Research interests: foundations of mathematics, mathematical logic