arXiv (Cornell University) · 2021 · 43 citations · 31 references
ComputingComputer ScienceMathematicsAlgorithmsInformation TheoryTheory Of ComputationAlgorithmic ComplexityComplexity TheoryComputational ComplexityRandomized AlgorithmsRandomized ComputationAlgorithmic Information TheoryComplexityInformation ComplexityKolmogorov ComplexityRandomness Complexity
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.
31
How to construct random functions
Oded Goldreich, Shafi Goldwasser, Silvio Micali · Journal of the ACM · 1986 · 2.1K citations · Full text
A formal theory of inductive inference. Part II
Ray J. Solomonoff · Information and Control · 1964 · 1.8K citations
Foundations of the Theory of Probability
B. C. Brookes, A. N. Kolmogorov · The Mathematical Gazette · 1951 · 1.7K citations