**Around Kolmogorov Complexity: Basic Notions and Results**

by Alexander Shen

**Publisher**: arXiv.org 2015**Number of pages**: 51

**Description**:

Algorithmic information theory studies description complexity and randomness and is now a well known field of theoretical computer science and mathematical logic. This report covers the basic notions of algorithmic information theory: Kolmogorov complexity (plain, conditional, prefix), Solomonoff universal a priori probability, notions of randomness, effective Hausdorff dimension.

Download or read it online for free here:

**Download link**

(300KB, PDF)

## Similar books

**Essential Coding Theory**

by

**Venkatesan Guruswami, Atri Rudra, Madhu Sudan**-

**University at Buffalo**

Error-correcting codes are clever ways of representing data so that one can recover the original information even if parts of it are corrupted. The basic idea is to introduce redundancy so that the original information can be recovered ...

(

**8545**views)

**Information Theory and Statistical Physics**

by

**Neri Merhav**-

**arXiv**

Lecture notes for a graduate course focusing on the relations between Information Theory and Statistical Physics. The course is aimed at EE graduate students in the area of Communications and Information Theory, or graduate students in Physics.

(

**12142**views)

**Quantum Information Theory**

by

**Robert H. Schumann**-

**arXiv**

A short review of ideas in quantum information theory. Quantum mechanics is presented together with some useful tools for quantum mechanics of open systems. The treatment is pedagogical and suitable for beginning graduates in the field.

(

**15746**views)

**Quantum Information Theory**

by

**Renato Renner**-

**ETH Zurich**

Processing of information is necessarily a physical process. It is not surprising that physics and the theory of information are inherently connected. Quantum information theory is a research area whose goal is to explore this connection.

(

**11719**views)