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
6 - Aspects of Chaitin’s Omega
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
The halting probability of a Turing machine was introduced by Chaitin, who also proved that it is an algorithmically random real number and named it Omega. Since his seminal work, many popular expositions have appeared, mainly focusing on the metamathematical or philosophical significance of this number (or debating against it). At the same time, a rich mathematical theory exploring the properties of Chaitin's Omega has been brewing in various technical papers, which quietly reveals the significance of this number to many aspects of contemporary algorithmic information theory. The purpose of this survey is to expose these developments and tell a story about Omega which outlines its multi-faceted mathematical properties and roles in algorithmic randomness.
Keywords
- Type
- Chapter
- Information
- Algorithmic RandomnessProgress and Prospects, pp. 175 - 205Publisher: Cambridge University PressPrint publication year: 2020
- 2
- Cited by