The Homogenous Capture of Random Strings
Permanent Link(s)
Collections
Author
Natarajan, B. K.
Abstract
It is well known that a set of strings that are random in the Kolmogorov sense is immune to all computable enumerations. In this paper, we discuss the generalization of this property to the computational resource hierarchies. We then introduce the notion of homogeneous capture of sets and show that sets of random strings are not homogeneously captured by any computable enumeration. Again, we discuss the extension of this property to the resource hierarchies. Finally, we discuss the relationship between the notion of homogeneous capture and the traditional concept of randomness.
Date Issued
1985-04
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR85-672
Type
technical report