**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

**Error-Correction Coding and Decoding**

by

**Martin Tomlinson, et al.**-

**Springer**

This book discusses both the theory and practical applications of self-correcting data, commonly known as error-correcting codes. The applications included demonstrate the importance of these codes in a wide range of everyday technologies.

(

**1213**views)

**Algorithmic Information Theory**

by

**Gregory. J. Chaitin**-

**Cambridge University Press**

The book presents the strongest possible version of GĂ¶del's incompleteness theorem, using an information-theoretic approach based on the size of computer programs. The author tried to present the material in the most direct fashion possible.

(

**7585**views)

**A Short Course in Information Theory**

by

**David J. C. MacKay**-

**University of Cambridge**

This text discusses the theorems of Claude Shannon, starting from the source coding theorem, and culminating in the noisy channel coding theorem. Along the way we will study simple examples of codes for data compression and error correction.

(

**8025**views)

**From Classical to Quantum Shannon Theory**

by

**Mark M. Wilde**-

**arXiv**

The aim of this book is to develop 'from the ground up' many of the major developments in quantum Shannon theory. We study quantum mechanics for quantum information theory, we give important unit protocols of teleportation, super-dense coding, etc.

(

**5170**views)