2008/05/17 by Kohtaro Tadaki, Tadaki, Kohtaro
Computer Science · Mathematics · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Logic (math.LO) #cs.CC #cs.IT #math.IT #math.LO
paper · pdf · doi:10.48550/arxiv.0805.2691
19 pages, LaTeX2e, no figures
arxiv created 2008/05/17 · arxiv updated 2009/12/01
A real number αis called recursively enumerable if there exists a computable, increasing sequence of rational numbers which converges to α. The randomness of a recursively enumerable real αcan be characterized in various ways using each of the notions; program-size complexity, Martin-Löf test, Chaitin's Ωnumber, the domination and Ω-likeness of α, the universality of a computable, increasing sequence of rational numbers which converges to α, and universal probability. In this paper, we generalize these characterizations of randomness over the notion of partial randomness by parameterizing each of the notions above by a real number T∈(0,1]. We thus present several equivalent characterizations of partial randomness for a recursively enumerable real number.