Note on the topological structure of ramdom strings
Description
Citation
| Title | Note on the topological structure of ramdom strings |
| Author(s) | C. Calude, C. 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. |
| ISSN | 0304-3975 |
Using APA 6th Edition citation style.
[Page generation failure. The bibliography processor requires a browser with Javascript enabled.]
Times viewed: 83
