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