**News**

5 Oct, 2012 Updated the reference list

The notion of randomness, prediction and probability based on algorithmic information theory and computable analysis

Algorithmic Information Theory gives the definition of complexity of a concrete object. Then the notion of randomness (algorithmic randomness) and the notion of prediction and probability (algorithmic probability) have been studied. By combining with computable analysis developed especially recently, I try to study the notion in detail.

**Computability theory**

The theory of computability from natural numbers to natural numbers

Summary – Computability theory(Wikipedia)

Undergraduate level text – S. B. Cooper, 2004. Computability Theory, Chapman & Hall/CRC. ISBN 1-58-488237-9

Advanced text – P. Odifreddi, 1989. Classical Recursion Theory, North-Holland. ISBN 0-444-87295-7

Advanced text – P. Odifreddi, 1999. Classical Recursion Theory, Volume II, Elsevier. ISBN 0-444-50205-X

Advanced text – R. I. Soare, 1987. Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer-Verlag. ISBN 0-387-15299-7.

**Algorithmic randomness**

The theory of random indivisual elements

Summary – Algorithmic randomness(Scholarpedia)

Summary – Algorithmically random sequence(Wikipedia)

Summary – Kolmogorov complexity(Wikipedia)

Survey paper – R. Downey, D. R. Hirschfeldt, A. Nies, and S. A. Terwijn, 2006. “Calibrating randomness”, The Bulletin of Symbolic Logic, vol.12, Num. 3, pp.411-491.

Text – R. Downey, D. R. Hirschfeldt, 2010. Algorithmic Randomness and complexity, Springer.

Text – A. Nies, 2009. Computability and Randomness, Oxford University Press.

**Computable analysis**

The study of real functions carried out in a computable manner

Survey paper – V. Brattka, P. Hertling and K. Weihrauch, 2008. “A Tutorial on Computable Analysis”, New Computational Paradigms, pp.425-491.

Research paper – K. Weihrauch and T. Grubba, 2009. “Elementary Computable Topology”, Journal of Universal Computer Science, vol. 15, no. 6, pp.1381-1422.

Text – K. Weihrauch, 2000. Computable Analysis, Springer.

**Game-Theoretic Probability**

Probability theory via game theoretic approach

Text – G. Shafer and V. Vovk, 2001. Probability and Finance: It’s Only a Game!, Wiley-Interscience.

**More reference**

biball