C2

Question 1

Shannon’s information theory

Answer 1

How to send messages from sender to receiver in as few bits as possible?

Question 2

entropy h(n)

Answer 2

the amount of information in bits, gained by learning which outcome occurred (equally likely outcomes)

h(n) = log n = - log 1/n
with n the number of possible outcomes

Question 3

unequally likely outcomes

Answer 3

denote probability of each possible outcome by p(x)

h(x) = log 1/p(x) = - log p(x)

Question 4

Shannon’s entropy

Answer 4

H(X) = - sum(p(x) * log(p(x)))

Question 5

Shannon’s Source Coding Theorem

Answer 5

an optimal lossless encoding satisfies
L(a) = - log p(a)
where L(a) is the length in bits of the code word assigned to a

Question 6

decoding

Answer 6

decoding function D
D(y) = x means y is a code word for source word x

E = D^-1 is the encoding relation (not a function because a code word can have multiple corresponding source words)

Question 7

Halting problem

Answer 7

Lemma: there is no recursive function g such that for all x,y we have:
1. g(x,y) = 1 if phi_x(y) is defined and
2. g(x,y) = 0 otherwise

Question 8

relative complexity

Answer 8

let U be some universal Turing machine and x some finite binary string

the relative complexity C_U of x with regard to U is defined as:
C_U(x) = min{ l(p) | U(p) halts and U(p) = x}

a string x is random relative to U iff
C_U(x) = |x|

Question 9

additive optimality

Answer 9

A function f is additively optimal for F
- if it belongs to F and
- if for every g ∈ F there is a constant
cf,g such that C_f (x) ≤ C_g (x) + cf,g, for all x

Question 10

invariance theorem

Answer 10

For any two universal Turing machines,
a constant-length ‘cross-compiler’ exists

Question 11

Kolmogorov complexity C(x)

Answer 11

the length of the shortest program that outputs x and halts (given an additively optimal universal Turing machine)

Question 12

properties of Kolmogorov complexity

Answer 12

x is incompressible iff C(x) ≥ |x|

C(x) can be regarded as the length of the ultimate compressed version from which x can be recovered by a general (lossless!) compression program

BUT C(x) is uncomputable because the halting problem is undecidable

Question 13

Conditional Kolmogorov complexity C(x|y)

Answer 13

the length, in bits, of the shortest computer program that produces x as output when given string y as input

Question 14

Normalised Information Distance (NID)

Answer 14

e(x,y) = max{C(x|y), C(y|x)} / max{C(x), C(y)}