Lecture notes on descriptional complexity and randomness
arXiv:2105.04704
Abstract
A didactical survey of the foundations of Algorithmic Information Theory. These notes are short on motivation, history and background but introduce some of the main techniques and concepts of the field. The "manuscript" has been evolving over the years. Please, look at "Version history" below to see what has changed when.
arXiv comment181 pages. arXiv admin note: text overlap with arXiv:cs/0312039
Cited by in corpus (10)
- A Note on A Priori Forecasting and Simplicity Bias in Time Series
- Random strings and tt-degrees of Turing complete C.E. sets
- Algorithmic randomness for Doob's martingale convergence theorem in continuous time
- Multiclass classification utilising an estimated algorithmic probability prior
- Upper semicomputable sumtests for lower semicomputable semimeasures
- Gacs Algorithmic Complexity on Hilbert Spaces and Some of its Applications
- Asymmetry of the Kolmogorov complexity of online predicting odd and even bits
- Relating and contrasting plain and prefix Kolmogorov complexity
- Randomness Conservation over Algorithms
- Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity