Note on the topological structure of ramdom strings

A string x is random according to Kolmogorov [10] if, given its length, there is no stringy, sensibly shorter than x, by means of which a universal partial recursive function could produce x. This remarkable definition has been validated in several ways (see [12, 14, 2, 11]) including a topological one [13]. Our present aim is to develop a constructive topological analysis of the ''size'' of the set of random strings in order to show to what extent they are incompressible. A substring of an incompressible string can be compressible [11] (conforming a well-known fact from probability theory: every sufficiently long binary random string must contain long runs of zeros). The converse operation makes sense and we may ask the question: can a compressible string be ''padded'' in order to be a substring of a random string? The answer depends upon the way we ''pad'' the initial string: for instance, if we add only arbitrary long prefixes (suffixes), then the answer is no, but if we pad from both directions, the answer is yes.