Oxford, England: Oxford University Press UK (2008)
| Abstract |
The interplay between computability and randomness has been an active area of research in recent years, reflected by ample funding in the USA, numerous workshops, and publications on the subject. The complexity and the randomness aspect of a set of natural numbers are closely related. Traditionally, computability theory is concerned with the complexity aspect. However, computability theoretic tools can also be used to introduce mathematical counterparts for the intuitive notion of randomness of a set. Recent research shows that, conversely, concepts and methods originating from randomness enrich computability theory.The book covers topics such as lowness and highness properties, Kolmogorov complexity, betting strategies and higher computability. Both the basics and recent research results are desribed, providing a very readable introduction to the exciting interface of computability and randomness for graduates and researchers in computability theory, theoretical computer science, and measure theory.
|
| Keywords | advanced computability theory |
| Categories | (categorize this paper) |
| Reprint years | 2009, 2012 |
| Buy this book | $14.34 used $123.36 new Amazon page |
| ISBN(s) | 9780199652600 9780199230761 0199230765 0199652600 |
| Options |
Mark as duplicate
Export citation
Request removal from index
|
Download options
PhilArchive copy
Upload a copy of this paper Check publisher's policy Papers currently archived: 69,226
External links
(no proxy) Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library
- Sign in / register and customize your OpenURL resolver..
- Configure custom resolver
References found in this work BETA
No references found.
Citations of this work BETA
Probability and Randomness.Antony Eagle - 2016 - In Alan Hájek & Christopher Hitchcock (eds.), The Oxford Handbook of Probability and Philosophy. Oxford, U.K.: Oxford University Press. pp. 440-459.
Putnam’s Diagonal Argument and the Impossibility of a Universal Learning Machine.Tom F. Sterkenburg - 2019 - Erkenntnis 84 (3):633-656.
Solomonoff Prediction and Occam’s Razor.Tom F. Sterkenburg - 2016 - Philosophy of Science 83 (4):459-479.
Demuth Randomness and Computational Complexity.Antonín Kučera & André Nies - 2011 - Annals of Pure and Applied Logic 162 (7):504-513.
Benign Cost Functions and Lowness Properties.Noam Greenberg & André Nies - 2011 - Journal of Symbolic Logic 76 (1):289 - 312.
View all 21 citations / Add more citations
Similar books and articles
Algorithmic Randomness and Measures of Complexity.George Barmpalias - forthcoming - Association for Symbolic Logic: The Bulletin of Symbolic Logic.
Computability of the Ergodic Decomposition.Mathieu Hoyrup - 2013 - Annals of Pure and Applied Logic 164 (5):542-549.
A C.E. Real That Cannot Be SW-Computed by Any Ω Number.George Barmpalias & Andrew E. M. Lewis - 2006 - Notre Dame Journal of Formal Logic 47 (2):197-209.
Computability and Complexity: From a Programming Perspective Vol. 21.N. D. Jones - 1997 - MIT Press.
Algorithmic Randomness and Complexity. Theory and Applications of Computability.Rodney G. Downey & Denis R. Hirschfeldt - 2012 - Bulletin of Symbolic Logic 18 (1):126-128.
Randomness, Computability and Algebraic Specifications.Bakhadyr Khoussainov - 1998 - Annals of Pure and Applied Logic 91 (1):1-15.
Randomness and Computability: Open Questions.Joseph S. Miller & André Nies - 2006 - Bulletin of Symbolic Logic 12 (3):390-410.
REVIEWS-A. Nies, Computability and Randomness.Anthony Morphett - 2010 - Bulletin of Symbolic Logic 16 (1).
Lowness and Π₂⁰ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044-1052.
Computability and Randomness. [REVIEW]Anthony Morphett - 2010 - Bulletin of Symbolic Logic 16 (1):85-86.
Lowness and $\pi _{2}^{0}$ Nullsets.Rod Downey, Andre Nies, Rebecca Weber & Liang Yu - 2006 - Journal of Symbolic Logic 71 (3):1044 - 1052.
Remarks on the Development of Computability.Stewart Shapiro - 1983 - History and Philosophy of Logic 4 (1-2):203-220.
Analytics
Added to PP index
2015-10-14
Total views
2 ( #1,443,000 of 2,499,684 )
Recent downloads (6 months)
2 ( #278,274 of 2,499,684 )
2015-10-14
Total views
2 ( #1,443,000 of 2,499,684 )
Recent downloads (6 months)
2 ( #278,274 of 2,499,684 )
How can I increase my downloads?
Downloads
