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
Date 1993
Volume 112
Issue 2
Start page 383
End page 390
Abstract 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.
DOI 10.1016/0304-3975(93)90027-Q

Using APA 6th Edition citation style.

[Page generation failure. The bibliography processor requires a browser with Javascript enabled.]

Times viewed: 483

Adding this citation to "My List" will allow you to export this citation in other styles.