Relative Effective Randomness References
Lecture notes on related topics
Downey's notes are particularly close to what we will be covering.
R. Downey, Some Computability-Theoretic Aspects of Reals and Randomness,
to appear in a volume of the ASL Lecture Notes in Logic
Series. Available from the Victoria
University of Wellington SMCS site.
S. Terwijn, Complexity and Randomness, available from Sebastiaan
Terwijn's site.
P. Gacs, Lecture Notes on Descriptional Complexity and Randomness,
available from Peter Gacs'
site.
The standard reference on Kolmogorov complexity and related
topics
M. Li and P. Vitanyi, An Introduction to Kolmogorov Complexity and Its
Applications, 2nd edition, Springer-Verlag, 1997.
A brief but very nice introduction to Kolmogorov complexity
L. Fortnow, Kolmogorov Complexity, in Aspects of
Complexity (Kaikoura, 2000) (Downey and Hirschfeldt, eds.), de Gruyter
(2001), 73 - 86. Available from Lance Fortnow's
site.
Two papers on c.e. reals
The first one is particularly relevant to what we will be covering.
C. Calude, P. Hertling, B. Khoussainov, and Y. Wang, Recursively Enumerable Reals
and Chaitin Omega Numbers, Theoretical Computer Science 255 (2001),
125 - 149. Also available from the University
of Auckland CDMTCS website.
C. Calude, R. Coles, P. Hertling, and B. Khoussainov, Degree Theoretical Aspects
of Reals and Randomness, in Models and Computability (Cooper and
Truss, eds.), Cambridge University Press (1997), 23 - 39. Also
available from the University
of Auckland CDMTCS website.
A chapter from the upcoming book by Downey and Hirschfeldt
Solovay's theorems relating K and
C.
A proof of the Kraft-Chaitin Theorem
C. Calude and C. Grozea, Kraft-Chaitin Inequality Revisited. Available
from the University
of Auckland CDMTCS website.
A proof that random c.e. reals are Solovay complete
A. Kucera and T. Slaman, Randomness and Recursive Enumerability, SIAM
Journal on Computing 31 (2001), 199 - 211. Also available from Ted
Slaman's site.
Three papers on measures of relative randomness
R. Downey, D. Hirschfeldt, and A. Nies, Randomness, computability, and
density, SIAM Journal on Computing 31 (2002), 1169 - 1183. Also
available here.
R. Downey, D. Hirschfeldt, and G. LaForte, Randomness and
reducibility, to appear in the Journal of Computer and System
Sciences. Available here.
R. Downey, D. Hirschfeldt, A. Nies, and F. Stephan, Trivial reals, to
appear in the Proceedings of the 7th and 8th Asian Logic
Conferences. Available here.