Note on the topological structure of ramdom strings
|Title||Note on the topological structure of ramdom strings|
|Author(s)||C. Calude, Cezar Campeanu|
|Journal||Theoretical Computer Science|
|Abstract||A string x is random according to Kolmogorov  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 . 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  (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.|
Using APA 6th Edition citation style.
Times viewed: 313