Information Theory Meets Power Laws

7Coding and Computation

As we have mentioned in the introduction to Chapter 5, there are two standard approaches to the definition of the amount of information: one initiated by Shannon, which applies probability, and another proposed by Kolmogorov, which uses algorithms. It turns out that in both approaches, the amount of information contained in an object is roughly equal to the minimal number of binary digits that we need to describe the object. In fact, we have not touched this interpretation yet and we would like to discuss it in this chapter. In a single package, we will present the coding interpretation of the Shannon entropy and its close links with Kolmogorov's algorithmic complexity, which implements the idea of the minimal coding in a direct way. This chapter develops formally ideas sketched in the half‐formal Sections 1.7 and 1.10.

The general idea of coding, an ingenious invention of the twentieth century, is to represent arbitrary objects from a countable set – such as letters, words, sentences, or whole finite texts – as unique finite sequences of binary digits. With the advent of personal computers and mobile devices, this idea seems as obvious as the idea of the alphabet, but it took some effort to discover profound implications of this idea for foundations of mathematics, computer science, and statistics. In particular, the idea of coding led to discovery of unprovable statements in mathematics by Gödel (1931), which was further strengthened by Chaitin (