An improved zero-one law for algorithmic
β
Steven M. Kautz
π
Article
π
1998
π
Elsevier Science
π
English
β 582 KB
Results on random oracles typically involve showing that a class {X :P(X)} has Lebesgue measure one, i.e., that some property P(X) holds for "almost every X". A potentially more informative approach is to show that P(X) is true for every X in some explicitly defined class of random sequences or lang