Book contents
- Frontmatter
- Contents
- Preface
- 1 Key developments in algorithmic randomness
- 2 Algorithmic randomness in ergodic theory
- 3 Algorithmic randomness and constructive/computable measure theory
- 4 Algorithmic randomness and layerwise computability
- 5 Relativization in randomness
- 6 Aspects of Chaitin’s Omega
- 7 Biased algorithmic randomness
- 8 Higher randomness
- 9 Resource bounded randomness and its applications
- Index
4 - Algorithmic randomness and layerwise computability
Published online by Cambridge University Press: 07 May 2020
- Frontmatter
- Contents
- Preface
- 1 Key developments in algorithmic randomness
- 2 Algorithmic randomness in ergodic theory
- 3 Algorithmic randomness and constructive/computable measure theory
- 4 Algorithmic randomness and layerwise computability
- 5 Relativization in randomness
- 6 Aspects of Chaitin’s Omega
- 7 Biased algorithmic randomness
- 8 Higher randomness
- 9 Resource bounded randomness and its applications
- Index
Summary
Algorithmic randomness lies at the intersection between computability theory and probability theory. In order to fully explore this interaction, one naturally needs a computable version of measurable functions. While several such notions appear in the literature, most of them do not interact well with algorithmic randomness because they are only defined up to a null set. Therefore, we need a computable notion of measurable function which is well defined on algorithmically random points, and this is what layerwise computability precisely does. This article is a survey about this notion. We give the main definitions, the most important properties, and several applications of this notion. We prioritize motivating this framework and explaining its salient features.
Keywords
- Type
- Chapter
- Information
- Algorithmic RandomnessProgress and Prospects, pp. 115 - 133Publisher: Cambridge University PressPrint publication year: 2020
- 1
- Cited by