Atlas: Equivalent characterizations of partial randomness for a recursively enumerable real by Kohtaro Tadaki

Atlas home || Conferences | Abstracts | about Atlas

Conference on Computability, Complexity and Randomness
May 19-23, 2008
Institute of Mathematical Science, Nanjing University.
Nanjing, JiangSu Province, P. R. of China

Organizers
Verónica Becher (University of Buenos Aires, Argentina), Rod Downey (Victoria University, Wellington, New Zealand), Denis Hirschfeldt (University of Chicago, USA), Jack Lutz (Iowa State University, USA), Wolfgang Merkle (Universität Heidelberg, Germany), Joseph Miller (University of Connecticut, USA), Liang Yu (Nanjing University, China)

View Abstracts
Conference Homepage

Equivalent characterizations of partial randomness for a recursively enumerable real
by
Kohtaro Tadaki
Chuo University

We present several equivalent characterizations of partial randomness for a recursively enumerable real number by generalizing the corresponding precedent results on equivalent characterizations of randomness for a recursively enumerable real number over the notion of partial randomness.

One of the consequences of the generalization is as follows: Let T be a computable real number with 0<T<=1. Then, for every recursively enumerable real number A with 0<A<1, Tn<H(A_n)+O(1) if and only if there exists a universal probability M such that A is the sum of M(s)^{1/T} over all finite binary strings s, where H(A_n) is the prefix program-size complexity of the first n bits of the base-two expansion of A.

PDF

Date received: February 29, 2008