The Homogenous Capture of Random Strings
Natarajan, B. K.
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.
computer science; technical report
Previously Published As