AN IMPROVED ZERO-ONE LAW FOR ALGORITHMICALLY RANDOM SEQUENCES

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 ran dom sequences or languages. In this note we consider the algorithmical ly random sequences originally defined by Martin-Lof and their general izations, the n-random sequences. Our result is an effective form of t he classical zero-one law: for each n greater than or equal to 1, if a class {X:P(X)} is closed under finite variation and has arithmetical complexity Sigma(n+1)(0) or Pi(n+1)(0) 1 (roughly, the property P can be expressed with n+1 alternations of quantifiers), then either P hold s for every n-random sequence or else holds for none of them. This res ult has been used by Book and Mayordomo to give new characterizations of complexity classes of the form ALMOST-R, the languages which can be less than or equal to(R)-reduced to almost every oracle, where R is a reducibility.