On the close interaction between algorithmic randomness and constructive/computable measure theory

Abstract

This is a survey of constructive and computable measure theory with an emphasis on the close connections with algorithmic randomness. We give a brief history of constructive measure theory from Brouwer to the present, emphasizing how Schnorr randomness is the randomness notion implicit in the work of Brouwer, Bishop, Demuth, and others. We survey a number of recent results showing that classical almost everywhere convergence theorems can be used to characterize many of the common randomness notions including Schnorr randomness, computable randomness, and Martin-Löf randomness. Last, we go into more detail about computable measure theory, showing how all the major approaches are basically equivalent (even though the definitions can vary greatly).

References in corpus (20)

• Local stability of ergodic averages
• Randomness and Differentiability
• Integrals and Valuations
• Upcrossing inequalities for stationary sequences and applications
• Algorithmic randomness, reverse mathematics, and the dominated convergence theorem
• Effective dimension of points visited by Brownian motion
• Computable de Finetti measures
• On computability and disintegration
• Kolmogorov complexity and strong approximation of Brownian motion
• Computable Stochastic Processes
• Fourier spectra of measures associated with algorithmically random Brownian motion
• Computable Jordan Decomposition of Linear Continuous Functionals on $C[0;1]$
• Representations of measurable sets in computable measure theory
• Computability of Probability Distributions and Characteristic Functions
• An Application of Computable Distributions to the Semantics of Probabilistic Programs
• Domains and Stochastic Processes
• Domains and Random Variables
• On the computability of graphons
• The reverse mathematics of theorems of Jordan and Lebesgue
• Categorifying measure theory: a roadmap

Cited by in corpus (1)

• Luzin's (N) and randomness reflection