A generalization of Levin-Schnorr's theorem

2013/10/11 by Keita Yokoyama, Yokoyama, Keita
Biochemistry, Genetics and Molecular Biology · Computer Science · #Computability, Logic, AI Algorithms #DNA and Biological Computing #FOS: Mathematics #Logic (math.LO) #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1310.3091

openalex publication_date 2013/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this paper, we will generalize the definition of partially random or complex reals, and then show the duality of random and complex, i.e., a generalized version of Levin-Schnorr's theorem. We also study randomness from the view point of arithmetic using the relativization to a complete Π⁰₁-class.

Related

• Randomness and uniform distribution modulo one
• Randomness notions and reverse mathematics
• Notes on random reals
• Random semicomputable reals revisited
• Equivalent characterizations of partial randomness for a recursively enumerable real