An improved zero-one law for algorithmically random sequences

✍ Scribed by Steven M. Kautz

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 582 KB
• Volume: 191
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(97)00116-3

✦ Synopsis

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 languages. In this note we consider the algorithmically random sequences originally defined by Martin-Lijf and their generalizations, the n-random sequences. Our result is an effective form of the classical zero-one law: for each n > 1, if a class {X : P(X)} is closed under finite variation and has arithmetical complexity ,Yi+, or ZZz+, (roughly, the property P can be expressed with n + 1 alternations of quantifiers), then either P holds for every n-random sequence or else holds for none of them. This result has been used by Book and Mayordomo to give new characterizations of complexity classes of the form ALMOST-W, the languages which can be <@-reduced to almost every oracle, where W is a reducibility.