An improved zero-one law for algorithmically random sequences

DOI10.1016/S0304-3975(97)00116-3zbMath0897.68046MaRDI QIDQ1127324

Steven M. Kautz

Publication date: 13 August 1998

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

zero-one lawalgorithmic randomnessrandom sequence\(n\)-randomness

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items

The weakness of being cohesive, thin or free in reverse mathematics ⋮ On the robustness of ALMOST-$\mathcal {R}$

Cites Work

• Incompleteness theorems for random reals
• Classical recursion theory. Vol. II
• Process complexity and effective random tests
• Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
• An observation on probability versus randomness with applications to complexity classes
• On Languages Reducible to Algorithmically Random Languages
• On the robustness of ALMOST-$\mathcal {R}$
• The definition of random sequences
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item