How much do we have to change a string to increase its Kolmogorov complexity. We show that we can
increase the complexity of any non-random string of length n by flipping O(sqrt(n)) bits and some strings
require
Omega(sqrt(n)) bit flips. For a given m, we also give bounds for ... more >>>

We introduce the study of Kolmogorov complexity with error. For a
metric d, we define C_a(x) to be the length of a shortest
program p which prints a string y such that d(x,y) \le a. We
also study a conditional version of this measure C_{a,b}(x|y)
where the task is, given ... more >>>

Constructive dimension and constructive strong dimension are effectivizations of the Hausdorff and packing dimensions, respectively. Each infinite binary sequence A is assigned a dimension dim(A) in [0,1] and a strong dimension Dim(A) in [0,1].

Let DIM^alpha and DIMstr^alpha be the classes of all sequences of dimension alpha and of strong ... more >>>